Фундаментальные циклы и разрезы

Пусть Т – остов графа и К – соответствующий ему ко-лес.

Если добавить к Т любую хорду hÎК, то получим единственный цикл, который называется фундаментальным циклом относительно хорды h. Понятно, что все циклы, получаемые таким способом, т.е. путем добавления к Т различных хорд из К, попарно различны и их число равно числу хорд в К, и равно g(G). Множество всех фундаментальных циклов относительно хорд К называется фундаментальной системой циклов относительно остова Т.

На рисунке 30 (а) и (б) изображен граф и его остов, а на рисунке 30 (в) – фундаментальная система циклов относительно этого остова.

Если удалить из Т любую ветвь b, то одна из компонент Т разобьется на две новые компоненты, каждая из которых является деревом. Обозначим множества вершин новых компонент V₁ и V₂. Заметим теперь, что хорды из К, соединяющие вершины из V₁ и V₂, в совокупности с ветвью b образуют разрез графа G. Этот разрез называется фундаментальным разрезом относительно ветви b остова Т. Множество всех разрезов, полученных таким способом, т.е. удалением по отдельности каждой ветви из Т, называется фундаментальной системой разрезов относительно остова Т. Очевидно, что все разрезы в этом множестве попарно различны и их число совпадает с числом ветвей в Т и равно (в‑k).

На рисунке 31 изображены фундаментальные разрезы графа, изображенного на рис.30(а), относительно его остова на рис.30(б). Рис. 31(а) – фундаментальный разрез относительно ветви (1,5); рис. 31(б) – ф.р. относительно ветви (2,5); рис. 31(в) – ф.р. относительно ветви (3,5) и рис. 31(г) – ф.р. относительно ветви (4,5).

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

Специальные графы

Граф называется r‑валентным или r‑однородным, если любая его вершина имеет степень, равную r.

Например, цикл является 2-валентным графом. На рисунке 32 (а) изображен 3-валентный граф Петерсона, графы Платоновых тел: (б)–куба, (в)‑тетраэдра, (г)–додекаэдра, (д)–4-валентный граф октаэдра и (е)–5-валентный граф икосаэдра.

Любой полный граф К_n, где n – число вершин, является (n‑1)‑регулярным.

Граф G=(V, E) называется двудольным, если множество его вершин V можно разбить на два непересекающихся подмножества V₁ и V₂, что каждое ребро графа имеет одну концевую вершину в V₁, а вторую в V₂. См. рис.33 слева. При этом не обязательно, чтобы каждая пара вершин из V₁ и V₂ была соединена ребром. Если же это так, то граф называется полным двудольным графом и обозначается обычно K_m,n, где m и n – число вершин в V₁ и V₂ соответственно. См. рис.33 справа.

В полном двудольном графе число вершин равно m+n, а число ребер m×n. Полный двудольный граф вида K_1,n называется звездным.

Граф G=(V, E) называется k‑дольным, если множество его вершин V можно разбить на k попарно непересекающихся подмножеств V₁, V₂,¼, V_k, что любое ребро имеет одну концевую вершину в V_i, а вторую в V_j, где i¹j. Полным k‑дольным графом называется такой k‑дольный граф, что любая вершина V_i смежна с любой вершиной из V_j, где i¹j и i, j=1,2,¼,k.

Объединение звездного графа K_1,n‑1 и цикла C_n‑1 называется колесом и обозначается W_n.

Эйлеровы графы

Знаменитая задача Эйлера о Кёнигсбергских мостах, сформулированная на языке графов в 1736 г., дала начало математической теории графов. Это игровая задача, суть которой заключается в следующем: в городе Кёнигсберге на реке Преголя имеется два острова, которые соединяются между собой и берегами семью мостами, как показано на рис.34. Прогуливаясь по городу и начиная движение из любой точки, требуется пройти по каждому мосту ровно по одному разу и вернуться в исходную точку.

Сопоставим каждому участку суши вершину графа, а каждому мосту – ребро. Тогда «план города» будет выглядеть так, как показано на рис.35. И задачу можно теперь переформулировать для графов: найти в связном графе такую замкнутую цепь, которая проходит через каждое его ребро или, как говорят, покрывает все ребра графа. Такая цепь называется эйлеровой цепью или эйлеровым циклом, а графы, в которых такая цепь существует, называются эйлеровыми графами. Очевидно, что граф, изображенный на рис.35, эйлеровым не является. Граф на рисунке 36 – эйлеров, и соответствующая эйлерова цепь – это последовательность ребер (1,2,¼,12).

Граф называется полуэйлеровым, если в нем существует открытая эйлерова цепь, т.е. цепь, покрывающая все ребра графа, у которой начальная и конечная вершины не совпадают. И, наконец, граф называется неэйлеровым, если в нем не существует ни открытой, ни замкнутой эйлеровой цепи. На рис.37 (слева) – полуэйлеров граф, на рис.37 (справа) – неэйлеров граф.

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

Следствие 1: семейство ребер эйлерова графа можно разбить на непересекающиеся по ребрам циклы.

Следствие 2: каждая вершина эйлерова графа содержится хотя бы в одном цикле.

В любом связном графе с 2k нечетными вершинами имеется семейство из k цепей (не пересекающихся по ребрам), которые в совокупности покрывают все ребра графа.

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

Рассмотрим алгоритм Флёри построения эйлеровой цепи в эйлеровом графе.

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

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

В 1859г. ирландский математик сэр Уильям Гамильтон придумал игру–головоломку. Основой её был правильный додекаэдр, сделанный из дерева. Каждая вершина этого додекаэдра была помечена названием одного из крупных городов (Брюссель, Франкфурт, Дели и т.д.). Задача состояла в нахождении пути вдоль ребер додекаэдра, проходящего через каждый город в точности по одному разу.

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

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

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

(Дирака) Если в простом графе с n вершинами (n³3) степень любой вершины больше, либо равна n/2, то граф является гамильтоновым.

Если в простом графе с n вершинами (n³3) для любой пары несмежных вершин v_i, v_j выполняется условие deg(v_i)+deg(v_j)³n, то граф является гамильтоновым. (Если deg(v_i)+deg(v_j)³n‑1, то граф – полугамильтонов.)

Классическим примером задачи поиска гамильтоновых циклов является известная задача о коммивояжере (странствующем торговце). Коммивояжеру необходимо посетить несколько городов, расстояния между которыми известны. Нужно найти кратчайшую дорогу, проходящую через все пункты и возвращающуюся в исходный пункт. Здесь каждому городу сопоставим вершину графа, дороге между городами – ребро. Ребру приписываем заданное расстояние, которое, очевидно, можно рассматривать как функцию двух вершин f(v_i,v_j). Если вершины v_i,v_j несмежны, то f(v_i,v_j)=¥. Таким образом, длина гамильтонова цикла L= . Найти цикл, для которого L минимальна. Не известно до сих пор никакого эффективного алгоритма для решения этой задачи. Для конечного случая её можно решить простым перебором. Отметим, что для полного графа на n вершинах существует гамильтоновых циклов, т.е. сложность задачи очень быстро возрастает с ростом числа вершин.