АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

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

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

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

С_i = С_{j 1} +... + С_{j k}, где j ₁ < j ₂... < j_k.

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

a) i < j ₁.

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

b) i > j ₁.

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

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

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

Среди циклических ребер u ₁,..., u_k найдем ребро u_{i 1} с минимальным индексом, которое содержится в С.

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

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

Составим сумму С + С_{i 1}+ С_{i 2}. Эта сумма является четным графом. Она не содержит ребер u_{i 1} и u_{i 2}, а также циклических ребер из u ₁,..., u_k , индексы которых меньше, чем i₂.

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

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

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

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

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

Дата добавления: 2015-09-27 | Просмотры: 413 | Нарушение авторских прав