Гамильтоновы циклы
Гамильтоновым циклом (путем) называют простой цикл (путь), содержащий все вершины графа.
Внешне определение гамильтонова цикла похоже на определение эйлерова цикла. Однако есть кардинальное различие в сложности решения соответствующих задач. Мы видели, что имеется достаточно простой критерий существования эйлерова цикла и эффективный алгоритм его построения. Для гамильтоновых же циклов (и путей) неизвестно никаких просто проверяемых необходимых и достаточных условий их существования, а все известные алгоритмы требуют для некоторых графов перебора большого числа вариантов. Такие задачи называют задачами переборного типа или неподдающимися задачами. Очень многие известные задачи относятся к разряду неподдающихся, среди них немало задач на графах. Существует математическая теория сложности алгоритмов и задач, в которой под эффективным алгоритмом понимают алгоритм, время работы которого ограничено сверху полиномом от длины записи входных данных. Выводы этой теории делают весьма правдоподобным предположение о том, что для многих неподдающихся задач, в том числе и для задачи о гамильтоновом цикле, не существует эффективных алгоритмов.
Перебор вариантов в задаче о гамильтоновом цикле (построить гамильтонов цикл или убедиться, что его не существует) можно организовать с помощью дерева путей. Это дерево представляет всевозможные простые пути в данном графе, начинающиеся в некоторой вершине а. Его вершины соответствуют вершинам графа, при этом каждая вершина графа может быть представлена в дереве несколько раз. Оно может быть построено следующим образом. Выберем в графе произвольно вершину а и объявим ее корнем дерева. Вершины, смежные с а, добавим к дереву в качестве сыновей вершины а. Для каждой вершины b, добавленной к дереву, рассмотрим все смежные с ней вершины и те из них, которые не лежат на пути (в дереве) из a в b, добавим к дереву в качестве сыновей вершины b. Процесс построения дерева заканчивается, когда к нему уже невозможно добавить новую вершину. Очевидно, что каждому пути в дереве, начинающемся в корне, соответствует точно такой же (простой) путь в графе, и обратно, каждому простому пути в графе с началом в вершине а соответствует такой же путь в дереве. Каждой вершине, находящейся в дереве на расстоянии от корня, соответствует гамильтонов путь в графе с началом в вершине а, а если последняя вершина этого пути смежна с а, то получаем гамильтонов цикл. Если высота дерева путей не превосходит , то в графе нет гамильтоновых путей, начинающихся в а, и нет гамильтоновых циклов. На рисунке 7 показаны граф и его дерево путей из вершины 1.
Дерево путей можно построить с помощью процедуры типа поиска в ширину: вершины исследуются и добавляются к дереву в порядке возрастания их расстояний (в дереве) от корня. Отличие от обычного поиска в ширину состоит в том, что вершина графа может добавляться к дереву несколько раз.
Дерево путей может быть очень большим. Для полного графа в этом дереве будет листьев. Однако, если задача состоит в том, чтобы найти один гамильтонов путь или цикл (если такой существует), то совсем не обязательно строить это дерево целиком. Можно организовать обход этого дерева с помощью, скажем, поиска в глубину, без его явного построения. Для полного графа такой алгоритм даст ответ очень быстро, но в некоторых случаях время его работы тоже растет с факториальной скоростью. Например, для графа , если в качестве стартовой выбрана не изолированная вершина, будут рассмотрены все простых путей длины в большой компоненте.
Кодом Грея порядка называется расположение всех двоичных слов длины в последовательность, в которой любые два соседних слова различаются ровно в одной букве. Двоичные слова длины n можно рассматривать как вершины графа – ребра этого графа соединяют как раз пары слов, различающихся в одной букве. Значит, код Грея есть не что иное, как гамильтонов путь в графе . Существование такого пути при любом n легко доказать с помощью индукции, используя равенство .
В ориентированном графе гамильтонов цикл (путь) – это ориентированный цикл (путь), проходящий через каждую вершину точно один раз. Задачи о гамильтоновых циклах и путях для орграфов в общем случае тоже неподдающиеся. В то же время имеется важный класс графов, для которых эти задачи имеют простое решение. Это так называемые турниры.
Орграф называется турниром, если для каждых двух вершин в нем имеется единственное ребро, соединяющее эти вершины.
Теорема о гамильтоновых путях в турнирах. В любом турнире имеется гамильтонов путь.
Для нахождения гамильтонова пути в турнире можно использовать следующее легко доказываемое свойство: если – ориентированный простой путь в турнире, y – вершина, не принадлежащая этому пути, то хотя бы одна из последовательностей , , …, тоже является ориентированным простым путем.
Аналогично обстоит дело с гамильтоновыми циклами в турнирах (см. задачу 5.25).
Пространство циклов
Циклы – очень важная часть структуры графа, с ними приходится иметь дело при решении многих задач. В графе может быть очень много циклов (см. задачу 5.15), поэтому полезно иметь средства для компактного описания множества всех циклов данного графа и манипулирования ими. Одно из наиболее удобных средств такого рода предоставляет аппарат линейной алгебры.
Далее будем рассматривать графы с фиксированным множеством вершин V. Буквой O будем обозначать пустой граф: .
Суммой по модулю 2 (в дальнейшем в этом разделе будем называть ее просто суммой) двух графов и называется граф , где обозначает симметрическую разность множеств.
Следующие свойства введенной операции очевидны или легко проверяются.
1) Коммутативность: для любых и .
2) Ассоциативность: для любых .
3) для любого G.
4) для любого G.
Отсюда следует, что множество всех графов с множеством вершин V образует абелеву группу относительно операции сложения по модулю 2. Нейтральным элементом («нулем») этой группы служит граф O, а противоположным к каждому графу является сам этот граф. Уравнение с неизвестным X и заданными графами G и H имеет единственное решение . Благодаря свойству ассоциативности мы можем образовывать выражения вида , не используя скобок для указания порядка действий. Легко понять, что ребро принадлежит графу тогда и только тогда, когда оно принадлежит нечетному количеству из графов .
Рассмотрим множество из двух элементов <0,1>. Оно является полем относительно операций умножения и сложения по модулю 2. Определим операцию умножения элементов этого поля на графы: , для любого графа G. Множество всех графов с множеством вершин V при введенных операциях сложения графов и умножения на элементы поля является линейным векторным пространством (т. е. подчиняется аксиоматике таких пространств).
Зафиксируем некоторый граф и рассмотрим множество всех его остовных подграфов. Это множество состоит из элементов, среди них сам граф G и граф . Оно замкнуто относительно сложения графов и умножения на элементы поля, следовательно, является подпространством пространства всех графов. Его называют пространством подграфов графа G.
В пространстве подграфов можно естественным способом ввести координаты. Занумеруем ребра графа G: . Теперь остовному подграфу можно поставить в соответствие характеристический вектор его множества ребер:
Получаем взаимно однозначное соответствие между множеством подграфов и множеством -мерных двоичных векторов. Сумме графов соответствует векторная (покоординатная) сумма по модулю 2 их характеристических векторов.
Далее в этом разделе слово «цикл» будем понимать несколько иначе, чем до сих пор. Именно, циклом графа G будем называть его остовный подграф, у которого одна компонента связности является простым циклом, а остальные – изолированными вершинами. Остовный подграф, у которого степени всех вершин четны, называется квазициклом. Таким образом, любой цикл является квазициклом и граф О – квазицикл.
Теорема о квазициклах. Множество всех квазициклов данного графа замкнуто относительно сложения по модулю 2.
Из этой теоремы следует, что множество всех квазициклов графа G является подпространством пространства подграфов, оно называется пространством циклов графа.
Компактное представление линейного векторного пространства дает его базис. Базис пространства циклов называют просто базисом циклов. Построить базис циклов можно следующим образом. Выберем в графе G какой-нибудь каркас T. Пусть – все ребра графа G, не принадлежащие T. Если добавить к T ребро , то в полученном графе образуется единственный цикл . Таким образом, получаем семейство из s циклов, они называются фундаментальными циклами относительно каркаса T.
Теорема о фундаментальных циклах. Множество всех фундаментальных циклов относительно любого каркаса T графа G образует базис пространства циклов этого графа.
Из этой теоремы следует, что размерность пространства циклов графа равна числу ребер, не входящих в его каркас. Так как каркас содержит ребер, где k – число компонент связности графа, то эта размерность равна . Это число называют цикломатическим числом графа.
Каркас графа можно построить многими способам. Для построения базиса циклов графа особенно удобен поиск в глубину благодаря основному свойству DFS-дерева – каждое обратное ребро относительно этого дерева является продольным. Это означает, что из двух вершин такого ребра одна является предком другой в DFS-дереве. Каждое такое ребро в процессе поиска в глубину встретится дважды – один раз, когда активной вершиной будет предок, другой раз, когда ею будет потомок. В этом последнем случае искомый фундаментальный цикл состоит из рассматриваемого обратного ребра и участка пути в DFS-дереве, соединяющего эти две вершины. Но этот путь так или иначе запоминается в процессе обхода в глубину, так как он необходим для последующего возвращения. Если, например, для хранения открытых вершин используется стек, то вершины этого пути находятся в верхней части стека. В любом случае этот путь легко доступен и цикл находится без труда.
Хотя сам поиск в глубину выполняется за линейное от числа вершин и ребер время, решающее влияние на трудоемкость алгоритма оказывает необходимость запоминать встречающиеся циклы. Подсчитаем суммарную длину фундаментальных циклов, полученных с помощью поиска в глубину для полного графа с n вершинами. DFS-дерево в этом случае является простым путем, относительно него будет цикла длины 3, цикла длины 4, …, 1 цикл длины n. Сумма длин всех фундаментальных циклов будет равна
Таким образом, на некоторых графах число операций этого алгоритма будет величиной порядка .
С пространством циклов тесно связано пространство разрезов графа. Пусть , . Разрез графа G, определяемый множеством А, – это остовный подграф, ребрами которого являются все ребра графа, соединяющие вершины из А с вершинами из .
Теорема о разрезах. Множество всех разрезов данного графа замкнуто относительно сложения по модулю 2.
Разрез, определяемый одноэлементным множеством А, называется элементарным. Базис пространства разрезов связного графа можно получить, если взять все его элементарные разрезы, кроме одного (любого). Для несвязного графа это нужно проделать для каждой компоненты связности. Таким образом, размерность пространства разрезов графа с k компонентами равна .
Пусть и – характеристические векторы двух остовных подграфов графа G. Будем говорить, что эти подграфы ортогональны, если . Это равносильно тому, что подграфы имеют четное число общих ребер.
Теорема о циклах и разрезах. Любой цикл данного графа ортогонален любому его разрезу.
Так как сумма размерностей пространств циклов и разрезов равна размерности пространства подграфов, то из этой теоремы следует, что пространства циклов и разрезов являются ортогональными дополнениями друг друга. Это можно использовать для построения базиса циклов по матрице инцидентности. Продемонстрируем это на примере. Пусть требуется найти базис циклов для графа, показанного на рисунке 8. Построим его
матрицу инцидентности и удалим из нее одну (любую) строчку (в случае несвязного графа удаляется по одной строке из каждой компоненте связности):
Строки этой матрицы – характеристические векторы элементарных разрезов, образующих базис разрезов. Так как пространство циклов является ортогональным дополнением пространства разрезов, то остается найти фундаментальную систему решений системы линейных однородных уравнений с этой матрицей (над полем из двух элементов). Для этого с помощью операций над строками преобразуем матрицу так, чтобы в первых столбцах образовалась единичная подматрица:
Удаляем первые четыре столбца, оставшуюся матрицу транспонируем и приписываем кт ней справа единичную подматрицу:
Строки полученной матрицы представляют базис циклов.
5.1. Сколько существует абстрактных эйлеровых графов с 5 вершинами?
5.2. Граф нужно превратить в эйлеров, изменяя (удаляя и добавляя) ребра. Каково
наименьшее число изменений, если разрешается а) только удалять ребра; б) только
добавлять ребра; в) и удалять, и добавлять?
5.3. Проследите работу алгоритма построения эйлерова цикла на графе . Вершины
одной доли имеют номера 1-4, другой – номера 5-8, старт в вершине1. Всякий раз,
когда имеется несколько непройденных ребер, по которым можно продолжить
движение, выбирается то из них, которое ведет в вершину с наименьшим номером.
5.4. Алгоритм построения эйлерова цикла применяется к графу . Каков будет ответ
(содержимое стека С в конце работы алгоритма)?
5. 5. Что нужно изменить в алгоритме построения эйлерова цикла, чтобы получился
алгоритм построения эйлерова пути в графе с двумя вершинами нечетной степени?
5.6. С помощью графа де Брейна найдите последовательность де Брейна 1) порядка 4 для
двухбуквенного алфавита; 2) порядка 2 для четрехбуквенного алфавита.
5.7. Сколько существует абстрактных графов с 5 вершинами, имеющих гамильтонов
5.8. В каких из следующих графов имеется гамильтонов цикл?
5.9. При каких p и q в графе имеется а) гамильтонов цикл? Б) гамильтонов путь?
5.10. При каких n существует гамильтонов цикл в графе а) ; б) ?
5.11. Постройте дерево путей для графа, изображенного на рисунке а) с корнем в
вершине 1; б) с корнем в вершине 2.
5.12. Сколько листьев будет в дереве путей для графа ?
5.13. Найдите гамильтонов путь в графе .
Найдите гамильтонов путь в турнире, заданном матрицей смежности:
5.15. Сколько в полном графе имеется подграфов, изоморфных а) ; б) ;
5.16. Операция сложения графов по модулю 2 может быть распространена на графы с
разными множествами вершин следующим образом: если ,
, то . Можно ли с помощью этой операции, а
также удаления и добавления изолированных вершин и переименования вершин
получить а) из ; б) из ; в) из ; г) из ?
5.17. Связный граф имеет 10 вершин, 4 из них имеют степень 6, остальные – степень 3.
Чему равно цикломатическое число этого графа?
5.18. Постройте фундаментальные циклы для графа относительно каркаса,
полученного с помощью а) поиска в глубину; б) поиска в ширину. Выразите границу
внешней грани как сумму базисных циклов.
5.19. Какова будет суммарная длина фундаментальных циклов, построенных с помощью
поиска в ширину для графа а) ; б) ?
5.20. Сколько различных разрезов имеется а) у связного графа с n вершинами;
б) у графа с k компонентами и n вершинами?
5.21. Найдите базис циклов по матрице инцидентности для графа, показанного на
5.22*. Модифицируйте алгоритм построения эйлерова цикла так, чтобы не требовалась
предварительная проверка четности степеней. Существование вершины нечетной
степени должно обнаруживаться по ходу работы алгоритма.
5.23*. Докажите, что при любом в графе существует гамильтонов цикл.
5.24*. Разработайте алгоритм построения дерева путей и поиска гамильтонова цикла.
5.25*. Докажите, что в любом сильно связном турнире имеется гамильтонов цикл.
5.26.* Разработайте алгоритм построения базиса циклов на основе поиска в ширину.
Сколько существует абстрактных графов с 5 вершинами имеющих гамильтонов цикл
 (1)  
 (2) 
 
 (3) 
 
 (4) 
 
 (1) если ребро 
