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

Остовные деревья графа

Пусть – связный граф.

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

Если в графе всего р вершин, то в остовном дереве ребер. Чтобы построить остовное дерево графа, нужно последовательно удалять ребра, принадлежащие циклам, пока все циклы не будут разрушены. Если в графе всего q ребер, то, чтобы получить остовное дерево, потребуется удалить ребро.

На рис. 10 показаны два различных остовных дерева (Т ₁ и Т ₂) исходного графа .

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

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

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

Рис. 1

Дата добавления: 2013-12-13