Алгоритмы на графах

ФПМИ БГУ
|V|=n - число вершин в графе (орграфе)
|E|=m - число ребер (дуг) в графе (орграфе)

Структуры данных для представления графа (орграфа)
ФПМИ БГУ
Матрица смежности
Списки смежности
Матрица инцидентности
Списки дуг

Матрица смежности. Списки смежности
2 3 4
1 4
1 4
1 2 3
1 2 3 4
4
4
Если матрицу смежности AG возвести в степень k, то AGk[v,w] – число попарно различных (v,w)-маршрутов длины k.
Ө(n2)
Ө(n+m)
Ө(n2)
Ө(n+m)
v
w
ФПМИ БГУ

Матрица инцидентности
Ө(nm)
Ө(nm)
ФПМИ БГУ

Списки дуг
1
3
4
2
e4
e1
e2
e3
e’2
Ө(n+m)
e’3
e’4
e’1

Поиск в ширину
(англ. BFS - Breadth First Search)
ФПМИ БГУ

1
1
1
0
2
2
2
3
Поиск в ширину
1
6
5
4
3
2
7
10
Обход всех вершин графа в порядке удаленности от стартовой вершины.
8
9
11
queue:
1
2
3
4
8
5
9
6
10
7
3
3
ФПМИ БГУ

Задание графа матрицей смежности
Время работы О(n2)
Время работы О(n+m)
v
u1
uk
ФПМИ БГУ
Задание графа списками смежности

кратчайший путь – задан взвешенный граф (орграф); необходимо найти такой путь между заданной парой вершин, для которого сумма стоимостей входящих в него ребер (дуг) минимальна;
наименьший путь – задан граф (орграф); необходимо найти путь между заданной парой вершин, длина которого по количеству рёбер (дуг) минимальна;
ФПМИ БГУ
Терминология
1
4
3
2
5
10
6
1
3
1
1
кратчайший путь между вершинами 1 и 5 (стоимость 8):
1
4
3
5
1
1
6
наименьший путь между вершинами 1 и 5 (длина 2):
1
3
5

ФПМИ БГУ
BFS находит наименьший путь между стартовой вершиной поиска в ширину (start) и всеми, достижимыми из неё вершинами;

1
1
3
5
4
3
1
6
5
4
3
2
7
10
8
9
11
1
None
2
8
pred
ФПМИ БГУ
BFS находит наименьший путь между стартовой вершиной поиска в ширину (start) и всеми, достижимыми из неё вершинами;
если необходимо восстановить последовательность вершин наименьшего пути, то для этого нужно сформировать массив pred:

1
4
7
3
6
9
2
0
5
8
Пометки вершин орграфа в порядке их обхода алгоритмом BFS:
1
6
5
4
3
2
7
10
8
9
11

Свойством двудольного графа является то, что если две вершины графа смежны, то они принадлежат разным долям.
ФПМИ БГУ
BFS можно использовать для определения двудольности графа
Теорема Кёнига (1936 г.)
Для двудольности графа необходимо и достаточно, чтобы он не содержал циклов нечетной длины.

Орграф G
Основание орграфа G
ФПМИ БГУ
Для определения двудольности ориентированного графа нужно сначала перейти к его основанию (т.е. дуги орграфа заменить рёбрами).
Если полученный псевдограф - двудольный, то и исходный орграф - двудольный.

1
6
5
4
3
2
7
10
8
9
11
При обнаружения цикла (вершина w, которая смежна с текущей вершиной v, уже была посещена) мы сравним метки вершин v и w. Если окажется, что вершины v и w принадлежат одной доле (met[w]=met[v]) , то граф не является двудольным.
1
2
2
1
1
1
2
2
2
1
1
ФПМИ БГУ
BFS можно использовать для определения двудольности графа
Присвоив метку стартовой вершине, мы определим метки всех смежных с ней вершин как противоположные, и так далее:
met[v]
met[u]=3-met[v]
Отметим, что, если компонент связности несколько, то для двудольности графа требуется, чтобы каждая каждая компонента связности была двудольной.
Граф является двудольным.
w
met[w]

