Учебно-методический комплекс по дисциплине «Теория конечных графов и ее приложения» Алексеев В. Е, Захарова Д. В

4. Методы обхода графа

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

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

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

Если все ребра, инцидентные активной вершине, уже исследованы, она становится закрытой. Эти действия повторяются до тех пор, пока множество открытых вершин не станет пустым. Если при этом еще остались новые вершины, то выбирается и посещается одна из таких вершин и процесс повторяется.

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

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

Поиск в ширину

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

В приводимом описании процедуры поиска в ширину (BFS – Breadth First Search) a – стартовая вершина, Q – очередь открытых вершин.
Procedure BFS(a)
1 посетить ;

2 while do

3 ;

4 for do

5 if y новая then посетить
Процедура посещения, кроме действий, связанных с решением конкретной задачи, должна включать две обязательных операции: вершину нужно пометить как посещенную (т.е. не новую) и поместить в очередь Q.

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

Поиск в ширину
6 пометить все вершины как новые;

7 for do if новая then BFS(x)

Если граф задан списками смежности, то внутренний цикл в строке 4 процедуры BFS повторяется раз. Кроме того, цикл в строке 7 повторяется n раз. Поэтому общая трудоемкость поиска в ширину оценивается как . Если же граф задан матрицей смежности, то для сканирования окрестности вершины (строка 4) необходимо полностью просмотреть соответствующую строку этой матрицы и общая трудоемкость будет .
Рассмотрим примеры применения поиска в ширину для решения конкретных задач.
Компоненты связности. Рассмотрим задачу выявления компонент связности графа. Ответ нужно получить в виде таблицы, в которой для каждой вершины должен быть указан номер компоненты , которой эта вершина принадлежит. Для решения этой задачи достаточно ввести переменную c со значением, равным текущему номеру компоненты, и каждый раз при посещении новой вершины x присваивать значение . Значение c первоначально устанавливается равным 0 и модифицируется при каждом вызове процедуры BFS.
Кратчайшие пути и расстояния. Допустим, поиск в ширину выполняется на связном графе. Каркас, образованный прямыми ребрами, можно рассматривать как корневое дерево с корнем в стартовой вершине. Оно называется BFS-деревом. В процессе обхода легко построить таблицу отцов , задающую это дерево: достаточно при посещении вершины при активной вершине присвоить значение . BFS-дерево с данным корнем не единственно, оно зависит от того, в каком порядке рассматриваются ребра, инцидентные активной вершине. Но все BFS-деревья обладают одним свойством, на котором основаны важнейшие применения поиска в ширину. Корневой каркас связного графа называется деревом кратчайших путей, если путь от любой вершины до корня в этом каркасе является кратчайшим путем между этими вершинами во всем графе.
Теорема о BFS-дереве. Любое BFS-дерево является деревом кратчайших путей.
Таким образом, однократным выполнением поиска в ширину можно найти кратчайшие пути и расстояния от данной вершины до всех остальных.
Центр дерева. Центр дерева можно найти следующим образом. Выберем в данном дереве произвольную вершину . Выполнив поиск в ширину из вершины , найдем наиболее удаленную от нее вершину . Выполнив второй раз поиск в ширину со стартом в вершине , найдем наиболее удаленную от нее вершину . Центр пути, соединяющего и , является центром всего дерева.

Поиск в глубину

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

Обозначим стек для открытых вершин через S, а верхний элемент стека – через . Тогда процедура обхода одной компоненты связности методом поиска в глубину со стартовой вершиной a может быть записана следующим образом (DFS – от Depth First Search).
Procedure DFS(a)

посетить a;

2 while do

3 ;

4 if имеются неисследованные ребра, инцидентные вершине

5 then выбрать такое ребро ;

6 if y новая then посетить y

7 else удалить из S

При посещении вершина помечается как посещенная и помещается в стек.

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

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

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

