Восстановление пути от s до t:

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

BFS – поиск в ширину находит путь кратчайшей длины в невзвешенном графе; одинаково работает на ориентированных и неориентированных графах; работает за O(N+M).

DFS – поиск в глубину находит лексикографически первый путь в графе; работает за O(N+M).

Нахождение компонент связности можно проверить с помощью любого обхода: запуская алгоритм от каждой вершины и смотря на массив used можно узнать к какой компоненте связности принадлежит граф: вершины, принадлежащие этой компоненте, будут посещены, то есть used[v]=true. Для вершин в других компонентах связности used[v]=false.

Узнать кратчайшие пути от вершины s до каждой другой можно с помощью обхода в ширину и массива предков – p[v]=u означает, что в v попали через u. Таким образом, находим вершины в обратном порядке от конечной вершины до вершины s.

Проверка на двудольность: нужен дополнительный массив part, в котором каждой вершине будет сопоставляться номер ее доли (1 или 2). Если пытаемся из вершины v пойти в вершину, которая имеет ту же долю, что и v, то граф не двудольный.

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

Построение стягивающего дерева: Для произвольного неориентирован­ного графа G = <V, Е> каждое дерево <V, Т>, где Т ∈ Е, будем назы­вать стягивающим деревом или каркасом графа G. Нужно, чтобы все вершины были в этом дереве, значит каждую не посещённую вершину нужно обязательно добавить инцидентное ей ребро.

Топологическая сортировка:

• порядок вершин, при котором каждая дуга ведет из вершины, которая была раньше в порядке, в вершину, которая позже

• существует, если граф ацикличен

• алгоритм:

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

  2. перепишем ответ в обратном порядке

10. Понятие дерева. Свойства деревьев.

Дерево – простой связный граф без циклов. Простой (не обязательно связный) граф без циклов называется лесом.

Вершина дерева, имеющая степень 1, называется листом.

Лемма. У любого дерева, построенного на n≥2 вершинах, имеется как минимум 2 листа.

Доказательство. Рассмотрим произвольный простой путь Р = (х1,х2,..., хк) максимальной длины. Его концы – листья. Предположим, что один из концов (пусть хк) – не лист. Тогда он либо связан с еще одной вершиной хк-1, что противоречит условию максимального пути х1-хк, либо связан с вершиной хi (i<k), но тогда получается цикл, что противоречит условию дерева.

Теорема. В дереве, построенном на n вершинах, имеется ровно n-1 ребро.

Доказательство по индукции.

Обратная теорема. Любой простой связный граф, построенный на n вершинах и имеющий n-1 ребро, является деревом.

Доказательство от противного. Существует цикл С. Любое ребро е, принадлежащее циклу С, мостом в графе G не является. Удаляем по очереди ребра из циклов, пока они есть, получаем простой связный граф без циклов, то есть дерево. По предыдущей теореме у него n-1 вершина.

Следствие. Всякий связный граф, построенный на n вершинах, имеет как минимум n-1 ребро.

По-другому это означает, что у всякого связного графа существует остовное дерево.

• Связный граф является деревом тогда и только тогда, когда любое его ребро является мостом.

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

•Следствие. Пусть T есть остовное дерево связного графа G, и пусть e – ребро, не принадлежащее T. Тогда граф T+e содержит единственный цикл, который проходит через e.

Корневым деревом называется дерево с выделенной вершиной, называемой корнем. Корневым лесом называется лес, каждая компонента связного которого представляет собой корневое дерево.

m-арное дерево (например, бинарное)

11. Помеченные деревья. Теорема Кэли.

Теорема (формула Кэли). Количество a_n различных помеченных деревьев на n вершинах равно n^n-2. Доказательство (Х.Прюфер, 1918 г.).

Код Прюфера или последовательность Прюфера переводит помеченные деревья порядка n в последовательности чисел по следующему алгоритму:

1. Выбирается лист с минимальным номером.

2. Лист и инцидентное ему ребро удаляются из дерева, а в последовательность Прюфера добавляется номер смежной с данным листом вершины.

3. Если в дереве больше двух вершин, то п. 1, иначе — выход.

По любому коду Прюфера можно однозначно восстановить исходное дерево.

Заметим:

1. Листья исходного дерева в коде не встречаются

2. Если вершина имеет степень k > 1, то такая вершина встречается в коде Прюфера ровно k-1 раз