1
2
2
2
1
6
5
4
3
2
7
10
8
9
11
1
6
5
4
3
2
7
10
8
9
11
Ориентированный граф не является двудольным так как его основание не является двудольным графом.
ФПМИ БГУ
Определить, является ли приведённый на рисунке орграф двудольным, используя BFS.

1
6
5
4
3
2
7
10
8
9
11
Всякий максимальный по включению связный подграф графа G (т.е. не содержащийся в связном подграфе с большим числом элементов) называется связной компонентой графа G.
У графа, изображённого на рисунке, две связные компоненты.
ФПМИ БГУ
BFS можно использовать для определения связности графа
Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом.

ФПМИ БГУ
BFS можно использовать для решения следующих задач
Поиска маршрута между заданной парой вершин.
Поиска наименьшего (по количеству рёбер/дуг) маршрута между заданной парой вершин.
Определения двудольности графа (орграфа).
Выделения связных компонент графа.
Время работы О(n+m), если граф задан списками смежности.
Время работы О(n2), если граф задан матрицей смежности.
В программной реализации поиска в ширину используется структура данных ОЧЕРЕДЬ (queue).

Эйлеров цикл в графе
Для связного графа эйлеров цикл – это цикл, который содержит все рёбра графа.
Связный граф, обладающий эйлеровым циклом, называется эйлеровым графом.
Необходимое и достаточное условие, Л. Эйлер, 1736
Нетривиальный связный граф содержит эйлеров цикл тогда и только тогда, когда степени всех его вершин чётны.
Степень вершины равна числу инцидентных ей рёбер.
Леонард Эйлер
(1707-1783)
швейцарский
немецкий
российский математик
ФПМИ БГУ

ФПМИ БГУ
эйлеров граф
граф не является
эйлеровым т.к. есть вершины нечётной степени
граф должен быть связным
граф - тривиальный

ФПМИ БГУ
Граф эйлеров, если мы можем его нарисовать, не отрывая руку от бумаги: стартуем из любой вершины, прорисовываем каждое ребро ровно один раз и обязательно возвращаемся в стартовую вершину.

Алгоритм построения эйлерова цикла в графе
Абстрактные типы данных очередь (queue) и стек (stack) – пустые.
2. Выбрать произвольную вершину графа и добавить её в стек.
3. Пока стек не пуст, выполнять следующие действия:
пусть v – вершина, которая последняя была занесена в стек :
если существует ребро (v,w), то добавляем вершину w в стек и удаляем ребро (v,w) из графа ;
если не существует ребра, инцидентного вершине v, то удаляем вершину v из стека и добавляем её в очередь.
4. Последовательность вершин очереди задаёт порядок обхода вершин в эйлеровом цикле.
ФПМИ БГУ

1
5
3
4
2
Алгоритм построения эйлерова цикла графа
Структуры данных очередь (queue) и стек (stack) – пустые.
Выбрать произвольную вершину графа и добавить её в стек.
Пока стек не пуст, выполнять следующие действия (пусть v – вершина, которая последняя была занесена в стек :
если существует ребро (v,w), то добавляем вершину w в стек и удаляем ребро (v,w) из графа ;
если не существует ребра, инцидентного вершине v, то удаляем вершину v из стека и добавляем её в очередь.
4. Последовательность вершин очереди задаёт порядок обхода вершин в эйлеровом цикле.
стек
очередь
| 1
| 1
| 1
| 1
| 1
1
3
2
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
1
1
3
2
4
5
1
2
3
4
5
6
5
1
5
4
3
2
6
1
3
4
4
5
5
6
6
6
5
2
1
Время работы алгоритма на матрице смежности:
О(m) + О(n2)
ФПМИ БГУ
для каждой строки i укажем номер столбца, начиная с которого в этой строке будет осуществляться движение при поиске вершин, смежных с вершиной i

1
5
3
4
2
Время работы алгоритма на списках смежности:
О(m)
ФПМИ БГУ
1
2
2 5
1 5
3
4 5
4
3 5
5
1
2
3
4

Задан граф (не обязательно связный).
Необходимо покрыть граф наименьшим числом рёберно-непересекающихся цепей.
Цепи могут быть открытыми или замкнутыми.
Каждое ребро графа должно входить в одну из этих цепей.
ФПМИ БГУ
Если граф не связный, то решаем задачу оптимально для каждой компоненты связности.
Задача

ФПМИ БГУ

1
5
3
4
2
6
7
ФПМИ БГУ
1. Если граф содержит эйлеров цикл, то задача решена – строим эйлеров цикл и покрываем граф одной замкнутой цепью эйлеровым циклом).
2. Если граф не содержит эйлеров цикл, значит в нём , есть вершины нечётной степени. Предположим, что их – k штук. Отметим, что число k – чётно (лемма о рукопожатиях).
3. Введём фиктивную вершину f, которую соединим рёбрами со всеми вершина нечётной степени. Теперь степени всех вершин – чётны.
4. Построим в преобразованном графе эйлеров цикл.
f
Эйлеров цикл : 1-5-7-f-6-4-5-f-3-5-2-1
1
5
3
4
2
6
7
f

