Материал: Дискретная математика. учебное пособие. Горбунов В.В., Лапшина М.Л

5.12. Гамильтоновы графы

Гамильтоновой цепью называется простая цепь, приходящий через каждую вершину графа ровно один раз.

Гамильтоновым циклом (англ. Hamiltonian cycle) называется замкнутая гамильтонова цепь.

Граф называется гамильтоновым (англ. Hamiltonian graph), если он содержит гамильтонов цикл.

Граф называется полугамильтоновым (англ. Semihamiltonian graph), если он содержит гамильтонову цепь.

В графе, изображенном на рис. 31 слева, гамильтоновым циклом является, например, последовательность 1, 2, 3, 5, 4, 1. В графе, изображенном в центре, нет гамильтоновых циклов, но есть гамильтоновы цепи, например, 2,5,3,1,4. В правом графе нет и гамильтоновых цепей.

Гамильтоновы графы применяются для моделирования многих практических задач, например, служат моделью при составлении расписания движения поездов. Основой всех таких задач служит классическая задача коммивояжера: коммивояжер должен совершить поездку по городам и вернуться обратно, побывав в каждом городе ровно один раз, сведя при этом затраты на передвижения к минимуму.

В отличие от поиска эйлеровых циклов, проходящих через каждое ребро графа по одному разу, для которых еще Эйлером получено необходимое и достаточное условие существования цикла, для гамильтоновых циклов такого условия не найдено. Для гамильтоновых циклов и путей неизвестно никаких просто проверяемых необходимых и достаточных условий их существования, а все известные алгоритмы требуют для некоторых графов перебора большого числа вариантов.

Достаточные условия гамильтоновости графа формулируются в виде терем.

Теорема Дирака. Простой граф порядка n≥3 гамильтонов, если степень любой его вершины удовлетворяет неравенству

.

Граф, удовлетворяющий неравенству, называется графом Дирака. Каждый граф Дирака обязательно гамильтонов. Однако, встречаются гамильтоновы графы, не являющиеся графами Дирака. Граф на Рис. 32 будучи гамильтоновым, не является графом Дирака.

Известно, что каждый полный граф – гамильтонов, потому что в нем проведены все возможные ребра, благодаря чему возможен обход по всем вершинам.

Теорема Оре. Граф (n≥3) гамильтонов, если степени любых двух его несмежных вершин и удовлетворяют неравенству

_.

Граф с выполненным условием теоремы, называется графом Оре. Переформулировав теорему Оре, можно сказать, что если степени любых двух несмежных вершин не меньше общего числа вершин в графе, то граф обязательно является графом Оре. Каждый граф Оре – гамильтонов граф, но обратное утверждение не верно.

На рис. 33 приведен пример графа Оре.

Для ориентированных графов также имеется достаточное условие гамильтоновости.

Теорема Гуйя-Ури. Связный орграф обладает гамильтоновым циклом, если для любой его вершины v_i выполняется условие:

, .

В качестве метода построения гамильтоновой цепи рассмотрим метод последовательного перебора. В ходе выполнения алгоритма строится отрезок пути, который хранится в стеке PATH. На каждом шаге путь наращивается дугой, связывающей последнюю вершину со смежной, не включенной в цепь, до тех пор, пока не будет обнаружена гамильтонова цепь или все возможные пути не будут исследованы.

Пример 5.6. Построить гамильтонов цикл для орграфа, изображенного на рис. 34.

Для графа G можно описать окрестность Г каждой вершины: В качестве исходной выбираем вершину а, поэтому в начале стек PATH={a}. Фиксируем вершину a в первой позиции. Единственной доступной из вершины a является вершина b, поэтому включаем ее в стек PATH=

Наращиваем цепь из вершины b. Множество Г(b)={c,e} позволяет присоединить одну из дуг (b,с), (b,e). Выбираем вершину c. Образуется PATH Поскольку то на третьем шаге можем присоединить только вершину d, так как вершина уже принадлежит PATH. В _{результате PATH={a,b,c,d}. На четвертом шаге добавляем вершину f и имеем PATH={a,b,c,d,f}. Дальнейшее наращивание становится невозможным, так как все вершины в текущем множестве Г уже содержатся в стеке PATH.}