Теорема о DFS-дереве. Относительно DFS-дерева все обратные ребра являются продольными.
На этом свойстве основаны многие применения поиска в глубину. Рассмотрим некоторые из них.
Шарнир. Допустим, требуется выяснить, является ли шарниром некоторая вершина х данного графа (предположим, что он связный). Для решения этой задачи достаточно выполнить поиск в глубину со стартом в вершине х и построением DFS-дерева. Если теперь вершину х удалить из графа, то, ввиду отсутствия поперечных ребер, он распадется на столько компонент связности, сколько сыновей у вершины х в DFS-дереве. Значит, вершина х является шарниром тогда и только тогда, когда она имеет в DFS-дереве с корнем х степень 2 или больше.
Все шарниры. Однократным поиском в глубину можно найти все шарниры графа. Будем нумеровать вершины при обходе графа в том порядке, в котором они посещаются. Номер, полученный вершиной , обозначим через , он называется глубинным номером. Введем на множестве вершин еще одну функцию L, связанную с DFS-деревом: значением является наименьший из глубинных номеров вершин, смежных с потомками вершины х. Если вершина y является сыном вершины x, то (так как вершина y является потомком самой себя и смежна с вершиной x).
Теорема о шарнирах. Корень DFS-дерева является шарниром графа тогда и только тогда, когда его степень в этом дереве больше 1. Вершина x, отличная от корня, является шарниром тогда и только тогда, когда у нее в DFS-дереве имеется такой сын y , что .
Функцию L можно определить рекурсивно – если мы знаем ее значения для всех сыновей вершины x и глубинные номера всех вершин, смежных с x и не являющихся ее сыновьями, то есть минимум из всех этих величин, то есть
,
где A обозначает множество всех сыновей вершины x, а B – множество всех остальных вершин, смежных с x. Ниже приведена основанная на этом равенстве процедура вычисления функции и выявления шарниров для одной компоненты связности. Вначале каждой вершине присвоен нулевой глубинный номер и это нулевое значение используется затем как признак того, что вершина новая. Переменная c хранит текущий глубинный номер, вначале . Предполагается, что окрестность каждой вершины реализована в виде списка и запись означает, что в качестве берется очередная вершина из списка и при этом вершина из списка удаляется.
Procedure Шарниры(a)
1 посетить(а);

2 while do

3 ;

4 if

5 then ;

6 if

7 then посетить( y)

8 else

9 else ;

10 if

11 then ;

12 if then ;

13 if then пометить х как шарнир
Procedure посетить( x)
1 ;

2 ;

3 ;

Этот алгоритм находит все шарниры, кроме стартовой вершины а (если она является шарниром). Из теоремы видно, что эта вершина должна обрабатываться особо – нужно просто отслеживать ее степень в DFS-дереве. Это не включено в описание алгоритма, чтобы не загромождать его.
Блоки. Блок графа – это его максимальный связный подграф, не имеющий собственных шарниров (т.е. некоторые шарниры графа могут принадлежать блоку, но своих шарниров у блока нет). Каждое ребро графа принадлежит в точности одному блоку, а вершина может принадлежать нескольким блокам, но только в том случае, когда она – шарнир. Строение связного графа G, состоящего из нескольких блоков, описывается BC-деревом, которое строится следующим образом. В этом дереве вершины двух типов – одни соответствуют блокам графа G (вершины-блоки), другие – его шарнирам (вершины-шарниры). Вершина-блок соединяется в BC-дереве ребром с вершиной-шарниром, если соответствующий шарнир принадлежит соответствующему блоку.

Описанный выше алгоритм выявления шарниров нетрудно приспособить для отыскания всех блоков графа. Достаточно завести еще один стек и складывать в него все посещаемые вершины. При обнаружении шарнира x (строка 13) достаточно извлечь из стека все вершины, содержащиеся в его верхней части вплоть до вершины y и добавить к ним еще вершину x (не удаляя ее, в отличие от других, из стека). Это множество вершин образует очередной блок.

Задачи

4.1. Используя метод поиска в ширину, найдите компоненты связности графа, заданного

матрицей смежности:

Методом поиска в ширину постройте дерево кратчайших путей из вершины 1 для

графа, заданного списками смежности:

1: 2,9; 3: 2, 7; 5: 4, 6, 7, 9, 10; 7: 2, 3, 5, 6, 8; 9: 1, 4. 5, 8, 10;

2: 1, 3, 7, 8; 4: 5, 9; 6: 5, 7, 10; 8: 2, 7, 9; 10: 5, 6, 9
4.3. Лес задан списками смежности. Какие из следующих оценок времени работы верны

для поиска в ширину?

