1.7. Точки сочленения и разделимые графы

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

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

Неразделимый граф — это связный граф без точек сочленения. Все другие графы — разделимые (отметим, что несвязный граф также является разделимым графом).

Граф G, представленный на рис. 1.16, а, является разделимым. У него три точки сочленения:

Рис. 1.16. Разделимый граф и его блоки. а — разделимый граф G; б — блоки графа

Блоком разделимого графа G является максимальный неразделимый подграф графа G. Блоки разделимого графа G (рис. 1.16, а) изображены на рис. 1.16, б.

Следующая теорема дает эквивалентное введенному определение точки сочленения.

Теорема 1.5. Вершина v является точкой сочленения связного графа G тогда и только тогда, когда существуют такие две вершины и и w, отличные от и, что вершина v лежит на всяком -пути.

Доказательство.

Необходимость: Если v — точка сочленения в графе G, тогда по определению граф — несвязный. Пусть — одна из компонент и пусть — множество вершин — дополнение . Пусть вершина и находится в а вершина w — в . Рассмотрим в графе G произвольный -путь. Если точка сочленения v не лежит на этом пути, то данный путь находится и в т. е. вершины и и w связаны в Однако это противоречит тому, что и и w находятся в разных компонентах Следовательно, вершина v лежит на любом -пути.

Достаточность: Если v лежит на -пути, то вершины и и не связаны в Таким образом, граф — несвязный. Следовательно, по определению v — точка сочленения.

Как следствие теоремы 1.5 можно дать эквивалентное определение разделимого графа:

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

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

Теорема 1.6. Любой нетривиальный связный граф содержит по крайней мере две вершины, которые не являются точками сочленения.

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

Теперь предположим, что в графе G v есть точка сочленения. Далее, пусть являются -компонентами графа

Если какой-либо граф - является тривиальным, то его единственная вершина не является точкой сочленения. Рассмотрим произвольную нетривиальную компоненту По предположению индукции, содержит вершины и которые не являются точками сочленения. Очевидно, что если одна из этих вершин не смежна в графе G, то эта вершина не является точкой сочленения в G. С другой стороны, если обе вершины и смежны с v в G, то ни ни не будут точками сочленения в

Таким образом, каждая компонента имеет по крайней мере одну вершину, которая не является точкой сочленения в

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