Блоки и точки сочленения.

Пусть G – произвольный граф.

Вершина V называется точкой сочленения графа G, если граф G-V имеет больше компонентов связностей, чем G.

Неразделимый граф G – связный граф, если он не содержит точек сочленения.

Блок графа G – любой его максимальный неразделимый подграф.

U и V – точки сочленения.

Лемма: Пусть V-любая вершина связного графа G. Тогда следующие условия эквивалентны:

1. Вершина V- точка сочленения;

2. такие,что V простой (U,W) цепи;

3. разбиение множества вершин графа (G-V) на два непустых подмножества U и W такое, что для любых вершин u U и w W, вершина v простой (U,W) цепи.

Любые две различные блока связного графа G имеет не более одной общей вершины.

Теорема: 1) пусть b₁ и b₂ – два разлиных блока связного графа G, тогда либо они не пересекаются, либо имеют одну общую вершину, которая является точкой сочленения.

2) пусть V – точка сочленения связного графа G , тогда вершина V является общей вершиной по крайней мере двух различных блоков графа G.

3) пусть G – блок, содержащий по крайней мере три вершины, тогда любые две вершины графа G некоторому общему циклу.

Лемма: пусть G-блок, содержащий не менее трех вершин, тогда любая вершина U и любое ребро графа G, не являющееся петлей, некоторому общему циклу.

Теорема: Пусть G – связный граф, содержащий не мене трех вершин, тогда следующие условия эквивалентны:

1) G-блок;

2) Любые две вершины графа G некоторому общему циклу;

3) В графе G любая вершина и любое ребро, не являющееся петлей, некоторому общему циклу;

4) В графе G любые два ребра, не являющееся петлями, некоторому общему циклу;

5) Для любых двух вершин и любого ребра, не являющегося петлей, в графе G существует простая цепь, соединяющая эти вершины и проходящая через данное ребро;

6) Для любых трех вершин U,V,W существует простая (U,W) цепь, проходящая через вершину V;

7) Для любых трех различных вершин U,V,W графа G существует простая (U,W) цепь, не проходящая через вершину V.