3. Мы можем восстановить дерево, если на каждом шаге имели пару вершин – смежную и удаляемую. У нас есть последовательность смежных удаляемым вершин. Нужно восстановить по ней последовательность удаляемых.

Восстановление дерева по коду Прюфера

1. Обозначим P(T) = [y1, y2, ..., yn-3, yn-2] — последовательность Прюфера,

X= [1, 2, ..., n].

2. Выберем минимальное число v из X, не содержащееся в P(T).

3. Соединяем ребром вершину с номером v и вершину, соответствующую первому числу из P(T).

4. Удаляем v из X, удаляем первое число из P(T).

5. Если в X осталось два числа — соединяем ребром соответствующие вершины, иначе — п. 1.

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

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

Эйлеров цикл — замкнутый эйлеров путь.

Граф называется эйлеровым, если он содержит эйлеров цикл.

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

Доказательство. |=> Предположим, что существует эйлеров цикл С. Выберем произвольную вершину. Если это цикл, то зайдя в вершину, можем выйти из нее по еще не пройдённому ребру. Т.е. все ребра по отношению к любой вершине разбиваются на «вход» и «выход». Таким образом число степеней четно, т.к. «вход» и «выход» это пары.

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

Предположим, что остались непройденные ребра. Обозначим полученный цикл за С1. Пусть осталось неокрашенное ребро е. Т.к. граф связный, то имеется путь, соединяющий ребро е и вершину х. Значит, что существует вершина у, которая принадлежит С1 и инцидентна некрашеному ребру е’. Начнем от у новый путь. Получим цикл С2. Возьмем объединение x+C1+y+C2+y+C1+x. Получим цикл, который хотя бы на три ребра больше или равен чем мах. Продолжая эти действия в силу конечности графа получим эйлеров цикл.

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

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

Орграф называется эйлеровым, если он содержит хотя бы один эйлеров цикл.

Теорема критерий существования эйлерова цикла. В орграфе (слабо связном) существует эйлеров цикл тогда и только тогда, когда для любой его вершины x outdeg(x)=indeg(x)

Теорема критерий существования эйлерова пути. В орграфе (слабо связном) существует эйлеров цикл тогда и только тогда, когда для всех вершин x кроме двух u,v outdeg(x)=indeg(x), для u,v: outdeg(u) - indeg(u) = 1, outdeg(v) - indeg(v) = -1.

13. Гамильтонов путь, гамильтонов цикл. Определения, примеры, теорема Оре, следствие (теорема Дирака). Примеры. Понятие замыкание. Теоремы Хватала и Бонди-Хватала. Результаты для некоторых классов графов (например: полный, двудольный). Прикладные задачи. Аналоги для ориентированных графов.

Головоломка Гамильтона «Вокруг света»: обойти «вокруг света» по ребрам многогранника, посещая каждую вершину ровно один раз.

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

Примеры графов

•В любом циклическом графе Сn (n>2) существует ровно один гамильтонов цикл

•В графе K2 гамильтонова цикла не существует, но существует гамильтонов путь

•В случае полного графа Kn n>2 имеется (n-1)! гамильтоновых циклов.

Теорема Оре (1960 год). Пусть G – граф, построенный на n>2 вершинах. Если для любой пары несмежных вершин выполняется условие deg(x)+deg(y) ⩾n, то в графе G имеется гамильтонов цикл.

Следствие (Дирак, 1952 год). Пусть G – граф, построенный на n>2 вершинах. Если степень каждой его вершины ⩾ n/2, то в нем существует гамильтонов цикл.

Замыканием C(G) графа G называется граф, полученный из G последовательным соединением в нем ребрами пар несмежных между собой вершин, суммарные степени которых ⩾ n до тех пор, пока ни одной такой пары в графе не останется.

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

Теорема (Бонди-Хватал, 1976 год). Простой граф является гамильтоновым тогда и только тогда, когда его замыкание является гамильтоновым графом.

Данная теорема является обобщением теорем Оре и Дирака, которые непосредственно следуют из теоремы Бонди-Хватала.

Следствие. Если C(G)= Kn, то G – гамильтонов.

Т еорема (Хватал, 1972 год). Пусть G – простой граф, построенный на n вершинах, последовательность степеней вершин которого d1≤ d2≤... ≤dn удовлетворяет следующему условию: .

Тогда в G существует гамильтонов цикл.

