Точки сочленения

Определение. Вершина v графа называется точкой сочленения, если её удаление из графа увеличивает число компонент связности.

Определение. Блоком называется связный граф, не имеющий точек сочленения.

На рис. 1 показан связный граф с точкой сочленения v, который после удаления вершины v распадается на три блока.

Рис. 1

Утверждение (теорема о свойствах точки сочленения).

Пусть - связный граф и . Тогда следующие утверждения эквивалентны:

1. v – точка сочленения;

2. : любая простая цепь, соединяющая вершины u и w проходит через вершину v.

3. Вершина v не является висячей вершиной никакого остовного дерева графа G.

Дата добавления: 2014-01-05; Просмотров: 508; Нарушение авторских прав?; Мы поможем в написании вашей работы!