3.05.4. Остовы графа, циклический ранг и ранг разрезов

Пусть — произвольный - граф с компонентами связности. Если — не лес, то в нем (его компонентах связности) существуют циклы. Рассмотрим какой-либо цикл и удалим из него некоторое ребро. При этом количество компонент связности не увеличится. Если после этого еще останутся циклы, то рассмотрим следующий из них и снова удалим какое-либо его ребро. Продолжим этот процесс до тех пор, пока не исчезнут все циклы. Полученный в результате подграф, который, очевидно, является лесом и имеет столько же компонент связности, как и исходный граф , называется Остовом графа .

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

Доказательство. Пусть — компоненты связности графа , и пусть -графы. После удаления ребер из циклов компоненты она превратится в дерево, которое (см. теорему о критериях дерева) имеет ребер. Значит, из необходимо удалить ребер. Суммируя по всем компонентам, находим, что для получения остова из графа необходимо удалить ребер, что и требовалось доказать.

Определение. Число ребер, которые необходимо удалить из графа для получения остова, называется Циклическим рангом (или Цикломатическим числом) графа . Число ребер в остове графа , которое в различных остовах одно и то же и равно , называется Рангом разрезов (или Коциклическим рангом) графа .

Легко видеть, что справедливы следующие утверждения:

1. Граф является лесом тогда и только тогда, когда .

2. Граф содержит единственный цикл тогда и только тога, когда .

3. Граф, в котором число ребер не меньше, чем число вершин, обязательно содержит цикл.

Имеют место также следующие теоремы.

Теорема (Кирхгофа). Число остовов в связном графе порядка равно алгебраическому дополнению любого элемента матрицы Кирхгофа графа .

Теорема. Орграф сильно связен, если в нем существует остовной циклический маршрут.

< Предыдущая		Следующая >