Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Методы систематического обхода вершин графа

Методы систематического обхода вершин графа


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


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


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


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


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


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


Если же неотмеченных вершин в [math]L[v][/math] нет, то возвращаемся из [math]{v}[/math] в ту вершину, из которой мы в нее попали, и продолжаем анализировать список смежности этой вершины.


"Путешествие" прекратится в тот момент, когда мы вернемся в начальную вершину [math]v_0[/math] и либо все вершины будут отмеченными, либо окажется, что неотмеченные вершины есть, но из [math]v_0[/math] больше никуда пойти нельзя. В последнем случае возможны продолжение поиска из новой вершины или остановка, что определяется конкретной версией алгоритма.


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


На рис. 5.20 показаны примеры поиска в глубину на неориентированном и ориентированном графах.


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

Рассмотрим неориентированный граф, изображенный на рис. 5.20,а. Списки смежности вершин графа удобно задать кортежами:


[math]\begin{cases}v_0\to (v_1,v_3),\quad v_1=(v_0, v_2, v_3),\quad v_2=(v_1, v_4),\\ v_3\to (v_0, v_1, v_4, v_5),\quad v_4\to (v_2, v_3),\\ v_5\to (v_3, v_6, v_7),\quad v_6\to (v_5),\quad v_7\to (v_5). \end{cases}[/math]
(5.1)


Здесь запись [math]v_i\to (v_k,\ldots, v_m)[/math] означает, что кортеж [math](v_k,\ldots, v_m)[/math] задает список смежности вершины [math]v_i[/math].


Результаты работы алгоритма с использованием приведенных списков смежности проиллюстрированы графически. При поиске отмечаем вершины, присваивая им номера. При этом каждая новая вершина получает номер, на единицу больший, чем текущая. Вершине [math]v_0[/math] присвоим номер 1. Номера остальных вершин, присвоенные им в процессе поиска, приведены на графе. Ребра, по которым из текущей вершины переходим к новой, изображены более толстыми линиями.


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


[math]\begin{array}{lll}v_0\to (v_1, v_3),&\quad v_1\to (v_2),&\quad v_2\to(),\\[2pt] v_3\to (v_1, v_4),&\quad v_4\to (v_2),&{} \\[2pt] v_5\to (v_3, v_6, v_7),&\quad v_6\to(),&\quad v_7\to(). \end{array}[/math]

"Путешествие" начинается в вершине [math]v_0[/math], и ей присваивается номер 1. Первой в списке смежности вершины [math]v_0[/math] стоит вершина [math]v_1[/math]. Даем ей номер 2 и продолжаем поиск из этой вершины. В списке смежности последней только одна вершина [math]v_2[/math]. Даем ей номер 3 и, так как ее список смежности пуст, возвращаемся в вершину [math]v_1[/math]. В списке смежности вершины [math]v_1[/math] нет других вершин, кроме вершины [math]v_2[/math], уже помеченной номером 3, поэтому возвращаемся в вершину [math]v_0[/math].


Второй элемент списка смежности вершины [math]v_0[/math] — вершина [math]v_3[/math]. Эта вершина новая. Помечаем ее номером 4 и переходим к рассмотрению ее списка смежности. Первая в списке смежности вершина [math]v_1[/math] уже получила номер 2. Поэтому переходим в новую вершину [math]v_4[/math] и помечаем ее номером 5. Единственный элемент ее списка смежности, вершина [math]v_2[/math], уже отмечена. Возвращаемся в вершину [math]v_3[/math]. Здесь тоже нет никаких "отложенных продолжений", и мы снова оказываемся в стартовой вершине [math]v_0[/math]. Все вершины из списка смежности стартовой вершины уже отмечены, т.е. все возможные пути поиска из этой вершины пройдены. Тем не менее в графе остались непосещенные (непронумерованные) вершины. Следующей по исходной нумерации вершин графа является вершина [math]v_5[/math]. Продолжим поиск из этой вершины и пометим ее номером 6. Первая вершина ее списка смежности —вершина [math]v_3[/math] — уже отмечена. Посещаем следующую вершину — вершину [math]v_6[/math] — и помечаем ее номером 7. Ее список смежности пуст. Возвращаемся в вершину [math]v_5[/math]. Посещаем последнюю неотмеченную вершину из ее списка смежности — вершину [math]v_7[/math] — и помечаем ее номером 8. Поскольку все вершины из списка смежности вершины [math]v_5[/math] отмечены, поиск в глубину закончен.


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