5. Удалим из эйлерова цикла вершину f и инцидентные ей рёбра.
ФПМИ БГУ
1
5
3
4
2
6
7
f
1 удаление
3 удаление
2 удаление
фиктивная вершина встречается в цикле k/2 раз
1
1
2
1
2
3
Если k – число вершин нечётной степени, то эйлеров цикл распадется на k/2 рёберно-непересекающихся цепей.
k=4 – число вершин нечётной степени
(продолжение)

ФПМИ БГУ

1
5
3
4
2
6
ФПМИ БГУ
стек
эйлеров цикл : 1 – 5 – 7 – f1 – 6 – 4 – 5 – f2 – 3 – 5 – 2 – 1
5
7
f
6
4
5
f
3
1
5
2
1
top
очередь: 1 5 7 f 6 4 5 f 3 5 2 1
(продолжение)
7
f
удаление фиктивной вершины f1
6 – 4 – 5 – f2 – 3 – 5 – 2 – 1– 5 – 7
удаление фиктивной вершины f2
6 – 4 – 5
3 – 5 – 2 – 1– 5 – 7

Поиск в глубину ( англ. DFS - Depth First Search)

1
6
5
4
3
2
7
10
8
9
11
1
2
3
5
10
8
6
4
9
7
12
11
12
Один из способов обхода вершин и рёбер (дуг) графа (орграфа).
сначала все вершины белые;
становится серой, когда первый раз приходим в неё;
становится чёрной, когда все смежные вершины уже были посещены;
Поиск в глубину в орграфе:

1
6
5
4
3
2
7
10
8
9
11
1
2
3
5
10
8
6
4
9
7
12
11
12
обратное (ещё не ориентировано и ведёт в вершину,
которая ранее уже была посещена);
древесное (ведёт в непосещенную вершину)
1 2 3 4 5 6 7 8 9 10 11 12
1 0 1 1 1 0 0 0 0 0 1 0 0
2 1 0 1 0 0 0 0 1 0 0 0 0
3 1 1 0 1 1 0 0 0 0 0 0 0
4 1 0 1 0 0 0 0 0 1 0 0 0
5 0 0 1 0 0 0 0 0 0 1 0 0
6 0 0 0 0 0 0 0 1 0 1 0 0
7 0 0 0 0 0 0 0 0 1 1 0 0
8 0 1 0 0 0 1 0 0 0 0 0 0
9 0 0 0 1 0 0 1 0 0 0 0 0
10 1 0 0 0 1 1 1 0 0 0 0 0
11 0 0 0 0 0 0 0 0 0 0 0 1
12 0 0 0 0 0 0 0 0 0 0 1 0
ФПМИ БГУ
Ориентация рёбер при обходе в грубину:
ориентированные, как обратные, рёбра приводят к циклу
Поиск в глубину в графе

