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. Алгоритмы на графах

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

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

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

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

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

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

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

лена вершина отделимости. Все пути, связывающие 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.