_{Возвращаемся к вершине d и анализируем ее множество} Вершина f уже была включена с отрицательным результатом, поэтому возвращаемся на шаг ранее к вершине c, а потом и к b. Множество содержит еще не прозондированную вершину e. Получаем PATH Множество позволяет выбрать c PATH _{Г(е) позволяет выбрать с PATH={a,b,е,c}. Еще две итерации позволяют построить PATH={a,b,е,c,d,f}. Поскольку в графе есть дуга (f,a), получаем гамильтонов цикл. Выполненные действия алгоритма наглядно представляются таблицей.}

_{Таблица 30}

5.13. Деревья

Деревом называется связный граф без контуров (ациклический граф). Несвязный граф, состоящий из нескольких деревьев называют лесом. В графе без циклов каждая компонента связности является деревом.

Вершины степени 1 в дереве называются листьями или висячими вершинами. Ребро, инцидентное концевой вершине, будем называть концевым ребром графа.

Среди различных деревьев выделяют два простых частных случая: последовательное дерево, представляющее собой простую цепь, и звездное дерево (или куст), в котором одна из вершин (центр) смежна со всеми остальными вершинами.

Среди графов n-го порядка (с n вершинами) без кратных ребер полный граф имеет наибольшее количество ребер, а дерево (n-го порядка) - наименьшее. Дерево содержит минимальное количество ребер, необходимое для того, чтобы граф был связным.

Теорема 1. Если граф G является деревом, то число его ребер m и число его вершин n связаны соотношением .

Теорема 2. При удалении любого ребра дерева оно распадается на связные компоненты, являющиеся либо изолированными вершинами, либо деревьями.

Теорема 3. Любые две вершины в графе могут быть связаны (простым) путем, и этот путь единствен.

При добавлении в дерево любого нового ребра в нем образуется простой цикл, и оно перестает быть деревом.

Деревья имеют особое положение в теории графов из-за предельной простоты строения, и часто при решении какой-либо задачи на графах ее сначала исследуют на деревьях.

Генеалогическое дерево, в котором смежные вершины – это люди, связанные родством: мать и ее ребенок или отец и его ребенок, деревом в смысле теории графов не является, так как оно обязательно должно содержать циклы: некоторые предки данного человека должны иметь общего предка.

Игры с полной информацией (т. е. игры, не имеющие вероятностного характера: шахматы, шашки, уголки и т. д. ) могут быть изображены в виде дерева.

Возможности выбора при решении проблемы можно представить в виде ориентированного дерева, где в корне (выделенной вершине) – проблема, дуге соответствует один из вариантов выбора, вершине - новая ситуация, возникающая в результате реализации приписанного дуге варианта. Такой трактовке соответствует граф типа дерева, получивший название дерево решений. Предположим, что можно оценить эффективность принятого выбора. Тогда возникает задача поиска среди возможных путей от корня (когда проблема поставлена) к одному из листьев (когда проблема решена) пути, имеющего оптимальную оценку.

Центр дерева — множество вершин графа, для которых эксцентриситет вершины минимален, т.е равен радиусу графа, может состоять из одной или из двух смежных вершин.

Центр дерева можно найти следующим образом. Если в дереве больше двух вершин, удаляются все его листья. С полученным деревом поступаем так же, это продолжается, пока не останется дерево из одной или двух вершин. Эти вершины и образуют центр исходного дерева.

Пример 5.7. Найти центр, диаметр и радиус графа, изображенного на рис. 35

Сначала удаляются листья-вершины v₁, v₃, v₇, v₈, являющиеся вершинами первого типа. Потом удаляются вновь образованные листья v₂, v₆ – вершины второго типа. Центром дерева являются вершины v₄, v₅. Диаметр графа равен 5, а радиус равен 3.