ФПМИ БГУ
Программная реализация DFS

ФПМИ БГУ

Нерекурсивный DFS на списке смежности
Здесь last - массив, в котором для каждой вершины v хранится индекс той позиции списка смежных с ней вершин, в которой мы остановились, когда осуществляли поиск вершин смежных с v. Первоначально массив заполнен 0.
ФПМИ БГУ
visit[u]=True
visit[s]=True

1
6
5
4
3
2
7
10
8
9
11
1
2
7
0
5
3
8
4
9
6
10
ФПМИ БГУ
Порядок обхода вершин

Вместо None можно использовать -1 или v, если мы точно знаем, что нет петель.
Зная метки pred, можно восстановить пути из стартовой вершины во все остальные вершины.
6
5
4
3
2
7
10
8
9
11
2
1
3
4
5
9
pred
1
None
1
2
8
None
ФПМИ БГУ
Корневое дерево поиска в глубину

Компоненты связности графа
0
2
1
Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом.
ФПМИ БГУ

Определение двудольности графа
1
2
3
4
True
False
True
is_bipartite=False
ФПМИ БГУ

Топологическая сортировка
ФПМИ БГУ

Топологической сортировкой
вершин орграфа, который не содержит контуров, называется такая перенумерация его вершин, что у любой дуги (u,v) номер её начала u меньше, чем номер её конца v (либо наоборот).
1
2
7
5
6
8
3
4
1
2
3
4
5
6
7
8
Для этого можно разместить вершины орграфа на одной линии так, чтобы все дуги исходного орграфа шли в одну сторону, например, слева направо или справа налево.
Затем присвоить новые номера вершинам, двигаясь вдоль линии слева направо.
ФПМИ БГУ

Для выполнения топологической сортировки вершин ациклического орграфа можно использовать, алгоритмы
А. Кана (1962)
Р. Тарьяна (1976)
Артур Кан
(A. B. Kahn)
Роберт Тарьян
(Robert Endre Tarjan), родился в 1948 г.
американский учёный в области вычислительных систем
ФПМИ БГУ

Алгоритм Кана
Пока в графе G существуют вершины без входящих дуг, выполнять следующие действия:
найти любую вершину v без входящих дуг и присвоить ей новый номер (нумерация начинается с единицы);
удалить из орграфа G вершину v вместе с выходящими из неё дугами и повторить алгоритм.
1
5
2
3
7
6
4
8
1
2
6
5
7
8
3
4
1
2
3
4
5
6
7
8
ФПМИ БГУ
Проверить, всем ли вершинам были присвоены номера. Если не все вершины получили новые номера, то в орграфе существует контур и топологическая сортировка не может быть выполнена.
Пример
G

1
2
3
4
5
1
2
1
2
ФПМИ БГУ
Проверить, всем ли вершинам были присвоены номера:
можно ввести счётчик числа вершин, которые были перенесены на линию:
если нет вершин без входящих дуг и счётчик = |V|, то топологическая сортировка выполнена успешно;
если счётчик < |V|, то в орграфе существует контур и топологическая сортировка не может быть выполнена.
Пример

1
5
2
3
7
6
4
8
1
2
6
5
7
8
3
4
1 2 3 4 5 6 7 8
1 0 0 0 0 0 0 0 1
2 0 0 0 0 0 0 0 1
3 0 0 0 1 0 0 0 0
4 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0
6 0 0 0 0 1 0 0 0
7 0 0 0 0 0 0 0 0
8 0 0 1 1 0 0 0 0
0 0 1 2 1 0 0 2
Queue:
1
2
6
7
1
0
8
0
5
0 1
3
0
4
Время реализации алгоритма топологической сортировки Кана
при задании орграфа матрицей смежности - O(n2);
при задании орграфа списками смежности - O(n +m).
ФПМИ БГУ
Пример

Алгоритм Тарьяна
ФПМИ БГУ

1
5
2
3
6
7
4
8
topsorted: 4 3 8 1 2 5 6 7
Алгоритм Тарьяна
ФПМИ БГУ
4
3
8
1
2
5
6
7