1) ; 2) ; 3) ; 4) ; 5) .
4.4. Лес задан матрицей смежности. Какие из следующих оценок времени работы верны

для поиска в ширину?

1) ; 2) ; 3) ; 4) ; 5) .
4.5. Какова будет высота BFS-дерева, если поиск в ширину применяется к графу

1) ; 2) , ; 3) ; 4) ; 5) , старт в вершине степени 2?

4.6. Пусть h –высота BFS-дерева для графа G. Может быть ? ?

Всегда ли можно выбрать стартовую вершину так, чтобы было ?

?
4.7. Ребро является обратным ребром относительно BFS-дерева с корнем . Какие

из следующих соотношений могут выполняться? А если граф двудольный?

1) ; 3) ;

2) ; 4) .

4.8. Два человека имеют восьмилитровый кувшин, наполненный вином, и два пустых

кувшина:

а) трехлитровый и двухлитровый;

б) пятилитровый и шестилитровый.

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

опустеет, либо второй не наполнится. Могут они разделить вино поровну с помощью

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

заданного списками смежности:

1: 2, 4, 6; 3: 5, 9; 5: 3, 9; 7: 8, 10; 9: 3, 5; 11: 8, 12;

2: 1; 4: 1; 6: 1; 8: 7, 10, 11; 10: 7, 8, 12; 12: 10, 11.

Постройте DFS-дерево с корнем в вершине 1 для графа, заданного списками

смежности:

1: 5, 6, 7, 8; 3: 2, 4; 5: 1, 6, 10; 7: 1, 2, 4, 8; 9: 8;

2: 3, 4, 7, 8; 4: 2, 3, 7: 6: 1, 5; 8: 1, 2, 7, 9; 10: 5.
4.11. Планарный граф задан списками смежности. Какие из следующих оценок времени

работы верны для поиска в глубину?

1) ; 2) ; 3) ; 4) ; 5) .
4.12. Планарный граф задан матрицей смежности. Какие из следующих оценок времени

работы верны для поиска в глубину?

1) ; 2) ; 3) ; 4) ; 5) .
4.13. Дерево задано списками смежности. Какие из следующих оценок времени работы

верны для поиска в глубину?

1) ; 2) ; 3) ; 4) ; 5) .
4.14. Сколько различных DFS-деревьев можно построить для графа 1); 2); 3)?
4.15. Пусть h –высота DFS-дерева для графа G. Может быть a)?

б)?

4.16. Какой может быть максимальная высота DFS-дерева, если поиск в глубину

применяется к графу 1) ; 2) ; 3) , ?

4.17. Ребро является обратным ребром относительно DFS-дерева с корнем .

Какие из следующих соотношений могут выполняться ( обозначает расстояние

между вершинами в дереве)? А если граф двудольный?

1) ; 3) ;

2) ; 4) .
4.18. Постройте DFS-дерево и таблицы функций и для графа, заданного списками

смежности:

1: 3, 4 3: 1, 6 5: 2, 7, 11 7: 5, 6, 10, 11 9: 6, 8 11: 5,7,12

2: 5 4: 1, 6 6: 3, 4, 7, 8, 9 8: 6, 9 10: 7 12: 11.

Найдите все шарниры и блоки этого графа, постройте BC-дерево.
4.19. Каждый блок графа состоит из трех вершин. Сколько вершин и ребер в этом графе,

если его BC-дерево представляет собой а) путь ; б) путь ; в) граф ?

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

деревом.
4.21*. Разработайте алгоритм, проверяющий, является ли данный граф двудольным.

4.22*. Разработайте алгоритм, который находит кратчайший цикл, проходящий через

данную вершину.

4.23*. Докажите, что описанный выше алгоритм нахождения центра дерева с помощью

двойного обхода в ширину действительно находит центр любого дерева.

Приведите пример графа, для которого это не так.
4.24*. Доработайте алгоритм выявления шарниров так, чтобы он правильно обрабатывал

корень DFS-дерева (т.е. решал, является ли эта вершина шарниром).

4.25*. Разработайте алгоритм, определяющий, является ли данное ребро перешейком

графа.
4.26*. Разработайте алгоритм выявления всех перешейков графа.

4.27*. (Задача об одностороннем движении) Докажите, что ребра обыкновенного графа

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

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

ориентации.

следующая страница >>