8 Двусвязность Рассмотрим приложение метода поиска в глубину к выделению в неориентированном графе двусвязных компонент. Пусть связный неориентированный граф icon

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


Смотрите также:
7 Остовное дерево наименьшей стоимости Пусть связный неориентированный граф...
Алгоритмы решения задач на графах на основе метода муравьиной колонии...
Это конечный связный граф с выделенной вершиной...
План: Введение...
Лекция №20
3. Лекция: Методы поиска решений...
Приложение №1 45 Приложение №2 46 Приложение №3 47 Приложение №4 48 Приложение №5 49 Приложение...
Экзаменационные вопросы интернет-курсов интуит (intuit): 341...
Метод проектов в начальной школе...
Лабораторная работа №4...
Основные результаты научных исследований математические науки...
Поздравление отцу с рождением дочери...



Загрузка...
скачать

Лекция 08. Алгоритмы на графах


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

Тема 8.1. Двусвязность


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

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

Иначе говоря, – точка сочленения графа , если удаление расщепляет граф не менее чем на две части.

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

Теорема: Неориентированный связный граф двусвязен тогда и только тогда, когда в нём нет точек сочленения.

Будем считать, что на ребрах графа задано отношение эквивалентности. Такое отношение разбивает граф на такие классы эквивалентности , ,…, , что две различных дуги принадлежат одному и тому же классу тогда и только тогда, когда они лежат на общем цикле. Для обозначим через множество узлов, лежащих на дугах из . Каждый граф - называется двусвязной компонентой графа .

Пример:





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




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

Лемма: Пусть для - двусвязные компоненты связного неориентированного графа . Тогда:

  1. граф двусвязен для каждого , ;

  2. для всех содержит не более одного узла;

  3. – точка сочленения графа тогда и только тогда для некоторых .

Алгоритм поиска в глубину особенно полезен для нахождения двусвязных компонент неориентированного графа.

Лемма: Пусть – связный неориентированный граф. – глубинное остовное дерево для него. Узел является точкой сочленения графа тогда и только тогда, когда выполнено одно из условий:

  1. – корень и имеет более одного сына;

  2. – не корень и существует его сын , такой что нет обратных дуг между потомками узла (в том числе самим ) и подлинными предками узла .

П
ример
: Остовное дерево, построенное поиском в глубину для графа, приведённого в предыдущем примере показывает, что точками сочленения являются , , .


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

НИЖНИЙ[] - существует такая обратная дуга , что - потомок узла а – предок узла в глубинном остовном лесу .

Узел – является точкой сочленения тогда и только тогда, когда – не корень и имеет сына , для которого НИЖНИЙ[] >= .

Вход: Связный неориентированный граф .

Выход: Список дуг каждой двусвязной компоненты графа .

Метод:

  1. Полагаем и СЧЕТ = 1. Помечаем каждый узел в как «новый», выбираем произвольный узел в и вызываем ПОИСКБ() чтобы построить глубинное остовное дерево и вычислить НИЖНИЙ[] для каждого .

  2. Когда в строке 5 выбирается узел , помещаем дугу в СТЕК (если его там нет). Когда в строке 10 обнаруживается пара для которой – сын узла и НИЖНИЙ[], выталкиваем из СТЕКа все ребра вплоть до . Эти дуги образуют двусвязную компоненту. Т.к – дуга, то и . Поэтому встречается дважды: один раз, когда посещается узел , и второй раз, когда посещается узел . Узнать, попало ли уже дуга в СТЕК, можно установив, что и – «старый» узел или и = ОТЕЦ[].

Алгоритм:

procedure ПОИСКБ(v)

пометить узел v как «старый»

НОМЕР[v]  СЧЕТ

СЧЕТ++

НИЖНИЙ[v]  НОМЕР[v]

for w  L[ v ] do

if узел w помечен как «новый» then

добавить (v, w) к Т

ОТЕЦ[w]  v

call ПОИСКБ(w)

if НИЖНИЙ[w] >= НОМЕР[v] then Обнаружена двусвязная компонента

НИЖНИЙ[v]  MIN(НИЖНИЙ[v], НИЖНИЙ[w])

else

if w – не ОТЕЦ[v] then НИЖНИЙ[v]  MIN(НИЖНИЙ[v], НОМЕР[w])

end if

next w

end proc


П
ример
: Остовное дерево предыдущего примера. Узлы пронумерованы в соответствии с НОМЕР и указаны значения функции НИЖНИЙ.


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

Пример:

О
пределение
: Прямыми рёбрами в связном ориентированном графе называются рёбра, идущие от подлинных предков к подлинным потомкам, но не являющиеся древесными.

Определение: Поперечными рёбрами в связном ориентированном графе называются рёбра, соединяющие узлы, не состоящие в отношении предок - потомок.

Чтобы построить остовной лес, начнем с узла . ПОИСК () вызывает ПОИСК() , а тот вызывает ПОИСК(). Последний вызов ничего не добавляет к дереву, т.к. единственное ребро с началом идёт в узел , уже помеченный как «старый». Поэтому возвращаемся к ПОИСК(), который добавляет ребро в качестве второго сына узла . ПОИСК() заканчивает работу, ничего не добавляя к лесу, т.к. узел уже «старый». Затем заканчивается ПОИСК(), ибо все рёбра, выходящие из , к данному моменту уже рассмотрены. Поэтому возвращаемся обратно к и вызываем ПОИСК(). Этот вызов ничего не добавляет к дереву. Аналогично ничего уже не может добавить и ПОИСК().

Теперь возьмём в качестве корня нового глубинного остовного дерева. Его построение аналогично предыдущему.
^

Тема 8.2. Сильная связность


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

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

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

Лемма: Пусть сильно связная компонента ориентированного графа , а – глубинный остовной лес для . Тогда узлы графа вместе с рёбрами, входящими в пересечение , образуют дерево.

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

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

Для нахождения корней введём функцию


НИЖНЯЯСВЯЗЬ[] =MIN({}{| есть поперечное или обратное ребро из некоторого потомка узла в узел , а корень той сильно связной компоненты, которая содержит , является предком узла }).

Охарактеризуем корни сильно связных компонент в терминах значения этой функции.

Лемма: Пусть – ориентированный граф. Для того чтобы узел был корнем сильно связной компоненты графа необходимо и достаточно чтобы НИЖНЯЯСВЯЗЬ[] = .

Вход: Ориентированный граф .

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

Алгоритм:

procedure ПОИСКВ(v)

пометить узел v как «старый»

ПГНОМЕР[v]  СЧЕТ

СЧЕТ++

НИЖНИЙ[v]  ПГНОМЕР[v]

затолкнуть v в СТЕК

for w  L[v] do

if узел w помечен как «новый» then

call ПОИСКВ(w)

НИЖНЯЯСВЯЗЬ[v]  MIN(НИЖНЯЯСВЯЗЬ[v], НИЖНЯЯСВЯЗЬ[w])

else

if ПГНОМЕР[w] < ПГНОМЕР[v] и w  СТЕК then

НИЖНЯЯСВЯЗЬ[v]  MIN(ПГНОМЕР[w], НИЖНЯЯСВЯЗЬ[v])

end if

end if

next w

if НИЖНЯЯСВЯЗЬ[v] = ПГНОМЕР[v] then

repeat

вытолкнуть х из СТЕКа;

Print х

until х = v

print «Конец сильно связной компоненты»

end if

end proc

procedure ПОИСК_СИЛЬНО_СВЯЗНЫХ_КОМПОНЕНТ(v)

СЧЕТ  1

for w  V do пометить узел v как «новый»

сделать СТЕК пустым

while существует узел v, помеченный как «новый» do

call ПОИСКВ(v)

end while

next w

end proc


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

Попав в узел в первый раз, полагаем НИЖНЯЯСВЯЗЬ[] = . Когда встречается обратное или поперечное ребро и принадлежит той же сильно связной компоненте, что и некоторый предок узла , то полагаем значение функции НИЖНЯЯСВЯЗЬ в узле равным меньшему из двух чисел: её текущего значения и . Когда встречается древесное ребро рекурсивно просматривается поддерево с корнем и вычисляется НИЖНЯЯСВЯЗЬ[]. По возвращении к значение функции НИЖНЯЯСВЯЗЬ в узле полагается равным меньшему из чисел: её текущего значения и НИЖНЯЯСВЯЗЬ[].

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

Пример:





Вызов ПОИСКВ(3) заканчивает работу первым. Когда мы исследуем ребро (3, 1), полагаем НИЖНЯЯСВЯЗЬ[3] = MIN(3,1) = 1. По возвращении к ПОИСКВ(2) полагаем НИЖНЯЯСВЯЗЬ[2] = MIN(2, НИЖНЯЯСВЯЗЬ[3]). Затем вызываем ПОИСКВ(4) для исследования ребра (4,3). Т.к. 3 < 4 и 3 еще находится в СТЕКе, полагаем НИЖНЯЯСВЯЗЬ[4] = MIN(3,4) = 3.

Затем возвращаемся к вызову ПОИСКВ(2) и полагаем НИЖНЯЯСВЯЗЬ[2] равным меньшему из чисел: НИЖНЯЯСВЯЗЬ[4] и текущего значения НИЖНЯЯСВЯЗЬ [2] (равного 1). Т.к. последнее значение меньше, то НИЖНЯЯСВЯЗЬ[2] не меняется. Возвращаемся к вызову ПОИСКВ(1), полагая НИЖНЯЯСВЯЗЬ[1] = MIN(1, НИЖНЯЯСВЯЗЬ[2]) = 1. Исследовав далее ребро (1, 4), ничего не делаем, ибо (1, 4) – прямое ребро, и условие процедуры ПОИСКВ не выполняется, т.к. 4 > 1.

Теперь вызываем ПОИСК(5), и поперечное ребро (5,4) вынуждает нас положить НИЖНЯЯСВЯЗЬ[5] = 4, ибо 4 < 5 и 4 СТЕК. Когда снова возвращаемся к вызову ПОИСКВ(1), полагаем значение НИЖНЯЯСВЯЗЬ[1] равным меньшему из чисел: 1 (предыдущее значение) и НИЖНЯЯСВЯЗЬ[5], т.е. НИЖНЯЯСВЯЗЬ[1] = 1.

Затем, поскольку все ребра, выходящие из 1, уже рассмотрены и НИЖНЯЯСВЯЗЬ[1] = 1, мы обнаруживаем, что 1 – корень сильно связной компоненты. Эта компонента состоит из 1 и всех узлов, находящихся в стеке выше 1.Т.к. узел 1 посещался первым, то узлы 2, 3, 4 и 5 находятся выше 1 и именно в этом порядке. Поэтому стек опустошается и список узлов 1, 2, 3, 4, 5. Печатается в качестве сильно связной компоненты графа .

Другие сильно связные компоненты – это {7} и {6, 8}.




Скачать 89.51 Kb.
оставить комментарий
Дата04.03.2012
Размер89.51 Kb.
ТипЛекция, Образовательные материалы
Добавить документ в свой блог или на сайт

плохо
  1
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх