Поиск в глубину в графе

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

2) Все вершины, смежные с , просмотрены. Тогда и объявляется использованной вершиной. Обозначим через ту вершину, из которой мы попали в , т. е. ; ноиск в глубину продолжается из вершины .

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

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

Пусть в обыкновенном графе проведен поиск в глубину. Обозначим через множество всех древесных ребер. Все остальные ребра графа будем называть обратными ребрами. Множество всех обратных ребер обозначим через .

Результат применения поиска в глубину к связному графу (рис.4.4 а) показан на рис. 4.4 b. Здесь сплошные линии изображают древесные ребра, а пунктирные линии ‑ обратные ребра.

Рис. 4.4. a) Связный граф; b) Результат применения поиска в глубину к связному графу.

Нумерация вершин соответствует порядку, в которым они просматриваются поиском в глубину. Можно заметить, что множество всех древесных ребер с выделенной начальной вершиной образует корневое дерево с корнем , которое дерево часто называют глубинным деревом или -деревом графа [5]. Отметим, что каждое обратное ребро соединяет в -дереве предка и потомка.

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

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

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

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

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

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

Изложим версию алгоритма поиска в глубину, основанную на рекурсивной процедуре [6], осуществляющей поиск в глубину из вершины .

Алгоритм поиска в глубину.

1. procedure DFS(v);

2. begin

3. num[v] := i; i := i + 1;

4. for do

5. if then

6. begin

7. ; father[u] := v; DFS(u)

8. end

9. else if num[u] < num[v] and then

10.

11. end;

12. begin

13. i := 1; ;

14. for do ;

15. for do

16. if then

17. begin

18. DFS(v)

19. end

20. end.

4.1.3. Задачи о покрытиях графов.

Задача о реберном покрытии.

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

Покрытие с минимальным числом ребер называется минимальным (оптимальным).

Рассмотрим простой пример графа, изображенного на рис. 4.5.

В этом примере , , номера ребер указаны на рисунке в кружочках. Множество ребер не образует реберное покрытие, так как вершины 2 и 5 не инцидентны ни одному из ребер этого одному из ребер этого множества. Множество ребер (1, 4, 6) образует реберное покрытие.

Рис. 4.5. Пример графа.

Матрица инциденций графа имеет вид

Сформулируем модель целочисленного программирования для поиска минимального покрытия графа. Введем бинарных переменных:

.

Тогда целевая функция имеет вид

,

условия инцидентности для всех вершин запишутся в виде

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

(4.1)

Задача о паросочетаниях. Пусть число вершин графа четно. Под паросочетанием (совершенным) понимается такое множество попарно несмежных ребер, что каждая вершина графа инцидентна одному ребру из этого множества.

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

Здесь

.

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