Доказательство. Покажем, что замыкание С(G) графа G является полным графом Kn.

Предположим, что С(G) не является полным графом. Выберем в графе С(G) пару таких несмежных между собой вершин х, у, для которых сумма степеней максимальная: s = deg(x)+deg(y) < n.*

Пусть i := deg(x) < deg(y).

Из * следует:

1. deg(у) < n – i

2. i < n/2 => deg(x) < n – i

Любая несмежная с у вершины имеет степень, меньшую или равную deg(x)=i, т.к. выбрали несмежную пару с максимальной суммой степеней.

Т.к. deg(y) ≤ n – 1, то в графе C(G) гарантированно имеется i несмежных с у вершин, степень которых меньше или равна i.

Любая несмежная с х вершина имеет степень, меньшую или равную deg(у) < n – i:

1. т.к. степень вершины x=i, то в графе существует n-i-1 несмежных с х вершин, степень которых < n - i

2. кроме того, сама вершина х имеет степень < n - i.

Таким образом мы нашли по меньшей мере n-i вершин в графе C(G), степени которых < n - i.

Заметим, что G есть остовной подграф графа C(G). Поэтому если в C(G) какая-то вершина имеет степень, меньшую некоторого числа, то и в G степень этой вершины не превосходит того же числа.

Следовательно, мы нашли такое i < n / 2, для которого в графе G нашлось как минимум i вершин степени, меньшей или равной i, и n-i вершин, степень которых меньше n-i, а это противоречит условию теоремы.

Действительно, последовательность (d1,…,dn) степеней вершин упорядочена по неубыванию. Значит, первые i из этих чисел меньше или равны i, а следовательно, и i-тое число этой последовательности di<=i.

Аналогично доказывается для d_n-i<n-i.

Задачи, связанные с гамильтоновыми циклами

1.Задача коммивояжера

2. Задача о ходе шахматного коня

3. Задача сборки генома

Ориентированные графы

• Обобщение теоремы Дирака. Пусть есть сильно связный ориентированный граф с n вершинами, входящая и исходящая степень любой вершины которого больше или равна n/2. Тогда в данном графе существует гамильтонов цикл.

• Определение. Турниром T называется орграф, любые две вершины которого соединены ровно одним ориентированным ребром. Иными словами, турниром называется орграф, полученный из полного графа Kn произвольной ориентацией его ребер.

• Теорема. В любом турнире существует ориентированный гамильтонов путь.

14. Планарные графы. Грань, степень грани, аналог теоремы Эйлера. Теорема (формула Эйлера), следствия. Теорема Куратовского (критерий Понтрягина-Куратовского). Примеры.

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

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

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

Степень грани f - это количество ребер, инцидентных данной грани.

Мосты – ребра, по обе стороны от которых лежит одна и та же грань.

Теорема Эйлера. Сумма степеней всех граней связного плоского графа равна удвоенному числу ребер.

Теорема (формула Эйлера). Количество вершин n, ребер m и граней r произвольного связного плоского графа удовлетворяют следующему соотношению: n - m + r = 2.

Доказательство. I) Вспомогательное утверждение: n - m + r = 2 верно для дерева: n, m = n – 1, r = 1.

II) По индукции: r = 1 верно. Предположим, что верно для всех плоских связаных графов с r-1 гранью. Покажем, что верно для любого связного графа с количеством граней r.

Т.к. r > 1, то существует хотя бы 1 простой цикл. Возьмем произвольное ребро е этого цикла, и пусть е – это граница граней f1 и f2. Удаляем e, грани сливаются, -1 грань. В новом графе получаем, что n1 – m1 + r1 = 2, n1=n, m1=m-1, r1=r-1 => n - m + r = 2.

• Следствие 1. Все правильные вложения одного и того же связного планарного графа G в плоскость имеют одинаковое количество граней.

• Следствие 2. Количество m ребер в произвольном простом связном графе, построенном на n≥3 вершинах, не превосходит 3n-6.

• Следствие 3. Любой простой связный плоский граф обязан иметь вершину, степень которой не превосходит 5.

• Следствие 4. Граф K5 не планарен.

Теорема (Куратовский, 1930). Граф G не является планарным тогда и только тогда, когда он содержит подграф, представляющий собой подразбиение K5 или K3,3.

15. Представление графов: матрица смежности, матрица инциденций, списки смежности. Преимущества и недостатки. Примеры.