Деревья блоков и точек сочленения

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

Для связного графа G с множеством блоков {Bi} и множеством точек сочленения {сj} граф блоков и точек сочлененияbc (G) определяется как граф, у которого множеством вершин служит {В,} U {Cj} и две вершины смежны, если одна соответствует блоку Bi,

а другая - точке сочленения сj, причем сj, принадлежит Вj. Таким образом,

bc(G) - двудольный граф. Это понятие было введено в работе Харари и Принса, а также в статье Галлаи.

Теорема.G - граф блоков и точек сочленения некоторого графа Н тогда и только тогда, когда он является деревом, в котором расстояние между любыми двумя висячими вершинами четно.

Имея в виду эту теорему, мы будем говорить о дереве блоков и точек сочленения графа.