Теория графов

Из связности и ацикличности подграфа H₁ следует, что H₁ - остов-ное дерево.

Лемма 4. Пусть S и Т - остовы графа G. Для любого ребра е из S существует такое ребро f из Т, что подграф S - e + f является остовом.

Доказательство. Как и выше, достаточно рассмотреть случай, когда G - связный граф. Подграф S - е имеет две компоненты связности; обозначим через U и W множества вершин этих компонент. Поскольку остов Т является связным графом, существует ребро f из Т, соединяющее вершины, одна из которых принадлежит U, а другая - W. Легко понять, что подграф S-e+f ацикличен и связен. Следовательно, S-e+f является остовом.

граф математический матрица ациклический

6. Обходы графов

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

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

Свое название эйлеровы графы получили в честь Л. Эйлера, который первым рассмотрел такие графы в 1736 году в своей знаменитой работе о кенигсбергских мостах. Этой работой Эйлер, по существу, положил начало новому разделу математики - теории графов.

Задача о кенигсбергских мостах состояла в следующем. На реке Пре-гель в Кенигсберге было два острова, соединенных между собой и с берегами семью мостами, как показано на рис. 13 а)

Рисунок 13

Спрашивается, можно ли, начиная с некоторого места суши, обойти все мосты по одному разу и вернуться назад?

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

Теорема 3.1 (Эйлер, 1736). Для неодноэлементного связного графа G следующие условия эквивалентны:

1) G - эйлеров граф

2) каждая вершина графа G имеет четную степень;

3) множество всех ребер графа G можно разбить на циклы.

Доказательство. 1) => - 2). Пусть Р - эйлерова цепь графа G с начальной вершиной v₀. Двигаясь по цепи Р, будем подсчитывать степени вершин. Прохождение каждой промежуточной вершины в цепи Р вносит число 2 в ее степень. Первое и последнее ребро цепи Р дают вклад 2 в степень вершины v_о - Так как цепь Р содержит каждое ребро графа точно один раз, отсюда следует четность степеней всех вершин графа G.

2) > 3). Граф G связен и не имеет висячих вершин, поскольку степень каждой его вершины четна. В силу следствия 1 из теоремы 2.1 в G содержится некоторый цикл. Обозначим через G₁ максимальный подграф графа G, удовлетворяющий условию 3). Поскольку из условия 3) вытекает условие 2), степени всех вершин графа G₁ четны. Обозначим через G₂ подграф, полученный из G удалением всех ребер графа G₁. Предположим, что G₂ содержит неодноэлементную компоненту связности Н. Поскольку Н - связный подграф, удовлетворяющий условию 2), в нем нет висячих вершин, и, следовательно, Н - не дерево, т.е. в H содержится цикл С. Если добавить все ребра цикла С вместе с инцидентными им вершинами к подграфу G₁, то получится подграф, содержащий G₁и удовлетворяющий условию 3), что невозможно. Следовательно, подграф G₂ не содержит ребер, поэтому G совпадает с G₁.

3) > 1). Разобьем множество всех ребер графа G на наименьшее число замкнутых цепей P₁, Р₂,…, Р₈ (такое разбиение существует в силу условия 3)) и докажем, что s = 1. Пусть s > 1. В силу связностиграфа G найдется такое

i ?2, что замкнутые цепи P₁ и Pi имеют общую вершину. Поскольку P₁ и Pi не имеют общих ребер, их можно объединить в одну замкнутую цепь, уменьшив, тем самым общее количествоцепей s, что невозможно. Следовательно, все ребра графа G принадлежат некоторой замкнутой цепи, т.е. граф является эйлеровым.

Из теоремы 3.1 можно получить следствие, относящееся к произвольным графам.

Следствие 1. Пусть G - произвольный граф, содержащий 2l вершин нечетной степени, где l ? 1. Тогда множество всех ребер графа можно разбить на l цепей, каждая из которых соединяет две вершины нечетной степени.

Доказательство. Очевидно, утверждение достаточно доказать для случая, когда граф G связен. Пусть

- все вершины нечетной степени связного графа G. Рассмотрим граф G₁, полученный из G добавлением l новых ребер e_i,…, е_l таких, что ei = u_2i_₁u_2i (1 ? i ? l). Граф G₁, очевидно, связен и степень каждой его вершины - четное число. Поэтому в G₁ существует эйлерова цепь Р.

Можно считать, что цепь Р начинается с ребра е₁. Удаляя из Р все ребра e_i (1 ? i ? l), мы, очевидно, получим l нужных нам цепей.

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

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

Это утверждение, очевидно, вытекает из теоремы 3.1 и следствия 1. Следующее утверждение уточняет предложение 3.1.

Следствие 2. Пусть связный граф G содержит две вершины нечетной степени u u v. Тогда существует (u, v) - цепъ, содержащая все ребра графа G.

