an align="justify">. Отрімаємо новий цикл Z 1 Вў , Z 2 , Z 1 Вў Вў , что веде з v 1 у v 1 . Если цею цикл ейлерів - процес завершівся. У противному разі Продовжуємо аналогічні побудова ще раз и т.д. Цею процес завершитися побудова Шуканов ейлерового циклу.
Теорема 1.7.2 Ланцюг Ейлера в псевдо графові G існує тоді и Тільки тоді, коли віконуються наступні умови :
В· Граф зв'язного;
В· Степені внутрішніх вершин парні (внутрішні вершини не є качаном и кінцем ланцюга);
В· Если вершини а і b є качаном и кінцем ланцюга и то Ступені їх непарні;
В· Если вершини а і b є качаном и кінцем ланцюга, то Ступені їх парні.
Тепер абсолютно очевидно, что в графові, что моделює Завдання про мости Кенігсберга, ейлерового циклу найти НЕ можна. <В
Рис. 1.7.1 Схема старого Кенігсберга
Дійсно, Ступені всех его вершин непарні: 6 (B) = 6 (C) - 6 (D) = 3 и 6 (A) = 5. З легкої руки Ейлера графі, подібні тому, Який ми досліджувалі при вірішенні задачі про мости, начали використовуват при вірішенні багатьох практичних Завдання, а їх Вивчення виросло в значний область математики.
Теорема 1.7.2 Щоб у зв'язаних неорієнтованому графові G існував ейлеровій цикл, звітність, и Достатньо, щоб число вершин непарного ступенів Було хлопця.
Наслідок 1.7.1 Для зв'язного ейлерового графа G безліч ребер можна Розбита на простих циклі.
Наслідок 1.7.2 Для того, щоб зв'язного граф G покрівався Єдиним ейлеровім Ланцюг звітність, и Достатньо , щоб ВІН містів Рівно 2 вершини з непарним ступеня. Тоді ланцюг ПОЧИНАЄТЬСЯ в одній з ціх вершин и закінчується в Інший.
