Индуктивный переход
Пусть G - это четный граф, имеющий k = n + 1 ребер.
Уже было доказано, что в G существует элементарный цикл ненулевой длины.
Пусть C - некоторый такой цикл в G.
Удалим из G все ребра цикла C. Нетрудно видеть, что, степени всех вершин полученного графа четные. Это так, поскольку при удалении из G ребер цикла C степень произвольной вершины графа G либо остается прежней, либо уменьшается на 2.
Полученный граф G *может оказаться несвязным. Однако для каждой компоненты связности G выполняются условия теоремы: она связная, не имеет петель, содержит только ориентированные ребра и является четным графом.
По предположению индукции в каждой из компонент связности графа G *существует цикл Эйлера. Обозначим эти циклы как C 1,..., Cd.
Без ограничения общности можно считать, что каждый из этих циклов начинается и заканчивается в вершинах цикла C.
Общая схема расположения циклов C и C 1,..., Cd в графе G приведена на рис. 5.19.
v
C d G
C 1 C
Cj
Ci
Рис. 5.19
Здесь пунктирной линией изображен цикл C, а замкнутые области соответствуют компонентам связности G *, в которых проведены циклы C 1,..., Cd.
Организуем прохождение специального цикла в G, используя для этого циклы C, C 1,..., Cd.
1. Возьмем вершину v, являющуюся началом цикла C.
2. Из этой вершины выполняется перемещение по C до тех пор, пока не встретится первая вершина, являющаяся началом еще не проходившегося цикла из C 1,..., Cd, либо не будут пройдены все ребра .
3. Если такой цикл Ci найден, то выполняется прохождение этого цикла, начинающееся и заканчивающееся в вершине, лежащей на C.
4. Если последняя вершина Ci не совпадает с v (т.е. пройдены не все ребра C), то повторим действия 2 - 4.
Через конечное число повторений действий 2 - 4 описанный выше процесс закончится. При этом каждое ребро цикла C и циклов C 1,..., Cd проходится ровно один раз. Кроме того, проходятся все ребра G, так как C и C1,..., Cd содержат все ребра этого графа.
Итак, последовательность вершин в определенном выше порядке их прохождения по графу G образует цикл Эйлера в том же графе.
Дата добавления: 2015-09-27 | Просмотры: 463 | Нарушение авторских прав
|