Граф называется произвольно вычерчиваемым из вершины v, если любая его цепь с началом в вершине v может быть продолжена до эйлеровой цепи графа G. Разумеется, если граф произвольно вычерчиваем из вершины v, то он является эйлеровым графом.

Теорема 3.2. Неодноэлементный эйлеров граф G является произвольно вычерчиваемым из вершины v тогда и только тогда, когда вершина v принадлежит любому циклу графа G.

Доказательство. Пусть вершина v эйлерова графа G принадлежит любому циклу. Рассмотрим произвольную (v, w) - цепь Р и покажем, что ее можно продолжить до эйлеровой цепи. Обозначим через G₁ подграф графа G, полученный удалением из G всех ребер цепи Р. Если w = v, то все вершины подграфа G₁ имеют четную степень, если же w ? v, то G₁ содержит в точности две вершины нечетной степени. Пусть Н₀ - компонента связности графа G₁, содержащая вершину v. Ясно, что вершина w принадлежит h₀. Следовательно, Н₀ - полуэйлеров граф, и потому в Н₀ существует полуэйлерова (w, v) - цепь Q. Нетрудно понять, что H₀ содержит все ребра графа G₁. В самом деле, предположим, что G₁ содержит неодноэлементную компоненту связности Н, отличную от Н₀. Тогда Н - эйлеров граф, и потому в Н содержится цикл. Этот цикл, очевидно, не проходит через вершину v, что невозможно. Следовательно, все компоненты связности подграфа G₁, отличные от Н₀, одноэлементны.

Таким образом, цепь Q содержит все ребра графа G₁. Отсюда вытекает, что объединение цепей Р uQ - эйлерова цепь в графе G, являющаяся продолжением цепи Р.

Обратно, пусть в графе G существует цикл C, не содержащий вершину v. Рассмотрим подграф G₁, полученный удалением из G всех ребер цикла С. Пусть H - компонента связности подграфа G₁, содержащая вершину v. Легко понять, что H - эйлеров граф. Обозначим через Р эйлерову цепь подграфа Я. Можно считать, что началом и концом цепи Р является вершина v. Поскольку v не принадлежит циклу G, цепь Р нельзя продолжить до эйлеровой цепи графа G.

Опираясь на теорему 3.2, несложно описать строение всех графов, произвольно вычерчиваемых из вершины v.

Для этого возьмем произвольный лес H, т.е. ациклический граф, не содержащий вершину v. Каждую вершину нечетной степени из H соединим некоторым нечетным числом кратных ребер с v, а каждую вершину четной степени - четным числом (не исключая 0) кратных ребер с v, причем каждую изолированную вершину из Я обязательно соединим с v (см. рис. 14). Кроме того, в вершине v можно присоединить несколько петель.

Полученный граф G

1) связен;

2) имеет только вершины четной степени (deg v четно, так как в графе H содержится четное число вершин нечетной степени);

3) является произвольно вычерчиваемым из вершины v, (как эйлеров граф, у которого вершина v принадлежит всем циклам)

Рисунок 14

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

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

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

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

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

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

Указанные названия цепей и циклов связаны с именем Уильяма Гамильтона, который в 1859 году предложил следующую игру-головоломку:

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

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

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

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

(Задача о шахматном коне.) Можно ли, начиная с произвольного поля шахматной доски, обойти конем последовательно все 64 поля по одному разу и вернуться в исходное поле?

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

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

Сначала дадим необходимые определения и докажем одну вспомогательную лемму.

Пусть граф G имеет п вершин v₁, v₂,…, v_n. Положим d_i = deg v_i

(i = 1, 2,…, n) и будем считать, что вершины графа упорядочены таким образом, что d₁ ? d₂ ?… ? d_n. Последовательность d₁, d_2:…, d_n называют последовательностью степеней графа G.

Будем говорить, что числовая последовательность , если для любого i = 1,2,…, n

Лемма 1. Пусть обыкновенный граф G' получен из обыкновенного графа G добавлением одного нового ребра е. Тогда последовательность степеней графа G мажорируется последовательностью степеней графа G'.

Доказательство. Заметим сначала, что если в неубывающей последовательности d₁ ? d₂ ?… ? d_n увеличить число d_i на 1, а затем полученную последовательность привести к неубывающему виду, переставив число d_i + 1 на положенное место, то новая последовательность будет мажорировать исходную последовательность (очевидно, ту же новую последовательность можно получить сразу, добавив 1 к последнему числу исходной последовательности, равному d_i).

Ясно, что при добавлении к графу нового ребра е = uv, где u ? v, точно у двух вершин u и v степени увеличатся на 1. Осталось два раза воспользоваться сделанным замечанием.

Теорема 3.3 (Хватал, 1972). Пусть G - обыкновенный граф,

d₁ ? d₂ ?… ? d_n - его последовательность степеней u n ? 3. Если для любого k верна импликация

d_k ? k < n/2 - d_n__k ? n - к, (*)

