Page 69 - 4496

У першому випадку видалимо це ребро, а в другому додамо. В
обох випадках ступінь всіх вершин стане парною. Помітимо,
що у випадку видалення ребра, новий граф може стати
незв'язаним і мати 2 компоненти зв’язності (у цьому випадку
ребро, що видалене було мостом), кожне з яких або весь
новий граф має Ейлеровий цикл. Тепер якщо новий граф має
Ейлеровий цикл, то почнемо (і закінчимо його) у вершині з
непарним степенем і далі додамо ребро або видалимо його. В
обох випадках одержимо Ейлеровий шлях. Якщо новий граф
має 2 компоненти зв’язності, то, пройшовши одне з них по
Ейлерову циклу, починаючи й закінчуючи у вершині (яка в
початковому графі мала непарний ступінь), потім додамо
вилучене ребро (міст), пройдемо його, потрапимо в іншу
вершину, що раніше мала непарний ступінь, і пройдемо
другий компонент зв’язності за Ейлеровим циклом. У всіх
розглянутих випадках одержимо Ейлеровий шлях, що почався
в одній з вершин з непарним степенем і закінчився в іншій.
Теорема доведена.
Помітимо, що всі 4 вершини мультграфа (рис. 1), що
відповідає мостам Кенігсберга, мають ступінь 3. Тому
Ейлеровий цикл або шлях неможливий.
Примітка. Якщо граф (або мультграф без петель)
містить 2k вершин непарного степеня, то його можна розбити
на k напівейлерових графи (тобто намалювати k розчерками
пера). Доказ аналогічний доказу теореми Ейлера.
Є простий алгоритм (так званий алгоритм Флери) для
знаходження Ейлерова циклу (звичайно, якщо цей цикл існує),
що полягає в наступному: починаємо з будь-якої вершини й
“стираємо” пройдені ребра. При цьому по мосту (перешийку)
проходимо тільки, якщо немає інших можливостей.
Очевидно, що для того щоб побудувати Ейлеровий шлях
досить використати алгоритм Флери, якому треба почати з
вершини, що має непарний ступінь.
Розглянемо деякі додатки теореми Ейлера, які в
основному пов'язані з так званою задачею китайського
листоноші.
Нехай є деякий граф (зв'язний), ребрам якого приписані
деякі числа, називані вагами ребер (часто, але не завжди, у
додатках вага ребра – це його довжина). Потрібно знайти
такий цикл, при якому кожне ребро проходиться принаймні
66