Page 46 - 4386

Для знаходження деякого ейлерового циклу в ейлеровому

графі G можна застосувати алгоритм Фльорі.

Починаючи з довільної вершини v, присвоїмо довільному

ребру (v, u) номер 1. Викреслимо ребро (v, u) та переходимо до

вершини u. Нехай на попередньому кроці ми перейшли до

вершини w і присвоїли ребру номер k. На черговому кроці

вибираємо довільне ребро інцидентне w (причому, ребро, що не

входить до складу жодного циклу в графі, який залишився,

вибирається тільки тоді, коли інших немає) та, присвоївши

обраному ребру номер k+1, викреслюємо його. Процедура

завершується, коли всі ребра буде викреслено.

4.2 Гамільтонові цикли та ланцюги. Гамільтонові графи

У 1857 р. математик Вільям Гамільтон придумав іграшку-

головоломку. Ця іграшка являла собою додекаедр (правильний

багатогранник), 12 граней якого − це правильні п'ятикутники

(рис. 4.3 а). У кожному з 20 кутів просвердлювалась дірка, у яку

вставляли кілочок, що зображував місто. За допомогою мотузки

необхідно було знайти шлях через міста, відвідавши кожне місто

один раз, і повернутися у вихідне місто. Додекаедр на площині

зображується так, як показано на рис. 4.3 б.

а б

Рисунок 4.3 – Зображення додекаедр

45