Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






SearchC(Edge(w, t) ) ;






if (low[w] > low[t]) low[w] = low[t];

if (low[t] == ord[t])

bcnt++; // w-t является мостом } else if (t! = e.v)

if (low[w] > ord[t]) low[w] = ord[t]; } public:

EC(const Graph & G): SEARCH< Graph> (G), bcnt(O), low(G.V(), -1) { search (); }

int count() const { return bcnt+1; } };

В программе 18.7 мы используем поиск в глубину для исследования свойств графа. Разумеется, представление графа оказывает влияние на порядок поиска, но оно никак не влияет на результаты этих исследований, ибо мосты — это характерные особенности фа-


Глава 18. Поиск на графе



РИСУНОК 18.18. ДРУГОЕ ДЕРЕВО DFS, ИСПОЛЬЗУЕМОЕ ДЛЯ ПОИСКА МОСТОВ

На данной диаграмме показано дерево DFS, отличное от дерева, изображенного на рис. 18.17 и построенного для графа, показанного на рис. 18.16, тогда мы начинали поиск с другого узла. Несмотря на то что мы просматриваем узлы и ребра в совершенно другом порядке, мы, тем не менее, обнаружи­ваем одни и те же мосты (что вполне естественно). На этом дереве вершины 0, 7 и 11 — это вершины, для которых значение low равно значению ord, так что ребра, соединяющие каждую из таких вершин с их родителями (соответственно, 12-11, 5-0 и 6-7) являются мостами.

фа, а не выбранный нами способ представления графа или поиска на графе. Как и все­гда, любое дерево DFS - это просто еще одно представление графа, так что все такие деревья обладают одними и теми же свойствами связности. Корректность алгоритма за­висит от этого фундаментального факта. Например, рис. 18.18 представляет собой иллю­страцию другого поиска на том же графе, он начинается с другой вершины и, естествен­но, обнаруживает те же мосты. Вопреки свойству 18.6, в тех случаях, когда мы исследуем различные деревья DFS одного и того же графа, мы убеждаемся, что стоимость того или иного поиска может зависеть не только от свойств графа, но также и от свойств дерева DFS. Например, пространство памяти, необходимое для стека, который обеспечивает поддержку рекурсивных вызовов, больше для примера, представленного на рис. 18.18, чем для примера на рис. 18.17.

Так же, как мы поступили в отношении регулярной связности в программе 18.4, мы, возможно, воспользуемся программой 18.7 для построения класса, выполняющего про­верку, является ли заданный граф реберно-связным, либо подсчитывающего число ребер­но-связных компонент. При необходимости мы можем поступать так же, как и в случае программы 18.4, которая предоставляет клиентам возможность создавать (за линейное время) объекты, способные за постоянное время отвечать на запросы на предмет того, находятся ли две заданные вершины в одной и той же реберно-связной компоненте (см. упражнение 18.36).

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



Часть 5. Алгоритмы на графах


 


резающими вершинами (cut vertex). Мы могли бы воспользоваться термином " связанные вер­шины" для описания графа, в котором нет вершин отделимости, но мы воспользуемся другой терминологией, основанной на родственных понятиях, которые в конечном ито­ге оказываются эквивалентной терминологией. Определение 18.3. Граф называется двухсвязным (biconnected), если каждая пара вершин соединена двумя непересекающимися путями. Требование непересекающихся (disjoint) путей отличает двухвязность от реберной связ­ности. Альтернативное определение реберной связности отличается тем, что каждая пара вершин связана двумя путями, в которых никакие составляющие его ребра не пересека­ются, — эти пути могут иметь общие вершины, но отнюдь не ребра. Двусвязность пред­ставляет собой более сильное условие: реберно-связный граф остается связным, если мы удалим из него какую-нибудь вершину (и все ребра, инцидентные этой вершине). Каж­дый двухсвязный граф есть реберно-связный граф, однако реберно-связный граф не обя­зательно должен быть двухсвязным. Мы также пользуемся термином сепарабелъный (separable) в отношении к графу, который не является двухсвязным, поскольку за счет уда­ления всего лишь одной вершины он может быть разделен на две части. Наличие вершин отделимости являются ключевым свойством двухвязности. Свойство 18.7. Граф двусвязен тогда и только тогда, когда он не содержит вершин от­делимости (точек сочленения). Доказательство:. Предположим, что в графе имеется вершина отделимости. Пусть s и t - две вершины, которые окажутся в двух различных частях графа, если будет уда-

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

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

Определение 18.2. Точка сочленения (articulation point) графа есть вершина, в случае удаления кото­рой связный граф распадается, по меньшей мере, на два непересекающихся подграфа.

Мы будем также называть точки сочленения фа-фа вершинами отделимости {separation vertices) или раз-


РИСУНОК 18.19. ТЕРМИНОЛОГИЯ ОТДЕЛИМОСТИ ГРАФА

Этот граф состоит из двух реберно-связных компонент и одного моста. К тому же реберно-связная компонента, расположен­ная над мостом, является двухсвязной; компонента, расположенная ниже моста, состоит из двух двухсвязных компонент, соединенных друг с другом в точке сочленения.


Глава 18, Поиск на графе



 