Рассмотрим теперь поиск в ширину. При поиске в ширину "правила игры" такие: достигнув некоторой вершины [math]{v}[/math], отмечаем ее. Затем просматриваем ее список смежности [math]L[v][/math] и отмечаем все ранее не отмеченные вершины списка (при старте поиска [math]v=v_0[/math]). После того как отмечены все вершины из [math]L[v][/math], вершину [math]{v}[/math] считаем полностью обработанной и продолжаем обработку вершин из списка [math]L[v][/math] по очереди согласно описанным правилам.


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


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


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


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

Для неориентированного графа (см. рис. 5.21,а) поиск из стартовой вершины [math]v_0[/math] будем осуществлять так. Стартовой вершине присвоим номер 1. Затем пронумеруем все вершины из списка смежности стартовой вершины в порядке следования их в списке. При этом вершина [math]v_1[/math] получит номер 2, а вершина [math]v_3[/math] — номер 3. Теперь, когда все вершины из списка смежности вершины [math]v_0[/math] отмечены, перейдем в первую по очереди вершину [math]v_1[/math]. В ее списке смежности только одна ранее не отмеченная вершина — [math]v_2[/math]. Присвоим ей номер 4 и перейдем в вершину [math]v_3[/math]. На этом этапе номер 5 получит вершина [math]v_4[/math], а номер 6 — вершина [math]v_5[/math]. Затем перейдем в вершину [math]v_2[/math]. Поскольку все вершины из списка смежности вершины [math]v_2[/math] уже отмечены, перейдем в вершину [math]v_4[/math]. Здесь также все вершины из списка смежности отмечены, поэтому перейдем в вершину [math]v_5[/math]. Просмотрим неотмеченные вершины из ее списка смежности и отметим вершины [math]v_6[/math] и [math]v_7[/math], присваивая им номера 7 и 8 соответственно. Теперь, когда список смежности вершины [math]v_6[/math] обработан полностью, перейдем в вершину [math]v_6[/math]. Так как в ее списке смежности нет неотмеченных вершин, перейдем в вершину [math]v_7[/math]. Здесь также в списке смежности нет неотмеченных вершин. Все вершины обработаны, и поиск в ширину для графа закончен.


Результаты поиска в ширину из вершины [math]v_0[/math] в ориентированном графе представлены на рис. 5.21,б.


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


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


Рассмотрим алгоритм поиска в глубину в неориентированном графе. Будем считать, что граф задан списками смежности, собранными в массив лидеров.


Фундаментальные циклы дерева

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


В процессе обхода будем находить фундаментальные циклы графа. Понятие фундаментального цикла в неориентированном графе вводится следующим образом. Пусть в неориентированном графе [math]G=(V,E)[/math] произвольно фиксирован максимальный остовный лес (см. теорему 5.3). Для связного графа это будет максимальное остовное дерево. Множество его ребер обозначим [math]T[/math]. Все ребра из [math]T[/math] назовем древесными, а ребра исходного графа [math]G[/math], не принадлежащие [math]T[/math], — обратными. Таким образом, фиксируя в графе [math]G[/math] максимальный остовный лес, мы тем самым фиксируем разбиение множества его ребер на подмножества древесных и обратных ребер. В силу максимальности остовного леса любая пара вершин графа [math]G[/math], принадлежащих одной и той же компоненте связности, соединена цепью, все ребра которой являются древесными. Возьмем теперь произвольно две вершины [math]u[/math] и [math]{v}[/math], принадлежащие одной и той же компоненте связности графа [math]G[/math]. Пусть эти вершины соединены обратным ребром. Поскольку они также соединены цепью, содержащей исключительно древесные ребра, то существует цикл, содержащий эти две вершины, в котором будет единственное обратное ребро [math]\{u,v\}[/math]. Любой цикл графа [math]G[/math], содержащий только одно обратное ребро, назовем фундаментальным.


Докажем, что не существует двух различных фундаментальных циклов, содержащих одно и то же обратное ребро (рис. 5.22). Действительно, если предположить противное, то возникает цикл [math]C[/math], содержащий лишь древесные ребра, что невозможно.


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


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved