Базовые задачи на графах

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

Задача выделения компонент связности графа. Эта задача может быть решена с помощью поиска в глубину или ширину. Пусть поиск начат с вершины s е V. После его окончания, т. е. выделения компоненты связности, содержащей вершину s, следует проверить, все ли вершины графа отмечены. Если все вершины отмечены, то процесс обхода завершить. Если нет, то обход возобновить с любой неотмеченной вершины. Не представляет труда в алгоритме 5.1 предусмотреть вычисление числа k{G) компонент связности исходного графа G и вывод сообщения о начале обхода вершин /-й компоненты, 1 < i < k(G).

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

Задача распознавания дерева. Решение задачи сводится к проверке связности графа и подсчету числа ребер в нем. Напомним, что если исходный (п, л?)-граф связен и т = п - 1, то он является деревом [16].

Задача отыскания остовного дерева. Пусть G = (V, Е) - связный граф и Г - остовной его подграф. Если Т- дерево, то его называют остовным (или стягивающим) деревом графа G. Очевидно, что для каждого связного графа всегда существует остовное дерево: разрушая циклы, т. е. удаляя «лишние» ребра, всегда можно получить остовное дерево. Известно, что число «лишних» ребер в связном (п, »?)-графе G равно k(G) = т - п + 1, где А.((7) - цикломатическое число графа G. В общем случае цикломатическое число графа G с k = k(G) компонентами связности выражается формулой

Легко доказать, что граф ацикличен тогда и только тогда, когда {G) = 0 [16].

Очевидно, что при k(G)> 1 не существует остовного дерева. Если граф G помечен и является деревом, то он имеет единственное остовное дерево Т, совпадающее с самим графом G. В общем случае всякий связный помеченный граф имеет, как правило, несколько различных остовных деревьев. Некоторые из них можно найти, используя поиск в глубину или ширину.

Для построения остовного дерева алгоритм 5.1 необходимо модифицировать следующим образом:

  • - дополнительно к массиву X меток вершин надо формировать одномерный массив Y длины п - V. Для каждой вершины графа запоминать в Y непосредственно предшествующую ей вершину. Так, в пункте 4 следует полагать У[о)]:= и, если о - неотмеченная вершина из N(u), а в пункте 2 для начальной вершины 5 установить У[Д:=0;
  • - в пункте 3, извлекая из Q всякую отличную от s вершину и, создавать и выводить ребро {и, v}, где v= Y[u], Совокупность всех таких п - 1 ребер и образует остовное дерево.

Пример 5.2. Для графа G из примера 5.1 поиск в глубину из вершины 1 дает остовное дерево, изображенное на рис. 5.4. В табл. 5.3 приведены состояния массива Y после обхода вершин для этого дерева.

Рис. 5.4

Таблица 5.3

Вершина

со

Вершина и - предшественница для со

1

0

2

1

3

1

4

5

5

1

6

5

7

5

Из рис. 5.4 видно, что при построении остовного дерева исходный граф G теряет 4 ребра (они отмечены пунктирными линиями). Это соответствует значению цикломатического числа X(G) = 10 - 7 + 1 =4 графа G, для которого я? = 10, п = 7, к— 1.

Задача отыскания остовного леса. Пусть G = (V,E) - произвольный граф, связный или несвязный. Всякий остовной ациклический подграф Т графа G называется его остовным (или стягивающим) лесом. Очевидно, что остовной лес («, /л)-графа с к-k{G) компонентами связности определяется через остовные деревья этих компонент и, следовательно, содержит т = п - к ребер. Таким образом, задача отыскания остовного леса сводится к выделению компонент связности и нахождению для каждой из компонент остовного дерева. Все это можно реализовать с помощью поиска в глубину или ширину.

Задача проверки существования в графе G = (V,E) никла, проходящего через заданное ребро е = , b} е Е. Проверка этого условия эквивалентна проверке наличия (а, 6)-цепи в графе G - е. Последнее можно выполнить, применяя поиск в глубину или ширину из вершины а. Если вершины а и b принадлежат одной и той же компоненте связности графа G - е, то в графе G существует цикл, проходящий через ребро е — {а, Ъ), в противном случае такой цикл не существует.

Задача поиска «узких» мест графа. Вершина v графа G называется точкой сочленения (или разделяющей вершиной), если граф

G - v имеет больше компонент связности, чем G. В частности, если G связен и v- точка сочленения этого графа, то G-v не связен. Аналогично ребро графа называется мостом, если его удаление увеличивает число компонент связности. Таким образом, точки сочленения и мосты - это своего рода «узкие» места графа.

Заметим, что в дереве все вершины, кроме висячих, являются точками сочленения, а все ребра - мостами. Очевидно, что концевая вершина моста является точкой сочленения, если она не является висячей, т. е. в графе есть другие ребра, инцидентные этой вершине.

Пример 5.3. Граф, изображенный на рис. 5.1, имеет одну точку сочленения - вершину с номером 5. Мостов в этом графе нет.

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