графа. Аналогично, для двухсвязной компоненты характерно то, что между любой парой вершин существуют два непересекающихся пути. Можно использовать тот же подход, основанный на алгоритме DFS, который приме­нялся в программе 18.7 для определения, является ли тот или иной граф двухсвязным или нет, и для выявления точек сочленения. Мы не будем рассматривать соответствующий программный код, поскольку он во многом идентичен программе 18.7, за исключением разве что проверки, не является ли корень дерева DFS точкой сочленения (см. упраж­нение 18.44). Разработка программного кода, выполняющего распечатку двухсвязных ком­понент графа, также может послужить хорошим упражнением, которое лишь немного сложнее, чем соответствующая программа для определения реберной связности графа (см. упражнение 18.44). Свойство 18.8. Точки сочленения и двухсвязные компоненты графа можно обнаружить за линейное время. Доказательство: Как и в случае свойства 18.7, этот факт непосредственно следует из того, что решение упражнений 18.43 и 18.44 предусматривает внесение некоторых не­больших изменений в поиск в глубину, из которых вытекает необходимость несколь­ких проверок каждого ребра, выполняемых за постоянное время. ■ Определение 18.4. Граф называется k-связным (k-connected), если существуют, по мень­шей мере, к непересекающихся по вершинам путей, соединяющих каждую пару вершин гра­фа. Вершинная связность (vertex connectivity) графа есть минимальное число вершин, ко­торые нужно удалить, чтобы разделить этот граф на две части.

лена вершина отделимости. Все пути, связывающие s и /, должны проходить через вершину отделимос­ти, вследствие чего рассматриваемый граф не может быть двухсвязным. Доказательство в обратном на­правлении намного труднее и может быть предложе­но в качестве упражнения математически подготов­ленным читателям (см. упражнение 18.40). ■

Мы убедились в том, что можем разбить множество ребер несвязного графа на совокупность связных под­графов и что можем разбить ребра графа, не относяще­гося к категории реберно-связных, на множество мос­тов и реберно-связных подграфов (которые соединены между собой мостами). Аналогично, мы можем разбить любой граф, не относящийся к числу двухсвязных, на множество мостов и двухсвязных компонент {biconnected components), каждая из которых представляет собой двухсвязный подграф. Двухсвязные компоненты и мосты нельзя рассматривать как подходящее разбиение графа, поскольку точки сочленения могут входить во многие связные компоненты (см., например, рис. 18.20). Двухсвязные компоненты присоединены к графу в точках расчленения, возможно, через мосты.

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


РИСУНОК 18.20. ТОЧКИ СОЧЛЕНЕНИЯ (ВЕРШИНЫ ОТДЕЛИМОСТИ)

Данный граф не принадлежит к числу двухсвязных графов. Вершины 0, 4, 5, 6, 7 и 11 (заштрихованы) представляют собой точки сочленения. Рассматриваемый граф содержит пять двухсвязных компонент: одна из них состоит из ребер 4-9, 9-11 и 4-11, другая — из ребер 7-8, 8-10 и 7-10; еще одна -из ребер 0-1, 1-2, 2-6 и 6-0; следующая - из ребер 3-5, 4-5 и 3-4; и наконец, одиночная вершина 12. Если добавить в граф ребро, соединяющее вершину 12 с верши­нами 7, 8 или 10, получается двухсвязный граф.


 

130 Часть 5. Алгоритмы на графах


В этой терминологии " 1-связный" есть ни что иное как " связный", а " 2-связный" — это то же, что и " двухсвязный". Граф с точкой сочленения обладает вершинной связностью, равной 1 (или 0), так что, как утверждает свойство 18.7, граф 2-связен тогда и только тог­да, когда значение его вершинной связности не меньше 2. Особый случай классическо­го результата теории графов, известный как теорема Уитни {Whitney's theorem) утвержда­ет, что граф k-связен в том и только том случае, когда его вершинная связность не меньше к. Теорема Уитни непосредственно следует из теоремы Менгера (Menger's theorem) (см. раздел 22.7), согласно которой минимальное число вершин, удаление которых при­водит к утрате связи между некоторыми двумя вершинами, равно максимальному числу путей, не имеющих общих вершин (чтобы доказать теорему Уитни, нужно применить те­орему Менгера к каждой паре вершин).

Определение 18.5. Граф называется k-реберно-связным (к—edge-connected), если суще­ствуют, по меньшей мере, к путей, которые не имеют общих ребер, соединяющих каждую пару вершин графа. Реберная связность (edge connectivity) графа есть минимальное число ребер, которые нужно удалить, чтобы разделить этот граф на две части.

В этой терминологии " 1-реберно-связный" есть ни что иное как " реберно-связный" (т.е. для реберно-связного графа значение реберной связности не меньше 1). Другой ва­риант теоремы Менгера утверждает, что минимальное число вершин в графе, удаление которых приводит к разрыву связи между некоторыми двумя вершинами графа, равно максимальному числу путей, не имеющих общих вершин и связывающих эти две верши­ны графа. Отсюда следует, что рассматриваемый граф к— реберно-связен тогда и только тогда, когда его реберная связность равна к.

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

st-связность. Каким является минимальное число ребер, удаление которых приведет к разделению двух конкретных вершин s и t заданного графа? Чему равно минимальное число вершин, удаление которых приведет к разделению двух заданных вершин s и t за­данного графа?

Общая связность. Является ли заданный граф k-связным? Является ли заданный граф k-реберно-связным? Какой является реберная связность и вершинная связность заданного графа?

И хотя решения всех этих задач намного сложнее, чем решения простых задач связ­ности, рассмотренных в данном разделе, они, тем не менее, входят в обширный класс задач обработки графов, которые мы можем решать с помощью универсальных алгорит­мических средств, изучением которых займемся в главе 22 (при этом важную роль игра­ет поиск в глубину); конкретные решения будут изучаться в разделе 22.7.


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.008 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал