Теорема 5.8
F является фундаментальным семейством циклов графа G.
Доказательство
Для множества циклов F проверим выполнение условий из определения фундаментального семейства циклов графа.
1. Покажем, что никакой цикл F не является суммой других циклов из этого семейства.
Предположим противное. Пусть для некоторого цикла Сi имеет место равенство
Сi = Сj1 + ... + Сjk , где j1 < j2 . . . < jk.
Возможен ровно один из следующих двух случаев.
a) i < j1.
В этом случае ни один из циклов Сj1, . . . , Сjk не содержит ребро ui. Поэтому сумма циклов в правой части равенства не содержит это циклическое ребро. Однако цикл Сi содержит ребро ui. Поэтому данный случай не имеет места.
b) i > j1.
В этом случае цикл Сi не содержит ребро uj1. Это ребро содержится в Сj1 и не входит ни в один из остальных циклов суммы Сj1 + . . . +Сjk. Поэтому ребро uj1 входит в сумму Сj1+ . . . + Сj k. Следовательно, второй случай также не имеет места.
Полученные выводы противоречат предположению о справедливости равенства Сi = Сj1 + ... + Сjk. Поэтому никакой цикл из F не является суммой других циклов этого семейства.
2. Пусть С произвольный простой цикл в G.
Среди циклических ребер u1, . . . , uk найдем ребро ui1 с минимальным индексом, которое содержится в С.
Составим сумму циклов С + Сi1.
Полученный граф является четным и не содержит ребро ui1. Если в этом графе имеются циклические ребра, то опять найдем циклическое ребро ui2 c минимальным индексом, которое содержится в этом графе. При этом i1 < i2.
Составим сумму С + Сi1 + Сi2. Эта сумма является четным графом. Она не содержит ребер ui1 и ui2, а также циклических ребер из u1, . . . , uk , индексы которых меньше, чем i2.
Повторяем последние действия до тех пор, пока в результате получаются графы, содержащие циклические ребра. Поскольку всякий цикл, добавляемый к образующейся на очередном шаге сумме циклов, не содержит циклических ребер, индексы которых меньше или равны индексу предыдущего цикла суммы, то формируемая сумма составляется из циклов семейства F, с возрастающими значениями индексов.
Поскольку семейство циклических ребер является конечным, то через конечное число шагов будет получена окончательная сумма С + Сi1 +. . . + Сir, которая не содержит циклических ребер.
Так как эта сумма является четным графом, не содержащим циклических ребер, то она вообще не имеет ребер.
В противном случае каждая компонента связности графа С + Сi1 + ... + Сir должна иметь цикл Эйлера, а, значит, содержать хотя бы одно из ребер семейства {u1, . . . , uk}, что невозможно.
Следовательно, графы С и Сi1 + ... + Сir совпадают. Поэтому справедливо равенство С = Сi1 + ... + Сir.
Доказательство окончено.
Пример. Рассмотрим граф, изображенный на рис.5.24.
а b с
1 2 3
4
d e f
Рис. 5.24
В качестве фундаментального семейства циклов этого графа выберем следующую систему циклов (рис. 5.25):
С
c
a
b b b
d d e e e f
C1 C 2 C3 C4
Рис. 5.25
На рис. 5.24 числами 1, 2, 3, 4 помечены циклические ребра, удалявшиеся из графа в процессе построения фундаментального семейства циклов. Числа, приписанные таким ребрам, соответствуют номерам циклов семейства.
Нетрудно проверить, что цикл C = a b c f e d a в этом графе может быть выражен как C = C1 + C2 + C3 + C4.