Графы блоков и точек сочленения

Блоки

 

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

 

 

 

 

Известны несколько графов пересечений, получаемых из графа G, которые представляют его структуру. Возьмем блоки графа G в качестве множеств семейства F. Тогда граф пересечений W (F) называется графом блоков графа G и обозначается через В(G). Блоки графа G соответствуют вершинам графа B(G), и две вершины графа В(G) смежны тогда и только тогда, когда соответствующие им блоки графа G имеют общую точку сочленения. Для получения графа, вершины которого соответствуют точкам сочленения графа G, возьмем в качестве множества Si (из семейства F) объединение всех блоков, содержащих данную точку сочленения vi. Полученный с использованием этого семейства F граф пересечений W(F) называется графом точек сочленения и обозначается C(G). Две вершины графа C(G) смежны тогда и только тогда, когда соответствующие им точки сочленения графа G принадлежат одному блоку. Заметим, что С(G) определяется только для графов G, имеющих хотя бы одну точку сочленения.

 

Определенные выше понятия иллюстрируются на рисунке

Теорема. Граф Н является графом блоков некоторого графа тогда и только тогда, когда каждый блок графа Н - полный граф.

Доказательство. Пусть H=B(G); предположим, что в Н есть блок Нi не являющийся полным графом. Тогда в Hi найдется пара несмежных вершин, лежащая на одном простом цикле Z, длина которого не меньше 4. Отсюда следует, что объединение блоков графа G, соответствующих тем вершинам из Hi, которые лежат на Z, является связным графом, не имеющим точек сочленения, т. е. это объединение содержится в некотором блоке, что противоречит свойству максимальности блока графа.

Обратно, пусть Н — граф, в котором каждый блок — полный граф. Образуем граф В(Н), а затем новый граф G, добавляя к каждой вершине Hi, графа В(Н) некоторое количество концевых ребер, равное числу тех вершин блока НГ, которые не являются точками сочленения графа H. Легко видеть, что граф В(G) изоморфен H.

Ясно, что подобный критерий справедлив для графов точек сочленения.