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

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

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

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

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

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

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