6.13. Листы и блоки

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

6.13.1. Листы

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

• Определение. Ребро называется разделяющим ребром (или мостом, или разрезающим ребром) в если в графе получающемся после удаления ребра , вершины х и у не связаны. Тогда граф можно представить как объединение графов

где содержит содержит у.

• Утверждение 6.13.1. Ребро является разделяющим тогда и только тогда, когда оно не является циклическим. Доказательство. Допустим, что разделяющее ребро и является циклическим. Тогда после его удаления вершины х и у останутся связанными, а значит, разложение (6.13.1) невозможно, что противоречит условию: — разделяющее ребро. Теперь не циклическое ребро, т.е. не существует цепей, соединяющих х и у и не содержащих и. Отсюда и — разделяющее ребро.

• Определение. Будем говорить, что две вершины циклически-реберно связаны, если существует такая последовательность простых циклов что и каждая пара соседних циклов имеет хотя бы одну общую вершину. Условно взаимное расположение вершин и циклов можно представлять так, как показано на рис. 6.36.

Рис. 6.36. Вершины циклически-реберно связаны

• Утверждение 6.13.2. Циклически-реберная связность определяет отношение эквивалентности (см. п.6.4) на множестве вершин графа На рис 6.37 показано разбиение на компоненты циклически—реберной связности.

Рис. 6.37. Компоненты циклически-реберной связности графа. Компоненты связности графа. Компоненты связаны мостами

• Определение. Множество всех вершин, циклически—реберно связанных с данной вершиной х, называется листовым множеством которому принадлежит х. Отметим, что листовое множество может состоять только из одной вершины х, тогда листовое множество называется особым. Далее будет показано, что это возможно тогда и только тогда, когда все ребра, инцидентные вершине х, являются петлями или разделяющими ребрами.

• Определение. Подграф определяемый листовым множеством называется листом.

• Утверждение 6.13.3. Отметим следующие очевидные свойства листа

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

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

3. Все ребра в являются циклическими. Пусть ребро лежит в Покажем, что оно циклическое. Действительно, если, например, вершины соединены ребром, тогда циклическое по построению Если же не соединены ребром, то, добавив данное ребро к

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

6.13.2. Блоки

• Определение. Пусть неориентированный граф. Два ребра называются сильно циклически связанными, если существует такая последовательность простых циклов что и и любая пара соседних циклов имеет, по крайней мере, одно общее ребро. Условно взаимное расположение ребер и циклов можно представлять так, как показано на рис. 6.38.

Рис. 6.38. Сильно циклически связанные ребра

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

• Лемма 6.13.1. Два ребра сильно циклически связаны тогда и только тогда, когда существует простой цикл, содержащий оба эти ребра. Справедливость данного утверждения следует непосредственно из структуры сильно циклической связанности ребер (рис. 6.38).

• Лемма 6.13.2. Если — простая цепь, связывающая две различные вершины блокового множества, то все ребра цепи принадлежат блоку Доказательство. Если предположить, что утверждение леммы

не выполняется, то существует участок цепи , ребра которого не принадлежат данному блоку Не уменьшая

общности, будем считать, что этим участком является исходная цепь Р(х, у). Так как то в блоке существует простая цепь связывающая х, у. Тогда объединение простых цепей составит простой цикл. Согласно лемме 6.13.1, ребра этого цикла будут сильно циклически связаны, а значит, все ребра простой цепи Р(х, у) должны лежать в что противоречит предположению.

• Утверждение 6.13.4. Из леммы 6.13.2 следует, что блок является подграфом. Он циклически сильно замкнут, в том смысле, что если простой цикл С имеет хотя бы две вершины, общие с то все ребра цепи С принадлежат Поэтому два различных блока могут иметь не более одной общей вершины (рис. 6.39). В противном случае блоки должны совпадать.

Рис. 6.39