ФПМИ БГУ

Выделение сильно-связных компонент орграфа
Орграф называется сильносвязным, если любые его две вершины достижимы друг из друга (считается, что вершина достижима сама из себя).
Сильносвязной компонентой орграфа называется любой его максимальный по включению сильносвязный подграф.
1
3
2
4
5
8
7
6
9
10
Орграф не является сильно связным.
Орграф содержит 4 сильносвязные компоненты.
1'
2'
3'
4'
Конденсация графа:
все сильносвязные компоненты свёрнуты в одну вершину.
ФПМИ БГУ

Алгоритм Косарайю - Шарира
выделения сильно-связных компонент орграфа (основанный на DFS)
1978 год Самбрасива Рао Косарайю/Косараджу (Kosaraju)– американский учёный индийского происхождения, профессор информатики;
1979 год Миха Шарир (Micha Sharir) , родился в 1950 г., Израиль, профессор, специалист по вычислительной и комбинаторной геометрии;
Micha Sharir
С. Рао Косарайю
ФПМИ БГУ

Алгоритм Косарайю - Шарира
1
3
2
4
5
8
7
6
9
10
1
3
2
4
5
8
7
6
9
10
1
2
7
4
3
11
13
14
15
16
ФПМИ БГУ
Этап 1.
DFS. Вершинам присваивается две метки (нумерация у обеих меток – общая):
первая метка присваивается, когда первый раз заходим в вершину (вершина становится серой);
вторая метка присваивается, когда поиск в глубину из этой вершины завершён (осуществляется возврат из вершины и она становится чёрной).
Этап 2.
заменить каждую дугу орграфа на противоположно направленную;
выполнить DFS, начиная с вершины с самой большой второй меткой: вершины, которые при этом будут посещены, принадлежат одной сильно-связной компоненте.
,10
,9
,6
,5
,8
,12
,20
,19
,18
,17

Обоснование корректности алгоритма Косарайю-Шарира
Рассмотрим конденсацию графа G, то есть граф, в котором все сильно связные компоненты свернуты в одну вершину. Очевидно, что этот граф ацикличен, а значит, его можно отсортировать.
Если запишем вершины в порядке выхода из функции dfs, то самая последняя вершина в этом списке будет принадлежать "корню" конденсированного графа.
Воспользуемся фактом, что если транспонировать сильно связную компоненту, то мы все равно получим сильно связную компоненту. Таким образом, если транспонировать граф и запустить DFS из последней вершины, то мы посетим только вершины внутри одной сильносвязной компоненты. Соответственно, следующей непосещенной вершиной будет "корень" конденсированного графа без уже посещенной компоненты, и так далее.
Таким образом, задача решается двумя обходами DFS.
ФПМИ БГУ

Пусть rg -- транспонированный орграф g, то есть орграф, в котором все дуги развернуты в обратную сторону.
Время работы алгоритма Косарайю-Шарира:
O(n+m), если орграф задан списками смежности
O(n2), если орграф задан матрицей смежности.
ФПМИ БГУ
Программная реализация алгоритма Косарайю - Шарира

ФПМИ БГУ
DFS можно использовать для решения следующих задач
Поиск маршрута между заданной парой вершин.
Определение двудольности графа (орграфа).
Выделения связных компонент графа.
Выделение сильно-связных компонент ориентированного графа (алгоритм Косарайю-Шарира).
Топологическая сортировка вершин бесконтурного ориентированного графа (алгоритм Тарьяна).
Нахождение фундаментального множества циклов графа.
Нахождение контуров в орграфе.
Поиск точек сочленения и мостов.
и др.
Время работы О(n+m), если граф задан списками смежности.
Время работы О(n2), если граф задан матрицей смежности.

Общие задачи в iRunner для закрепления навыков
0.4 Матрица смежности
0.5. Канонический вид (по списку дуг)
0.6. Список смежности
0.7 Канонический вид (по матрице смежности)
0.8 BFS (поиск в ширину)
0.9 DFS (поиск в глубину)