то граф G гамильтонов.

Доказательство. Сделаем сначала три очевидных замечания.

1) Если d_k ? k, то число вершин, степень которых не превосходит k, больше или равно k. Очевидно, верно и обратное утверждение.

2) Если d_n__k ?n - k, то число вершин, степень которых не меньше n - k, больше или равно k + 1 (достаточно заметить, что в последовательности

d_n-_k, d_n-_k+1,…, d_n имеется k + 1 чисел). Конечно, и здесь верно обратное утверждение.

3) Если условие (*) верно для некоторой последовательности степеней, то оно верно и для мажорирующей её последовательности.

Пусть теперь, от противного, существует обыкновенный n-граф, где

n ? 3, который удовлетворяет условию (*), но не является гамильтоновым графом. Будем добавлять к нему новые ребра до тех пор, пока не получим максимальный негамильтонов обыкновенный граф G. В силу 3) граф G удовлетворяет условию (*).

Заметим, что граф К_n гамильтонов при n> 3. Будем считать, что граф G - это максимальный негамильтонов остовный подграф графа К_n.

Возьмем две такие несмежные вершины u и v графа G, что сумма

deg u + deg v является наибольшей из возможных. Без ограничения общности будем считать, что deg u < degv. Добавим к G новое ребро е = uv. Тогда граф G + e гамильтонов.

Рассмотрим гамильтонов цикл графа G + e. В нем обязательно присутствует ребро e= uv. Отбрасывая ребро е из цикла, получим гамильтонову (u, v) - цепь в графе G

u = u₁, u₂,…, u_п = V.

Положим

Покажем, что S?T = Ш. Действительно, если j € S?Т, то в графе G имеется гамильтонов цикл:

Из определения S и Т следует S U Т С {1, 2,…, n - 1}, поэтому 2degu ? degu + degv = \S\ + |T| = \SUT\ < n, т.е. degu < n/2.

Так как S?Т = Ш, ни одна вершина u_j, где j € S, не смежна с v = u_n. Отсюда в силу выбора u и v имеем degu_j < degu. Положим k - deg u. Тогда имеется по крайней мере |S| = deg u = k вершин, степень которых не превосходит k. В силу 1) выполняется

d_k ?k < n/2.

По условию (*) получаем

d_n-k ?п - к.

В силу 2) имеется по крайней мере k + 1 вершин, степень которых не меньше n - n.

Вершина и может быть смежна, самое большее, с k из этих k + 1 вершин, так как k = deg u. Следовательно, существует вершина w, не смежная с u, для которой deg w? n - k. Тогда получаем deg u+ deg u?k + (n - k) = n> deg u + deg v, что противоречит выбору u и v.

Следствие 1. Пусть G - обыкновенный граф, d₁ ? d₂ ?… ? d_n - его последовательность степеней и n ? 3. Граф G гамильтонов, если выполнено одно из условий:

1) d_k. ? n/2 для любого k = 1,…, n (теорема Дирака, 1952),

2) deg u + deg v ? n для любых двух различных несмежных вершин u, v графа G (теорема Оре, 1960),

3) d_k > k для любого натурального числа k такого, что 1 ? k < n/2.

Доказательство. Достаточно установить, что 1) > 2) > 3) > (*). Импликации 1) > 2) и 3) > (*) совершенно очевидны.

2) > 3). Пусть, от противного, верно 2), но не верно 3). Тогда существует такое t, что 1 ? t < n/2 и d_t ? t. Возьмем произвольные числа t₁, t₂ такие, что 1 ? t₁ < t₂ ? t. Тогда d_tl, d_t2 < d_t < t < п/2 влечет d_tl + d_t2 < n, откуда в силу 2) вершины v_tl, v_t2 смежны. Таким образом, вершины г>1, v₂,…, v_t порождают полный подграф.

Так как d_t ? t, любая вершина v_i для i = 1,…, t смежна не более чем с одной вершиной v_j для j € t + 1,…, n, причем |{t + 1,…, n}| = n - t. Заметим, что n - t > t, поскольку t < п/2. Поэтому существует вершина v_j для некоторого j = t + 1,…, n, которая несмежна с вершинами v₁,…, v_t. Поскольку v_j несмежна сама с собой, отсюда следует

d_j ? п - t - 1.

Тогда d_t + dj ?t + n - t - 1 < n и вершины v_t, v_t несмежны и различны, что противоречит 2).

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

О гамильтоновых орграфах в целом известно не очень много. Приведем без доказательства аналог теоремы Дирака

Теорема 3.4 (Гуйя-Ури). Пусть G - орсвязный п-орграф. Если

для любой его вершины v, mo G - гамильтонов орграф.

граф математический матрица ациклический

Рассмотрим теперь один важный класс орграфов и выясним, когда орграф из этого класса будет гамильтоновым.

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

Размещено на Allbest.ru