Задача распознавания блока. Связный граф без точек сочленения называют блоком. Блоки играют важную роль в теории графов. Ряд задач достаточно уметь решать для блоков. Решение задачи распознавания блоков сводится к проверке связности графа и наличия в нем точек сочленения.

Задача распознавания двудольности графа. Граф G = (V, Е)

называется двудольным, если существует такое разбиение множества его вершин V на две доли VV2 ( V u V2 — V, V n V2 = 0), что концы каждого ребра е е Е принадлежат разным долям. Если G - двудольный граф, то пишут G = (V], V2, Е). Полный двудольный граф - это граф, который содержит все ребра, соединяющие множества V и V2. Если V= p,V2 = q, то полный двудольный граф обозначается Крч.

Необходимые и достаточные условия двудольности графа устанавливает теорема Кенига [14, 16]: граф двудольный тогда и только тогда, когда в нем нет циклов нечетной длины. По теореме Кенига все ациклические графы двудольные.

Пример 5.4. Граф из примера 5.1 не является двудольным, так как он содержит циклы, некоторые из которых имеют длину 3 и 5 (рис. 5.1).

Теорема Кенига подсказывает простой способ распознавания двудольности графа, основанный на поиске в глубину или ширину. Не ограничивая общности, будем полагать, что исходный граф G = (V,E) связен, поскольку каждую компоненту связности можно рассматривать отдельно, ибо дизъюнктное объединение двудольных графов является двудольным графом.

Вначале с помощью алгоритма 5.1 необходимо множество вершин исходного графа разнести по уровням. Здесь номер уровня вершины v - это расстояние от начальной вершины s до вершины v, т. е. длина кратчайшей по числу ребер (5, у)-цепи. Для этого алгоритм 5.1 следует модифицировать следующим образом:

  • - дополнительно к массиву X меток вершин создать одномерный массив Y, в который записывать для каждой вершины графа непосредственно предшествующую ей вершину. В пункте 4 элемент У[со] полагать равным и, если со - неотмеченная вершина из N(u), а в пункте 2 для начальной вершины 5 установить У|У]:= 0;
  • - создать одномерный массив Z, в котором формировать для каждой вершины номер уровня. С этой целью в пункте 3, извлекая из Q всякую отличную от s вершину и, полагать

Это означает, что номер уровня вершины и на единицу выше

уровня её предшественницы - вершины v.

Таким образом, после завершения систематического обхода всех вершин графа каждая из них будет отнесена к некоторому уровню. Далее множество вершин V необходимо разбить на доли V и V2:

  • - все вершины с четными номерами уровней записать в V,
  • - все остальные вершины отнести к V2.

Критерий двудольности такой: если любые две несовпадающие вершины из одной доли не являются смежными, то G - ( V, V2, Е) - двудольный граф. Вообще достаточной является проверка отношения смежности для всех пар вершин с одинаковыми номерами уровней (почему?).

Пример 5.5. Рассмотрим граф G из примера 5.1. Для него поиск в глубину из вершины 1 дает остовное дерево (рис. 5.4) и разносит вершины графа по трем уровням (рис. 5.5). Номера уровней на рис. 5.5

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

Рис. 5.5

Задача о достижимости вершин орграфа. Пусть заданы орграф G-(V,E) и некоторая его вершина s е V. Требуется найти множество всех вершин орграфа, достижимых из s. Говорят, что вершина v достижима из вершины s, если в G существует путь, идущий от вершины 5 к вершине v. Напомним, что путь - ориентированная цепь.

Данная задача решается с помощью алгоритма 5.1. Для орграфа обход вершины следует производить с учетом направленности дуг. Направленность дуг полностью определяется списками смежности орграфа. Обход надо начинать с вершины s. Все вершины, которые удается отметить и пройти, достижимы из 5.

Пример 5.6. Пусть задан орграф G (рис. 5.6).

Рис. 5.6

Требуется выяснить, какие вершины достижимы из вершины 4. На рис. 5.7 и в табл.5.4 приведены результаты обхода орграфа в глубину из вершины 4: ПГ - номера вершин; метки вершин; текущее состояние стека Q. В результате обхода все вершины орграфа оказались отмеченными, а значит, достижимыми из вершины 4.

Таблица 5.4

Вершина и

Стек Q

ПГ-номер

Метка

1*

4

1,2

2*

2

1,3

3*

3

1,5

4*

5

1

5*

1

0

Рис. 5.7

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

Задача проверки существования в орграфе G = (V, Е) контура, проходящего через заданную дугу е = (a, b) е Е. Проверка этого условия равносильна проверке наличия (а, &)-пути в орграфе G - е. Эту проверку можно выполнить, используя поиск в глубину или ширину из вершины Ь. Если вершина а достижима из вершины b в G - е, то в G существует контур, проходящий через дугу {а, Ь). Так, например, в орграфе с рис. 5.6 имеется контур, проходящий через дугу (2, 3). Других контуров в этом орграфе нет.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >