1. Понятие графа
1.1. Определение графа
Когда нужно наглядно представить взаимоотношения между какими-либо объектами, это часто делают в графической форме, изображая объекты значками (кружками, прямоугольниками и т.д.), а связи между ними – линиями или стрелками. При этом получаются диаграммы вроде тех, что показаны на рисунке 1.
SHAPE \* MERGEFORMAT
| a |
| 1 |
| b |
| c |
| d |
| e |
| 2 |
| 3 |
| f |
| 4 |
| a |
| c |
| b |
| d |
| e |
| f |
а) б) в)
Рис. 1.
При этом ни способ изображения элементов, ни форма или длина линий не имеют значения – важно лишь, какие именно пары элементов соединены линиями. Если посмотреть внимательно, то можно заметить, что рисунки 1а и 1б изображают одну и ту же структуру связей между элементами a,b,c,d,e,f. Эту же структуру можно описать, не прибегая к графическому изображению, а просто перечислив пары связанных между собой элементов: (a, b), (a, c), (b, d), (b, e), (d, e), (d, f), (e, f). Эти два списка – список элементов и список пар и образуют граф. Более «математично»: граф состоит из двух множеств – множества V, элементы которого называются вершинами, и множества Е, состоящего из пар вершин, эти пары называются ребрами графа. Это записывают так: G = (V, E), где G – имя графа. Это не самое общее определение графа, но мы будем рассматривать только такие. Говорят, что ребро (a, b) соединяет вершины а и b. Если такое ребро в графе есть, то говорят, что вершины а и b в нем смежны. Договоримся, что в графе не может быть, ребер типа (х, х), т.е. соединяющих вершину с ней же самой.
В приведенном определении графа один момент требует уточнения: считаем ли мы ребра (a, b) и (b, a) различными. Если да (и это распространяется на все ребра), то граф называется ориентированным, в противном случае – неориентированным. Дальше рассматриваются главным образом неориентированные графы (их называют также обыкновенными).
Отметим, что наибольшее число ребер в обыкновенном графе с n вершинами равно числу неупорядоченных пар из n элементов, т.е. Сn2 = n(n -1)/2.
1.2. Способы задания графов
Существует много способов представить граф, назовем только самые распространенные.
Перечисление элементов. Исходя из определения, для того, чтобы задать граф, достаточно перечислить его вершины и ребра. Положим, например, V = {a, b, c, d, e, f}, E = {(a, c), (a, f), (b, c), (c, d), (d, f)}. Тем самым задан граф G с 6 вершинами и 5 ребрами.
Изображение. Если граф невелик, его можно нарисовать. В неориентированном графе ребра изображаются линиями, в ориентированном – стрелками. Существует бесконечно много способов нарисовать один и тот же граф, и это является источником целого ряда математических и алгоритмических проблем. Определенный выше граф G показан на рисунке 2.
SHAPE \* MERGEFORMAT
| f |
| a |
| e |
| d |
| c |
| b |
Рис. 2.
Матрица смежности. Пусть G – граф с n вершинами, пронумерованными числами от 1 до n. Матрица смежности – это таблица с n строками и n столбцами, в которой элемент, стоящий на пересечении строки с номером i и столбца с номером j, равен 1, если вершины с номерами i и j смежны, и 0, если они не смежны. Для определенного выше графа G эта матрица выглядит следующим образом (вершины пронумерованы в алфавитном порядке): Рис.граф, и это является исьочником целого ряда математических и алгори:
|
| 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 0 | 0 | 0 |
| 3 | 1 | 1 | 0 | 1 | 0 | 0 |
| 4 | 0 | 0 | 1 | 0 | 0 | 1 |
| 5 | 0 | 0 | 0 | 0 | 0 | 0 |
| 6 | 1 | 0 | 0 | 1 | 0 | 0 |
Списки смежности. Этот способ, как и предыдущий, часто используется для компьютерного представления графов. Состоит он в том, что для каждой вершины задается список всех смежных с ней вершин. Для того же графа G это выглядит так (вершины представлены их номерами):
1: 3, 6 2: 3 3: 1, 2, 4 4: 3, 6 5: 6: 1, 4
В структурах данных, применяемых в программировании, это может быть реализовано как массив линейных списков.
1.3. Некоторые понятия теории графов
Для продолжения разговора о графах необходимо ввести некоторые термины.
Множество вершин, смежных с данной вершиной х в некотором графе, называется окрестностью этой вершины и обозначается через N(x). Число вершин в N(x) называется степенью вершины х и обозначается через deg(x). Если сложить степени всех вершин графа, то каждое ребро внесет в эту сумму вклад, равный 2. Следовательно, сумма степеней всех вершин равна удвоенному числу ребер графа. Это утверждение называют теоремой о рукопожатиях.
Путь в графе – это последовательность вершин х1, х2, ... , хk , в которой каждая пара (xi, xi+1), i =1, … , k – 1, является ребром, причем все эти ребра различны. Длиной пути называется число ребер в нем, т.е. k – 1. Цикл – это путь, у которого х1 = хk.
Расстоянием между вершинами в графе называется наименьшая длина соединяющего их пути.
Граф называется связным, если для любых двух его вершин имеется путь, соединяющий эти вершины. Если граф несвязен, то он состоит из нескольких связных частей, они называются компонентами связности. Ориентированный граф называется сильно связным, если из каждой вершины в любую другую имеется (ориентированный) путь
Связный граф, не имеющий циклов, называют деревом. В дереве каждые две вершины соединены единственным путем. Иногда в дереве особо выделяется некоторая вершина, ее называют корнем, а все дерево – корневым деревом. Если вершина х лежит на пути, соединяющем вершину y с корнем, то говорят, что х – предок y , а y – потомок х (см. рисунок 3).
SHAPE \* MERGEFORMAT
| потомки |
| корень |
| потомки |
| предок |
Рис. 3.
2. Кратчайшие пути. Поиск в ширину
Одна из задач, естественно возникающих по отношению к графам – поиск кратчайшего пути между двумя заданными вершинами. Процедура поиска в ширину, решающая эту задачу, может использоваться и для других целей.
Пусть задан граф G, в нем указаны вершины а и b, требуется найти кратчайший путь между ними. Имеется простой план решения этой задачи: исследуем сначала все вершины, находящиеся на расстоянии 1 от вершины а (первый уровень). Если вершины b среди них нет, строим второй уровень, рассматривая поочередно вершины первого уровня и отбирая из окрестности каждой из них те, которые еще не исследованы. Если вершины b нет и на втором уровне, аналогично строим и исследуем третий и т.д. из окрестности каждой из нихсследованы. ровня иПри этом для каждой вершины следующего уровня запоминаем смежную с ней вершину предыдущего уровня (ту, при исследовании окрестности которой она была обнаружена). Когда встретится, наконец, вершина b, по этим данным можно будет проследить кратчайший путь от b к а. Если же вершина b вообще не встретится, значит, пути между вершинами а и b не существует.
Излагаемый ниже алгоритм на самом деле решает более широкую задачу – он находит кратчайшие пути от заданной вершины а до всех остальных (достижимых из а) вершин. Полученная система путей оформляется в виде дерева кратчайших путей. Это дерево с корнем а, в котором путь от а до любой вершины является кратчайшим путем между этими вершинами в графе. Оно задается массивом непосредственных предков Р – значением Р[x] является непосредственный предок («отец») вершины x (вершины идентифицируются своими номерами) в дереве. Р[x] – первая после х вершина на кратчайшем пути из х к корню. Вначале полагаем Р[а] = a и Р[х] = 0 для всех остальных вершин (считаем, что нумерация вершин начинается с 1, так что вершины 0 не существует). Если это нулевое значение сохраняется по завершении работы алгоритма, значит, не существует пути из х в а. Пример дерева кратчайших путей показан на рисунке 4.
SHAPE \* MERGEFORMAT
| 31111111 |
| 11111111 |
| 41111111 |
| 71111111 |
| 21111111 |
| 61111111 |
| 51111111 |
|
|
| 31111111 |
| 11111111 |
| 41111111 |
| 71111111 |
| 21111111 |
| 61111111 |
| 51111111 |
| х | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Р(х) | 1 | 1 | 1 | 3 | 2 | 2 | 6 |
Рис. 4. Граф и дерево кратчайших путей с корнем 1 для него.
Алгоритм посещает вершины в определенном порядке, каждая вершина посещается не более чем один раз. Вершину назовем новой, если она еще не посещена; вершину назовем открытой, если она посещена, а ее окрестность еще не исследована.
Для запоминания новых вершин используется массив H. Элемент этого массива H[x] принимает значение true, если вершина x новая, в противном случае – значение false. Вначале все элементы массива имеют значение true.
Для хранения открытых вершин используется очередь Q . Вначале она пуста. Первой в нее помещается вершина а. На очередном шаге из очереди выбирается активная вершина х (первая в очереди, при этом она из очереди удаляется) и исследуется ее окрестность. Каждая новая вершина из этой окрестности добавляется в конец очереди. Именно использование очереди обеспечивает главное свойство поиска в ширину: чем ближе вершина к старту а, тем раньше она будет посещена.
Теперь алгоритм поиска в ширину можно представить следующим образом (BFS – аббревиатура английского названия поиска в ширину – Breadth First Search) .
procedure BFS(a)
1 H[a] := false {посещение вершины а}
2 Q ← a
3 Р[а] := а
4 while Q ≠ Ø do
5 x ← Q {выбирается активная вершина}
6 for do {исследуется окрестность вершины х}
7 if H[y] then
8 H[y] := false {посещение вершины y}
9 Q ← y
10 P[y] := x
Теперь, чтобы найти кратчайший путь из любой вершины b до вершины а, нужно сначала убедиться, что P[b] ≠ 0, затем проделать следующее:
X[1] := b
k := 1
while X[k] ≠ a do
k := k + 1
X[k] := P[X[k – 1]]
Последовательность X[1], X[2], ... , X[k] и будет искомым путем.
Время работы этого алгоритма определяется числом повторений внутреннего цикла (строка 6). Этот цикл записан здесь в математической форме. Программная его реализация зависит от того, как задан граф. Если он задан матрицей смежности, то для выявления всех вершин из окрестности вершины х необходимо просмотреть всю строку матрицы, соответствующую этой вершине. Если в графе n вершин, то цикл повторяется для каждой вершины х ровно n раз, а общая трудоемкость оценивается как O(n2). Если же граф задан списками смежности, то для активной вершины х цикл будет повторяться deg(x) раз (столько элементов в списке). Так как каждая вершина становится активной только один раз, то общее число повторений равно сумме степеней вершин графа, т.е. 2m, где m – число ребер. Следовательно, общая трудоемкость алгоритма оценивается как О(m). Отметим, что m ≤ n(n – 1)/2 = O(n2), так что в худшем случае эти оценки совпадают. Однако для графов с небольшим числом ребер применение списков смежности может дать серьезный выигрыш в скорости.
3. Поиск в глубину
3.1. Алгоритм поиска в глубину
Поиск в глубину – вероятно, наиболее важная ввиду многочисленности приложений стратегия обхода и исследования графа. Идея этого метода – идти вперед в неисследованную область, пока это возможно, если же вокруг все исследовано, отступить на шаг назад и искать новые возможности для продвижения вперед. Метод поиска в глубину известен под разными названиями, например, «бэктрекинг», «поиск с возвращением»
Понятия новой и открытой вершин для поиска в глубину имеют такой же смысл, как и для поиска в ширину. При поиске в ширину в качестве активной вершины выбирается та из открытых, которая была посещена раньше других (это обеспечивается применением очереди для хранения открытых вершин), и она остается активной, пока не будет полностью исследована ее окрестность. При поиске в глубину вершина становится активной сразу после ее посещения и, если в ее окрестности есть новые вершины, она немедленно перестает быть активной (но в дальнейшем может снова стать активной). Для реализации такого правила выбора наиболее удобной структурой хранения множества открытых вершин является стек: открываемые вершины складываются в стек в том порядке, в каком они открываются, а в качестве активной вершины выбирается верхний (последний) элемент стека. При посещении вершины она помещается в стек, а удаляется из него тогда, когда будет полностью исследована ее окрестность.
Обозначим стек для открытых вершин через S, остальные обозначения сохраняют тот же смысл, что и в предыдущем разделе. Через top(S) обозначается верхний элемент стека. Как и при поиске в ширину будем в процессе обхода заполнять массив Р: значением Р(х) является вершина, которая была активной, когда посещалась вершина х.
Считаем, что граф задан списками смежности: L(x) – список вершин, смежных с вершиной х. Запись y ← L(x) означает, что в качестве y берется первый элемент из списка L(x), при этом он удаляется из списка.
Процедура обхода графа методом поиска в глубину со стартовой вершиной a может быть записана следующим образом (DFS – от Depth First Search – поиск в глубину).
Procedure DFS(a)
1 H[a] := false {посещение вершины а}
2 S ← a
3 P[a] := a
4 while S ≠ Ø do
5 x := top(S) {выбирается активная вершина}
6 if L(x) ≠ Ø
7 then y ← L(x)
8 if H[y] then
9 H[y] := false {посещение вершины y}
10 S ← y
11 P[y] := x
12 else удалить х из S
При каждом повторении цикла while либо одна вершина удаляется из списка смежности (строка 6), либо одна вершина удаляется из стека (строка 11, при этом она снова в стек попасть не может, так как перестала быть новой). Общее число вершин, помещаемых в стек, не превосходит суммарной длины списков смежности, которая равна 2m. Отсюда следует оценка О(m) трудоемкости этого алгоритма.
Далее рассмотрим два простых примера применения поиска в глубину.
3.2. Выявление компонент связности
Простейший пример применения поиска в глубину – выявление компонент связности графа. Решение задачи представляется в виде массива Comp, где Comp[x] – номер компоненты, содержащей вершину х. Далее в качестве счетчика компонент используется переменная с.
Процедуру поиска в глубину чаще представляют в рекурсивной форме, при этом запись получается более компактной, а стек скрыт в механизме реализации рекурсии. Рассмотрим рекурсивный вариант поиска в глубину, при котором каждой посещаемой вершине присваивается в качестве номера компоненты значение с.
Procedure DFS(a)
1 Comp(a) := c
2 for do
3 if H[b] then DFS(b)
Эта процедура обходит только одну компоненту – ту, которой принадлежит вершина а. Переход к другим компонентам можно обеспечить следующим образом. Через V обозначается множество всех вершин графа.
1 for do H[x] := true
2 c := 0
3 for do
4 if H[x] then
5 c := c + 1
6 DFS(x)
Это применение не является специфическим для поиска в глубину – ту же задачу можно успешно решать с помощью поиска в ширину или какого-либо другого метода обхода графа. В следующем примере уже существенно используются свойства именно поиска в глубину.
3.3. Задача об одностороннем движении
Допустим, связный граф представляет собой схему городских улиц: вершины соответствуют перекресткам, ребра – отрезкам улиц между перекрестками. Власти хотят ввести одностороннее движение на каждом таком отрезке. При этом должна сохраняться полная достижимость, т.е. возможность из каждой точки города попасть в любую другую. На языке теории графов задача состоит в том, чтобы каждому ребру заданного неориентированного графа придать ориентацию (в одном направлении) так, чтобы полученный ориентированный граф был сильно связным.
Задача эта не всегда имеет решение. Пример, когда его нет, показан на рисунке 5. Как бы мы не ориентировали ребро (a, b) в этом графе, из одной
SHAPE \* MERGEFORMAT
| b |
| a |
Рис. 5. Перешеек
части графа нельзя будет попасть в другую. Причина в том, что это перешеек – ребро, при удалении которого нарушается связность. Ясно, что если в графе имеется хотя бы один перешеек, то задача об одностороннем движении для этого графа не имеет решения. Оказывается, для любого графа без перешейков решение существует и может быть легко найдено с помощью поиска в глубину. Рассмотрим сначала одно свойство поиска в глубину.
Как и при поиске в ширину, массив Р[х], который строит процедура DFS(a), задает дерево c корнем a, оно называется dfs-деревом. Ребра этого дерева будем называть сильными, остальные ребра графа – слабыми. Важное свойство dfs-дерева состоит в том, что каждое слабое ребро соединяет предка с потомком в этом дереве. Поэтому, например, дерево, показанное на рисунке 7 (сильные ребра показаны жирными линиями), не является dfs-деревом, т.е. не может быть получено в результате поиска в глубину, так как слабое ребро (1, 2) соединяет вершины, не связанные отношением предок-потомок. На этом свойстве основаны многие применения поиска в глубину.
SHAPE \* MERGEFORMAT
| 1 |
| 2 |
| 3 |
| 4 |
Рис. 6.
К решению задачи об одностороннем движении это можно применить следующим образом. Выполним на графе поиск в глубину, при этом каждому сильному ребру придадим ориентацию от предка к потомку, а каждому слабому – от потомка к предку. Это можно делать в процессе обхода: нужно только после выбора вершины y (в строке 7 процедуры DFS) придать ребру (x, y), если оно еще не получило ориентации, ориентацию от х к y. Если в графе нет перешейков, то полученная ориентация является решением задачи. Действительно, ясно, что из корня дерева можно попасть в любую вершину ориентированным путем, состоящим из сильных ребер. Обратно, так как перешейков нет, то для любой вершины x, отличной от корня, существует слабое ребро, ведущее от x или ее потомка к ее предку (в противном случае ребро, соединяющее x с ее непосредственным предком, было бы перешейком). Поэтому из x можно ориентированным путем (сначала по сильным ребрам, потом по слабому) попасть в вершину, являющуюся ее предком. Серия таких «спусков» неизбежно приведет в корень. Таким образом, из любой вершины достижим корень. Следовательно, полученный ориентированный граф – сильно связный.
4. Графы и игры
Слова «граф» и «игра» нередко оказываются рядом. Чаще всего это происходит из-за того, что придумано много игр на графах. В этих играх игроки передвигаются по графу или что-нибудь делают с ним: удаляют вершины или ребра, красят их в разные цвета и т.д. Некоторые из этих игр возникли как подспорье при изучении проблем самой теории графов, другие моделируют жизненные коллизии или обобщают известные игры. В качестве примера рассмотрим игру Ним, проанализированную Бержем [2] и обобщающую известную игру с тем же названием.
В игре Ним два игрока поочередно передвигают одну фишку из вершины в вершину по ребрам ориентированного графа (каждый ход – одно ребро). Проигрывает тот, кто не может сделать очередной ход, так как оказался в тупике – вершине, из которой не выходит ни одно ребро. Начальная позиция выбирается случайным образом.
Если в графе нет тупиков, игра не имеет смысла, так как ни одна партия не может закончиться. Бесконечные партии возможны и в том случае, когда в графе имеется ориентированный цикл. Рассмотр… Продолжение »