Page 108 - 4204

ЛЕКЦІЯ 8. ЗАДАЧІ МЕРЕЖЕВОГО АНАЛІЗУ З ЕЛЕМЕНТАМИ ТЕОРІЇ ГРАФІВ

12
Зв’язний граф називається ейлеровим графом, якщо існує

замкнений ланцюг (цикл), який проходить через кожне ребро

рівно один раз.

13
Зв’язний граф називається гамільтоновим графом, якщо

існує замкнений ланцюг (цикл), який проходить через кожну ве-

ршину графа рівно один раз.

Незважаючи на схожість означень ейлерових і гамільтонових ци-

клів, вони мають цілком різні властивості. Зокрема, існують гамі-

льтонові графи, що не є ейлеровими, і навпаки.

Теорія графів «відкривалася» незалежно багато разів. Найпе-

рша згадка про неї зустрічається в роботах Ейлера, який у 1736

році розв’язав задачу про кенігсберзькі мости.

У Кенігсберзі було два острови, з’єднаних сімома мостами з берегами

річки та один із одним (рис. 8.1, а). Задача полягала в тому, щоб знайти

12
Леона́ рд Е́ йлер (нім. Leonhard Euler, *15 квітня 1707, Базель, Швейцарія — †18 вере-
сня 1783, Санкт-Петербург) — видатний швейцарський математик та фізик, який провів
більшу частину свого життя в Росії та Німеччині. Здійснив важливі відкриття в різних
галузях математики, а також в механіці, динаміці рідини, оптиці, астрономії та інших
прикладних науках.
13
Сер Ві́льям Ро́ вен Га́ мільтон (англ. Sir William Rowan Hamilton; *4 серпня 1806 — †2
вересня 1865) — ірландський і один з найбільших математиків XIX століття. Зробив
значний внесок у розвиток алгебри, теорії диференціальних рівнянь, а також астроно-
мії, оптики, динаміки.

107