Разделяющие множества. Разрезы

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

Пример

- разделяющее множество, разрез.

цикл разрез (коцикл)

Коциклический ранг - число линейно независимых коциклов графа. .

Пример

.

Алгоритм нахождения базисной системы разрезов

1. Построить остов графа .
2. Удалять поочередно по одному ребру (остов распадается на две компоненты). Добавить к разрезу те хорды, концы которых принадлежат разным компонентам.

Пример

	остов	хорды

Число коциклов в графе равно .

Устойчивость графа