циклически связано с ребром 
, а ребро циклически связано с ребром 
, то ребра и 
циклически связаны 
 (2) если вершина 
циклически связана с вершиной 
, а вершина циклически связана с вершиной 
, то вершины и циклически связаны 
 (3) если вершина циклически связана с ребром 
, а ребро циклически связано с вершиной , то вершины и циклически связаны 
 (4) если ребро 
циклически связано с вершиной , а вершина циклически связана с ребром , то ребра и циклически связаны 
Определение наличия эйлеровых и гамильтоновых циклов
Связный граф С называется эйлеровым, если в нем существует цикл, содержащий все ребра графа ровно по одному разу. Если граф С обладает эйлеровым циклом, то он является связным, а все его вершины — четными. Таким образом, существует очень простой критерий, позволяющий определить, является ли граф эйлеровым. Если граф С — связный и все его вершины имеют четную степень, то он имеет эйлеров цикл.
Оценка минимального числа ребер т*, удаление которых делает граф эйлеровым, в общем случае всегда производится на основе количества нечетных вершин п* по формуле
- * п * т* > —.
- (2.3)
Важно отметить, что не может возникнуть ситуации, при которой п* — число нечетное, так как суммарная степень вершин графа всегда четная, а значит, вершин с нечетными степенями всегда четное число.
Формула (2.3) дает именно нижнюю оценку, в реальности может возникнуть ситуация, когда необходимо удалить больше ребер, как, например, в задаче 2.104. Можно построить и другие графы, иллюстрирующие значительное превышение т* над п*, однако в любом случае оценкой сверху будет общее количество вершин графа, уменьшенное на единицу.
Граф (7 называется гамильтоновым, если в нем существует цикл, содержащий все вершины графа ровно по одному разу. Известны два критерия, позволяющие определить наличие гамильтонова цикла в графе. Если в простом графе с п вершинами, причем п > 3, выполняется условие 5(у) > п/2 для любой вершины у, то граф (7 является гамильтоновым. Пусть п — количество вершин в данном графе. Если для любой пары несмежных вершин (у,, уу) выполнено неравенство 5(у,) + 5(Уу) > п, то граф является гамильтоновым. Недостаток обоих критериев состоит в том, что даже если ни одно из этих условий не выполняется, граф может оказаться гамильтоновым.
Задача 2.104. Определить, является ли граф (рис. 2.20) эйлеровым, и если нет — указать с достаточным обоснованием, удаление какого минимального числа ребер делает граф эйлеровым.
Первое, что необходимо сделать, — это проверить критерий эйле-ровости, а именно четность вершин графа. Как видно из рис. 2.20, а, в графе из п = 14 вершин две имеют нечетную степень. Удобно при решении задач на рисунке заштриховать вершины, которые имеют нечетную степень. Поскольку удаление одного ребра может изменить степень двух вершин, то, если удалять попарно несмежные ребра, соединяющие только нечетные вершины, минимально возможное количество таких кандидатов на удаление будет 2/2 = 1. Нужно пробовать найти попарно несмежные ребра, соединяющие именно вершины нечетной степени. В данном случае это невозможно, поэтому, начиная с правой нечетной вершины, удаляем горизонтальные центральные ребра, пока не дойдем до левой нечетной вершины
Рис. 2.20. Этапы решения задачи 2.104: а — исходный граф; б — в графе отмечены вершины нечетной степени;
в — граф после удаления ребер
(рис. 2.20, в). Таким образом, хотя у исходного графа было только две вершины нечетной степени, для того чтобы граф стал эйлеровым, необходимо удалить пять ребер.
Задача 2.105. Является ли эйлеровым регулярный граф:
- а) степени 4 на 11 вершинах;
- б) степени 3 на 12 вершинах?
Задача 2.106. Является ли эйлеровым полный граф:
- а) на 17 вершинах;
- б) на 18 вершинах?
Задача 2.107. Какими должны быть степени всех вершин графа, чтобы в нем существовал эйлеров цикл?
Задача 2.108. Какое минимальное число ребер надо удалить из полного графа:
- а) на пяти вершинах;
- б) на четырех вершинах, чтобы он стал эйлеровым?
Задача 2.109. Является ли гамильтоновым простой цикл на 17 вершинах?
Задача 2.110. Можно ли построить гамильтонов граф с 16 ребрами на 17 вершинах?
Задача 2.111. Является ли эйлеровым регулярный граф степени 3 на 12 вершинах?
Задача 2.112. Является ли гамильтоновым полный граф:
- а) на 17 вершинах;
- б) на 18 вершинах?
Задача 2.113. В полных графах на скольких вершинах всегда есть эйлеров цикл?
Задача 2.114. В каких графах всегда существуют и эйлеров, и гамильтонов циклы и они совпадают?
Задача 2.115. Какой цикл (никакой, гамильтонов, эйлеров или оба) всегда есть:
- а) в полном графе на семи вершинах;
- б) в полном графе на 10 вершинах;
- в) в регулярном графе степени 3 на семи вершинах?
Задача 2.116. Какой цикл (никакой, гамильтонов, эйлеров или оба) всегда есть в полном двудольном графе:
- а) К71;
- б) к3,7;
- в) К2 9;
- Г) *8,8?
Задача 2.117. Пусть G — связный граф, в котором есть точно две вершины нечетной степени. Имеет ли он эйлеров цикл? Имеет ли он эйлерову цепь? Обоснуйте ответ.
Задача 2.118. Сколько гамильтоновых циклов существует в полном графе на 2, 3, 4 вершинах? Попробуйте сформулировать ответ на общий вопрос: сколько гамильтоновых циклов существует в полном графе на п вершинах?
Задача 2.119. Построить не эйлеров, но гамильтонов граф на восьми вершинах, число базисных циклов которого равно шести, про вершины которого известно, что две вершины имеют степень 4, а степени остальных вершин одинаковы, или дать обоснованный ответ о невозможности построения такого графа.
Задача 2.120. Построить граф, являющийся одновременно эйлеровым и гамильтоновым, у которого ребер в два раза больше, чем вершин, а цикломатическое число равно шести, или дать обоснованный ответ о невозможности построения такого графа.
Задача 2.121. Построить граф, не являющийся ни эйлеровым, ни гамильтоновым, у которого ребер на одно больше, чем вершин, а цикломатическое число равно двум, или дать обоснованный ответ о невозможности построения такого графа.
Задача 2.122. Построить эйлеров, но не гамильтонов граф на 11 вершинах, число базисных циклов которого равно шести, про вершины которого известно, что восемь вершин имеют степень 2 и две вершины — степень 4, или дать обоснованный ответ о невозможности построения такого графа.
Задача 2.123. Для заданного графа (рис. 2.21) определить с достаточным обоснованием:
- а) является ли граф гамильтоновым, и если да — указать гамильтонов цикл;
- б) является ли граф эйлеровым, и если да — указать эйлеров цикл; если нет — указать с достаточным обоснованием минимальное количество и название ребер, удаление которых делает граф эйлеровым.
Задача 2.124. Для заданного графа (рис. 2.22) определить с достаточным обоснованием:
- а) является ли граф гамильтоновым, и если да — указать гамильтонов цикл;
- б) является ли граф эйлеровым, и если да — указать эйлеров цикл; если нет — указать с достаточным обоснованием минимальное количество и название ребер, удаление которых делает граф эйлеровым.
Рис. 2.22. Условие задачи 2.124
Задача 2.125. Проверить, существует ли среди связных графов, имеющих 11 вершин, причем расстояние между любыми двумя несмежными вершинами равно двум, эйлеров, но не гамильтонов граф и гамильтонов, но не эйлеров граф. Если да — построить его (их), если нет — дать обоснование его (их) отсутствия.
Задача 2.126. Проверить, существует ли среди связных графов, имеющих десять вершин и 15 ребер, эйлеров граф. Если да — построить его, если нет — дать обоснование его отсутствия.
Задача 2.127. Проверить, существует ли гамильтонов граф среди связных графов на 21 вершине с 37 ребрами, причем 15 вершин имеют степень 4, четыре вершины — степень 3. Если да — построить его, если нет — дать обоснование его отсутствия.
Задача 2.128. Проверить, существует ли эйлеров граф среди связных графов на 15 вершинах с 26 ребрами, причем шесть вершин имеют степень 6, семь вершин — степень 2. Если да — построить его, если нет — дать обоснование его отсутствия.
Задача 2.129. Проверить, существует ли среди графов, полученных удалением произвольных 23 ребер из полного двудольного графа Кхз ід, эйлеров граф. Ответ обосновать.
Задача 2.130. Проверить, существует ли среди связных графов, имеющих шесть вершин и десять ребер, эйлеров граф. Если да, то привести его. Если нет — обосновать ответ.
Задача 2.131. Проверить, существует, ли среди связных графов, имеющих 47 ребер и 25 вершин, из которых 21 вершина имеет степень 4, а три — степень 3, гамильтонов граф. Если да, то указать его.
Задача 2.132. Проверить, существует ли среди связных графов, имеющих шесть вершин и девять ребер, эйлеров граф. Если существует, указать его. В противном случае дать обоснование его отсутствия.
05. Гамильтонов цикл и гамильтонов граф. Условия Дирака, Оре и Поша, гарантирующие существование в графе гамильтонова цикла
Пусть — некоторый граф. Он называется Гамильтоновым, если в нем сущест-вует простой цикл, содержащий все вершины графа. Например, каждый полный граф – гамиль-тонов, потому что в нем проведены всевозможные ребра и, в частности, те, благодаря которым возможен обход по всем вершинам. А вот пример графа, не являющегося гамильтоновым:
Общих и легко осуществляемых действий, с помощью которых можно было бы достоверно выяснить, является ли данный граф гамильтоновым, не существует. Однако, имеются доста-точные условия на гамильтоновость, которые проверятются легко. Недостаток здесь состоит в том, что даже если ни одно из этих условий не выполняется, граф может оказаться гамильто-новым. В дальнейшем в этой лекции будет молчаливо предполагаться, что число вершин в лю-бом рассматриваемом графе не меньше трех.
Итак, условие первое — Условие Дирака. Пусть — число вершин в данном графе; если степень каждой вершины не меньше, чем , то граф называется Графом Дирака. Можно дока-зать, что Каждый граф Дирака обязательно гамильтонов.
Вот пример графа Дирака:
Очевидно, этот граф — гамильтонов. А вот пример гамильтонова графа, не являющегося графом Дирака:
Условие второе — Условие Оре. По-прежнему будем обозначать через количество вер-шин в данном графе. Если для любой пары несмежных вершин выполнено неравенство , то граф называвается Графом Оре (словами: степени любых двух несмежных вершин не меньше общего числа вершин в графе). Можно доказать, что Всякий граф Оре обяза-тельно гамильтонов.
Вот пример графа Оре:
А вот пример графа, не являющегося графом Оре и, тем не менее, графа гамильтонова:
Нетрудно заметить, что всякий граф Дирака автоматически является графом Оре. Но вот пример графа Оре, не являющегося графом Дирака:
Условие третье — Условие Поша. Это — более сложная конструкция. Введем следующую функцию целого неотрицательного аргумента . Сначала запишем определение формулой, а затем прокомментируем его. Итак, речь идет по-прежнему о графе ,
Для которого и строится функция :
Написанное означает, что функция в каждом целом неотрицательном принимает значение, равное количеству вершин графа , степень которых не превосходит . Такую функцию называют Функцией Поша графа .