Алгоритмы на графах

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

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

Числом вершинной связности  δ(G) графа называется наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу. Числом реберной связности δ(G) называется наименьшее число ребер, при удалении которых граф становится несвязным. δ^*(G) < δ^*(G) < p^*(G), где p^*(G) – минимальная степень вершин графа.

Вершина х_i называется точкой сочленения (или разделяющей вершиной), если после ее удаления граф становится не связным. Ребро графа называется мостом, если его удаление приводит к несвязному графу.

 

1.4 Обход в ширину и в глубину в графе

 

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

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

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

 Существуют две основные  стратегии таких обходов: поиск в глубину  и  поиск в ширину. Эти стратегии можно описать так:

при поиске в глубину, отправляясь  в «путешествие» по графу из некоторой  начальной вершины  v0, мы действуем следующим образом. Пусть, «путешествуя» , мы достигли некоторой вершины v0  (в начале «путешествия» v = v0). Отмечаем вершину v  и просматриваем вершины из ее списка смежности L[v].

При условии, что в этом списке существует хотя бы одна неотмеченная вершина, продолжаем «путешествие»  из первой такой вершины w, действуя как описано выше – «ныряем» вглубь, т.е. просматриваем вершины списка смежности L[w]  вершины w, откладывая анализ других элементов L[v]  как возможных продолжений поиска «на потом».

Если же неотмеченных вершин в L[v]   нет, то возвращаемся из  v

в ту  вершину, из которой  мы в нее попали, и продолжаем анализировать  список смежности  этой вершин.

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

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

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

Пример поиска в глубину  на неориентированном и ориентированном  графах:

 

 

 

 

 

 

 

Рисунок 1.4 – Пример поиска в глубину на ориентированном и неориентированном графах

 

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

v0→(v1, v3),    v1→(v2),     v2→( ),

 

v3→(v1, v4),    v4→(v2),

 

v5→(v3, v6, v7),    v6→( ), v7→( ).

 

«Путешествие» начинается в  вершине  v0,  и ей присваивается номер 1.  Первой в списке смежности вершины v0  стоит вершина v1.

Даем ей номер 2 и продолжаем поиск из этой вершины. В списке смежности  последней только одна вершина  v2.  Даем ей номер 3 и, так как ее список смежности пуст, возвращаемся в вершину v1.

В списке смежности вершины  v1, нет других вершин, кроме вершины v1, нет других вершин, кроме вершины v2, уже помеченной номером 3, поэтому возвращаемся в вершину v0.

Второй элемент списка смежности вершины  v0  - вершина v3.

Это вершина новая. Помечаем ее номером  4  и  переходим к  рассмотрению ее списка смежности. Первая в списке смежности вершина  v1  уже получила номер 2. Поэтому переходим в новую вершину v4  и помечаем ее номером 5. Единственный элемент ее списка смежности, вершина v2, уже отмечена. Возвращаемся в вершину v3. Здесь тоже нет никаких «отложенных продолжений»,

И мы снова оказываемся  в  стартовой   вершине  v0. Все вершины из списка смежности стартовой вершины уже отмечены, т.е. все возможные пути поиска из этой  вершины пройдены. Тем не менее в графе остались непосещенные (непронумерованные) вершины. Следующей по исходной нумерации вершин графа является вершина  v5. Продолжим поиск из этой вершины и пометим ее номером 6. Первая вершина ее списка смежности – вершина v3 –уже отмечена. Посещаем следующую вершину – вершину v6 – и помечаем ее номером 7. Ее список смежности пуст. Возвращаемся в вершину v5. Посещаем последнюю неотмеченную вершину из ее списка смежности – вершину v7  - и помечаем ее номером 8. Поскольку все вершины из списка смежности вершины v5  отмечены, поиск в глубину закончен.

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

Рассмотрим теперь поиск  в ширину. При поиске в ширину «правила игры» такие: достигнув  некоторой вершины v , отмечаем ее. Затем просматриваем ее список смежности L[v]  и отмечаем все ранее не отмеченные вершины списка ( при старте поиска  v =v0 ).

После того как отмечены все вершины из L[v], вершину v  считаем полностью обработанной и продолжаем обработку вершин из списка L[v] по очереди согласно описанным правилам.

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

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

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

Для неориентированного графа  поиск из стартовой вершины  v0

будем осуществлять так. Стартовой  вершине присвоим номер 1. Затем пронумеруем  все вершины из списка смежности  стартовой вершины в порядке  следования их в списке. При этом вершина  v1 получит номер 2, а вершина  v3    - номер 3.  Теперь, когда все вершины из списка смежности вершины v0  отмечены, перейдем в первую по очереди вершину v1 . В ее списке смежности только одна ранее не отмеченная вершина - v2 . Присвоим ей номер 4  и перейдем в вершину v3 . На  этом этапе номер 5 получит вершина v4,  , а номер 6  - вершина v5 . Затем перейдем в вершину v2. Поскольку все вершины из списка смежности вершины v2  уже отмечены, перейдем в вершину v4 . Здесь также все вершины из списка смежности отмечены, поэтому перейдем в вершину v5. Просмотрим неотмеченные  вершины из ее списка смежности и отметим вершины v6  и v7, присваивая им номера 7  и 8  соответственно. Теперь, когда список смежности вершины   v5  обработан полностью, перейдем в вершину v6. Так как в ее списке смежности нет неотмеченных вершин, перейдем в вершину  v7. Здесь также в списке смежности нет неотмеченных вершин. Все вершины обработаны, и поиск в ширину для графа закончен.

 

 

 

 

 

 

 

 

 

