Дискретная математика

153 которого изображена на рис, 5.25. Эйлер показал, что этот граф не представляет единого цикла. Ибо если бы он существовал, то в каждой вершине графа было бы столько же входящих в нее ребер, сколько и выходящих из нее, т.е. в каждой вершине графа было бы четное число ребер. Таким образом, из какой бы вершины не начинался обход, обойти весь граф и вернуться обратно невозможно, не проходя никакого ребра дважды. Изложив решение задачи о кенигсбергских мостах, Эйлер в своей работе перешел к следующей общей проблеме теории графов: на каких графах можно найти цикл С, содержащий все ребра графа, причем каждое ребро в точности по одному разу? Такой цикл, т.е. цикл, содерлсащий все ребра графа в точности по одному разу, называется эйлеровым цнюю.ч, а граф, обладающий эйлеровым циклом - этероеъш графом. Теорема 5.17. Конечный граф G является эйлеровым графом тогда и только тогда, когда; 1) G связен; 2) все его локальные степени четны. Доказательство. Необходимость условия 1) очевидна. Далее, каждый раз, когда эйлеров цикл проходит через какую-то вершину, он должен войти в нее по одному ребру и выйти по другому, поэтому условие 2) также необходимо. Достаточность. Пусть условие 1) и 2) выполняется. Докажем, что граф эйлеров. Начнем цепь С в произвольной вершине v графа G и будем продолжать ее, насколько возможно, все время через новые ребра. Так как в каждой вершине число ребер четно, этот процесс может закончиться только а V, следовательно, цепь С будет циклом. Если С проходит через все ребра графа G, то цикл построен. Если же С содержит не все ребра графа G, то удалим из G ребра этого цикла С, в результате получим подграф G*. Графы С и G имеют четные локальные степени, следовательно, то же должно быть справедливо и для G*. Так как граф С связный, в С должна существовать вершина и, инцидентная ребрам из G* см. рис. 5.26. Из вершины и можно построить новую цепь С*, содержащую ребра только из G* и такая цепь может закончиться только при возвращении в и. Пусть S(v,u) B.S(V,U) две цепи, из которых образован цикл С. Тогда можно составить новый цикл; Ci=S(v,ii)u С*и S(v,u), который ^-0 возвращается в v и содержигг больше ребер, чем С, см. рис. 5.26, где цикл С "в' изображен сплошной линией, а цикл С* - штриховой. Если Сj не являете} Рис. 5.26 эйлеровым циклом, то это построени повторяется. Когда проце закончится, эйлеров цикл будет построен. Теорема доказана.