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

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

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

Procedure DFS(a)

1 Посетить(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 ;

4

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

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

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

Задачи

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

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

4.2. Методом поиска в ширину постройте дерево кратчайших путей из вершины 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.

4.10. Постройте 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 9: 6, 8 11: 5,7,12

2: 5 4: 1, 6 6: 3, 4, 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*. (Задача об одностороннем движении) Докажите, что ребра обыкновенного графа

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

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

ориентации.

Циклы

Эйлеровы циклы

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

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

Следствие (об эйлеровом пути). Эйлеров путь в связном графе существует тогда и только тогда, когда в нем имеется не более двух вершин нечетной степени.

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