Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Доказательство. Для множества циклов F проверим выполнение условий из определения фундаментального семейства циклов графа



Для множества циклов F проверим выполнение условий из определения фундаментального семейства циклов графа.

1. Покажем, что никакой цикл F не является суммой других циклов из этого семейства.

Предположим противное. Пусть для некоторого цикла Сi имеет место равенство

Сi = Сj 1 +... + Сj k, где j 1 < j 2... < jk.

Возможен ровно один из следующих двух случаев.

a) i < j 1.

В этом случае ни один из циклов Сj 1,..., Сj k не содержит ребро ui. Поэтому сумма циклов в правой части равенства не содержит это циклическое ребро. Однако цикл Сi содержит ребро ui. Поэтому данный случай не имеет места.

b) i > j 1.

В этом случае цикл Сi не содержит ребро uj 1. Это ребро содержится в Сj 1 и не входит ни в один из остальных циклов суммы Сj 1 +... + Сj k. Поэтому ребро uj 1 входит в сумму
Сj 1+... + Сj k. Следовательно, второй случай также не имеет места.

Полученные выводы противоречат предположению о справедливости равенства Сi = Сj 1 +... + Сj k. Поэтому никакой цикл из F не является суммой других циклов этого семейства.

2. Пусть С - произвольный простой цикл в G.

Среди циклических ребер u 1,..., uk найдем ребро ui 1 с минимальным индексом, которое содержится в С.

Составим сумму циклов С + Сi 1.

Полученный граф является четным и не содержит ребро ui 1. Если в этом графе имеются циклические ребра, то опять найдем циклическое ребро ui 2 c минимальным индексом, которое содержится в этом графе. При этом i 1< i2.

Составим сумму С + Сi 1+ Сi 2. Эта сумма является четным графом. Она не содержит ребер ui 1 и ui 2, а также циклических ребер из u 1,..., uk , индексы которых меньше, чем i2.

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

Поскольку семейство циклических ребер является конечным, то через конечное число шагов будет получена окончательная сумма С + Сi 1 +... + Сir, которая не содержит циклических ребер.

Так как эта сумма является четным графом, не содержащим циклических ребер, то она вообще не имеет ребер.

В противном случае каждая компонента связности графа С + Сi 1 +... + Сir должна иметь цикл Эйлера, а, значит, содержать хотя бы одно из ребер семейства { u 1,..., uk }, что невозможно.

Следовательно, графы С и Сi 1 +... + Сir совпадают. Поэтому справедливо равенство С = Сi 1 +... + Сir.





Дата публикования: 2015-03-29; Прочитано: 165 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...