Блоки

Теорема 1. В двусвязном графе любые два различных элемента циклически связаны. Если в графе любые два ребра циклически связаны, то он двусвязен.

Доказательство. Докажем сначала, что в двусвязном графе $$G$$ для любых двух различных вершин $$a$$ и $$b$$ имеется простой цикл, проходящий через обе эти вершины. Доказательство проводим индукцией по расстоянию между $$a$$ и $$b$$. Если $$d(a,b)=1$$, то $$a$$ и $$b$$ смежны. Ребро $$(a,b)$$ не является перешейком (иначе хотя бы одна из вершин $$a$$, $$b$$ была бы шарниром). Но тогда в графе имеется простой цикл, проходящий через это ребро. Пусть $$d(a,b)>1$$. Рассмотрим кратчайший путь из $$a$$ в $$b$$, и пусть $$x$$ - предпоследняя вершина этого пути. Тогда $$d(a,x) = d(a,b)-1$$ и, по предположению индукции, существует простой цикл $$C$$, содержащий вершины $$a$$ и $$x$$. Так как вершина $$x$$ - не шарнир, то существует простой путь $$P$$ из $$b$$ в $$a$$, не проходящий через $$x$$. Пусть $$y$$ - первая вершина этого пути, принадлежащая $$C$$ (такая существует, так как $$a \in C$$. Тогда отрезок пути $$P$$ от $$b$$ до $$y$$ вместе с отрезком цикла от $$y$$ до $$x$$, содержащим вершину $$a$$, и с ребром $$(x,b)$$ образует простой цикл, содержащий обе вершины $$a$$ и $$b$$ (показан стрелками на рис. 6.2).

Теперь покажем, что для любой вершины $$a$$ и любого ребра $$(x,y)$$ двусвязного графа $$G$$ в нем имеется цикл, содержащий эту вершину и это ребро. Как доказано выше, существует простой цикл $$C_1$$, содержащий вершины $$a$$ и $$x$$. Если этот цикл проходит и через $$y$$, то, заменив в нем отрезок от $$x$$ до $$y$$, не содержащий $$a$$, ребром $$(x,y)$$, получим простой цикл, проходящий через вершину $$a$$ и ребро $$(x,y)$$. В противном случае возьмем цикл $$C_2$$, содержащий вершины $$a$$ и $$y$$. Кратчайший отрезок этого цикла, соединяющий $$y$$ с какой-либо вершиной $$z$$ на $$C_1$$, вместе с отрезком цикла $$C_1$$ от $$z$$ до $$x$$, содержащим вершину $$a$$, и с ребром $$(x,y)$$ образует простой цикл, содержащий это ребро и вершину $$a$$.

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

Остается доказать, что если в графе $$G$$ через любые два различных элемента проходит простой цикл, то этот граф - двусвязный. Действительно, допустим, что вершина $$a$$ - шарнир графа $$G$$. Возьмем вершины $$x$$ и $$y$$, смежные с $$a$$ и принадлежащие разным компонентам связности графа, получающегося при удалении вершины $$a$$. Тогда в $$G$$ не существует цикла, содержащего оба ребра $$(a,x)$$ и $$(a,y)$$.

Теорема 2. Для любого графа отношение циклической связанности ребер является отношением эквивалентности.

Доказательство. Остается доказать транзитивность этого отношения. Пусть $$C_{1}$$ - простой цикл, содержащий ребра $$e_{1}$$ и $$e_{2}$$, а $$C_{2}$$ - простой цикл, содержащий ребра $$e_{2}$$ и $$e_{3}$$ ; покажем, что существует простой цикл, содержащий ребра $$e_{1}$$ и $$e_{3}$$. Если $$e_{1}$$ принадлежит $$C_{2}$$, то последний и является этим циклом. Если же $$e_{1}$$ не принадлежит $$C_{2}$$, то в $$C_{1}$$ есть отрезок $$P_{1}$$, включающий $$e_{1}$$, у которого концевые вершины $$a$$ и $$b$$ принадлежат $$C_{2}$$, а все внутренние вершины не принадлежат $$C_{2}$$. Пусть $$P_{2}$$ - отрезок цикла $$C_{2}$$, концами которого являются $$a$$ и $$b$$ и который включает ребро $$e_{3}$$. Соединение $$P_{1}$$ и $$P_{2}$$ дает простой цикл, содержащий $$e_{1}$$ и $$e_{3}$$.

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

Доказательство. Пусть $$B_1$$ и $$B_2$$ - различные блоки графа $$G$$. Рассмотрим подграф $$B = B_1 \cup B_2$$. Он не является блоком, следовательно, или несвязен, или имеет шарнир. Если $$B$$ несвязен, то $$B_1$$ и $$B_2$$ - его компоненты связности и, следовательно, не имеют общих вершин. Если же $$B$$ связен и $$a$$ - шарнир в $$B$$, то после удаления вершины $$a$$ граф $$B$$ распадается на компоненты связности. При этом все вершины подграфа $$B_1$$, отличные от $$a$$, принадлежат одной компоненте, иначе $$a$$ была бы шарниром в $$B_1$$. То же верно для вершин подграфа $$B_2$$. Значит, имеется всего две компоненты, одна из которых состоит полностью из вершин графа $$B_1$$, другая - из вершин графа $$B_2$$. Следовательно, $$a$$ - единственная общая вершина $$B_1$$ и $$B_2$$.

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

Теорема 4. Пусть $$x=F(y)$$ в DFS-дереве $$T$$. Ребро $$(x,y)$$ является начальным ребром некоторого блока тогда и только тогда, когда $$\Low(y)=\Dnum(x)$$.

Доказательство. Если $$x=a$$, то для каждого сына $$y$$ вершины $$x$$ имеет место равенство $$\Low(y)=\Dnum(x)$$ и ребро $$(x,y)$$ является начальным ребром некоторого блока.

Пусть $$x\ne a$$ и $$(x,y)$$ - начальное ребро блока $$B$$. Предположим, что $$\Low(y)\ne \Dnum(x)$$. Это означает, что имеется ребро, соединяющее некоторого потомка вершины $$y$$ с собственным предком вершины $$x$$. Но тогда ребра $$(x,y)$$ и $$(x,F(x))$$ оказываются циклически связанными, а отсюда следует, что вершина $$F(x)$$ принадлежит блоку $$B$$. Но это противоречит тому, что $$x$$ - начальная вершина блока, так как $$\Dnum(F(x)) \lt \Dnum(x)$$.

Обратно, пусть $$\Low(y)=\Dnum(x)$$. Тогда вершина $$x$$ является шарниром графа. Рассмотрим поддерево, состоящее из всех потомков вершины $$y$$. Ни одна из вершин этого поддерева не смежна ни с одной отличной от $$x$$ вершиной вне поддерева. Значит, все вершины блока, содержащего ребро $$(x,y)$$, принадлежат этому поддереву, и $$(x,y)$$ - начальное ребро этого блока.