Доказательство. Если в графе G=(V,E) нет циклов, то G=(V,E)

Если в графе G=(V, E) нет циклов, то G=(V, E). – дерево, следовательно, Т*= и Z= . И утверждение тривиально.

Пусть теперь в графе есть цикл Х. Этот цикл содержит хорды: . Такие хорды в Х обязательно есть, иначе бы , что противоречит с тем, что Х – цикл.

Докажем индукцией по n, что

Баз индукции: n=1.

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

Шаг индукции: пусть наше предположение справедливо для k< n, то есть .

Рассмотрим цикл Х с n хордами, . Возьмем Имеем

тоже цикл (возможно, не простой) с n -1 хордами.

X’ Ze_n

Х e_n

Следовательно, по предположению из того, что

вытекает, что

, что и требовалось доказать.

Пример

1 Данный цикл может быть получен как

Симметрическая разность циклов

2 ' ' 3 Z_{(1, 2),} Z_{(2, 4),} Z_{(3, 6)}

4 5 6

При порождении фундаментальной системы циклов удобно использовать метод поиска в глубину. С его помощью строится остовное дерево, и каждое обратное ребро порождает цикл относительно этого дерева. Для того, чтобы следить за ребрами дерева, используется поиск в глубину со стеком, в котором хранятся все текущие вершины пройденного пути в данный момент. Когда попадается обратное ребро, обнаруженный цикл будет состоять из этого ребра и ребер, соединяющих вершину из верха стека.