Пример 2.3. На рис. 2.8. изображен граф с p = 3 компонентами связности.

На рис. 2.8. изображен граф с p = 3 компонентами связности.

Если граф G связен, то p = 1, то есть, сам граф является своей единственной компонентой связности. Для несвязного графа количество компонент связности p всегда больше 1.

Рис. 2.8. Несвязный граф, p = 3

Рис. 2.9. Точка сочленения, v

Пусть G некоторый граф, обозначим через S (v) звездный граф вершины v. Вершина v графа G называется точкой сочленения, если число компонент связности дополнения звездного графа S (v) до графа G больше числа компонент связности графа G.

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

Дата добавления: 2015-07-20