Рисунок 1.5 -  Результаты поиска в ширину из вершины v0 в ориентированном графе

Обратим внимание на то, что  нумерация вершин при поиске в  ширину отличается от нумерации вершин при поиске в глубину. Так, в ориентированном  графе мы сразу отмечаем  оба  элемента списка смежности вершины  v0. Поэтому вершине,  получившей при поиске  в глубину номер 4, при поиске в ширину присваивается номер 3.

Перейдем теперь к подробному описанию алгоритмов поиска в глубину  и поиска в ширину.

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

Слабыми компонентами этого  глубинного остовного леса будут  некоторые ориентированные деревья: поэтому, используемая далее терминология из теории деревьев относится к той  или иной слабой компоненте глубинного остовного леса.

При поиске вершины ориентированного графа грани нумеруются в порядке их посещения. Номер вершины v графа, присваиваемый ей при поиске в глубину, обозначим D[v]  и будем называть

 D-номером. 

Классификация дуг при  поиске в глубину в ориентированном  графе сложнее по сравнению с  аналогичной классификацией ребер  при поиске в глубину в неориентированном  графе.

Различают четыре класса дуг:

1. Древесные дуги – каждая такая дуга ведет от отца к сыну в глубинном остовном лесу;
2. Прямые дуги – каждая такая дуга ведет от подлинного предка к подлинному потомку (но не от отца к сыну) в глубинном остовном лесу;
3. Обратные дуги – от потомков к предкам (включая все петли);
4. Поперечные дуги – все дуги, не являющиеся ни древесными, ни прямыми, ни обратными.

   Следовательно, в результате работы алгоритма будут получены множества  Tree – древесных дуг, Back – обратных дуг, Forward – прямых дуг, С – поперечных дуг и массив D, содержащий D-номера

вершин.

В процессе работы алгоритма  по сравнению с алгоритмом поиска в глубину в неориентированном  графе имеется ряд особенностей. Так, если очередная вершина w, извлеченная из списка смежностей текущей вершины v, новая, т.е. w V0, то дуга (v,w) является древесной. Следует добавить дугу (v ,w) в множество древесных дуг ( Tree = Tree {(v,w)} ), сделать вершину w текущей (v = w)  и начать ее обработку.

Если вершина w не новая (w V0), то дуга (v,w) будет либо прямой, либо обратной, либо поперечной.

Если  D-номер вершины v  строго меньше  D-номера вершины

 w( D[v] < D[w] ), то дуга (v,w) является прямой. Добавляем ее в множество прямых дуг Forward ( Forward = Forward  {(v,w)} ).

Если D-номер вершины v не меньше D-номера вершины w       (D[v] ≥ D[w]), необходимо проверить , есть ли в стеке STACK вершина w. Если вершина w находится в стеке, то дуга (v,w) является обратной и ее следует добавить в множество обратных дуг Back ( Back = Back {(v,w)} ). Если вершины w в стеке нет, то дуга является поперечной. Тогда нужно добавить ее множество поперечных дуг С ( С = С {(v,w)} ). Далее следует перейти к рассмотрению очередной вершины из списка смежности текущей вершины (если он не пуст).

Если стек пуст, но не все  вершины ориентированного графа  обработаны, поиск продолжают из любой  необработанной вершины.

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

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

На базе алгоритма поиска в глубину может быть разработан эффективный алгоритм поиска бикомпонент  в ориентированном графе. Однако здесь мы не будем останавливаться  на задаче поиска бикомпонент, так как  эта задача обсуждается в рамках общей задачи о путях в графах. Можно показать, что алгоритм поиска в глубину имеет сложность порядка max(|V|,|E|).

Пример:

Проведем поиск в глубину на ориентированном графе, представленном на рисунке.

 

Рисунок 1.6 - Поиск в глубину на ориентированном графе

 

Поиск начнем из вершины  v0. Пусть списки смежности вершин имеют следующий вид:

 

    v0→( v2, v3, v1),    v1→( v3),     v2→( v4, v3),

    v3→( v4),    v4→( v1),   v5→( v1),

    v6→( v3, v5),    v7→( v5, v6).

 

Результаты выполнения поиска  в глубину представлены на рисунке: около каждой вершины указан ее D-номер, все древесные дуги выделены более толстыми стрелками, а прямые, обратные и поперечные помечены буквами F, B, C соответственно.

Первое опустошение стека  происходит после обработки первых пяти вершин (в порядке обхода):  v0, v2, v4, v3, v1.

После опустошения поиск  продолжается из вершины   v7, которой присваивается D-номер 6. (Напомним, что в приведенном выше алгоритме после опустошения стека для продолжения поиска выбирается любая из необработанных вершин).