• Утверждение 6.13.5. Из определения блокового множества следует, что все его вершины являются циклически-реберно связанными при условии, что число ребер в блоке более одного. Отсюда заключаем, что где листовое множество вершин и каждый лист имеет непересекающееся по ребрам разложение

на семейство блоков.

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

Рис. 6.40

Прямое по ребрам разложение графа

• Утверждение 6.13.6. Блок не имеет разделяющих вершин, так как все его вершины циклически-реберно связаны. На основании разложения (6.13.2) любого листа на непересекающееся по ребрам разложение на блоки и последнего утверждения, составление листа из блоков может быть представлено какгусообразной фигурой, как на рис. 6.41,

в которой различные блоки соприкасаются в своих соединяющих вершинах. Соединяющие вершины блоков являются разделяющими вершинами графа. Разложение (6.13.2) листов на блоки позволяет теперь уточнить структуру графа (рис. 6.37): каждый лист Гц можно представить в виде кактусообразной схемы (рис. 6.41) составляющих его блоков

6.13.3. Поиск блоков в глубину

Разложение графа на блоки и выделение их имеет важное практическое значение. Иногда недостаточно знать, что граф связен; может интересовать насколько «сильно связен» связный граф.

Рис. 6.41

Рис. 6.42. Исходный граф (а); блоки графа (b); листы (с), (е) и один мост (d); точки сочленения:

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

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

На рис. 6.42 в качестве примера изображен связный граф и его блоки (двусвязные компоненты). Здесь же показано разложение графа на листы.

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

Рис. 6.43. Схематическое изображение графа с шестью блоками и четырьмя точками сочленения

Если начать поиск в глубину, скажем, из вершины то можем перейти из проходя через вершину Из свойства поиска в глубину, все ребра в должны быть пройдены до того, как вернемся в Поэтому состоит в точности из ребер, которые проходятся между входом и выходом из вершины Для других блоков дело обстоит несколько иначе. Так, например, если уйти из а оттуда — в через , то окажемся в пройдя ребра из Если хранить ребра в стеке, то во время прохождения назад из через вершину все ребра будут на верху стека. После их удаления на верху стека останутся ребра и снова продолжим проход блока Таким образом, если можно распознавать точки сочленения во время обхода, то применяя поиск в глубину и храня ребра в стеке в той очередности, в которой они проходятся, можно также определить и блоки (двусвязные компоненты). Ребра, находящиеся на верху стека в момент обратного прохода через точку сочленения, составляют блок.

Реализация рассмотренного подхода выделения блоков графа представлена в алгоритме 6.17. В векторе меток вершин графа фиксируются порядковые номера обхода

соответствующих вершин. В этом случае метка вершины сочленения при входе в блок получит наименьший номер из всех остальных вершин блока. Таким образом, для определения точки сочленения выхода из блока достаточно найти вершину этого блока с минимальной меткой. Свойство циклической замкнутости блока позволяет это сделать лишь на основе вектора меток не привлекая дополнительной информации. На рис. 6.44 схематично представлен блок, где вершина точка входа в блок и точка сочленения. Вершина следующая обследованная вершина блока после Свойство циклической замкнутости блока позволяет утверждать, что существует по крайней мере еще одна вершина у, смежная Рекурсивный характер алгоритма поиска в глубину на графе позволяет утверждать, что в этом случае ребро блока будет пройдено как обратное, и, значит, метка точки сочленения блока будет доступна до выхода из блока по ребру входа Поэтому, сохраняя минимальное значение меток обследованных вершин (включая и по обратным ребрам поиска в глубину), будем проверять при рекурсивном выходе из поиска в глубину совпадает ли это минимальное значение с меткой вершины выхода. Если ответ положительный, то найдена точка сочленения. В алгоритме значения минимальных меток фиксируются в векторе для каждой вершины как наименьшее значение из где у — вершины графа, которые достижимы из х при проходе графа в глубину.

Алгоритм 6.17. Выделение блоков графа

(см. скан)

Рис. 6.44

(см. скан)