Page 43 - 4386

4 ЕЙЛЕРОВІ ТА ГАМІЛЬТОНОВІ ЦИКЛИ І ЛАНЦЮГИ

4.1 Ейлерові цикли та ланцюги. Ейлерові графи

Теорія графів бере свій початок з рішення видатним

математиком Леонардом Ейлером у 1736 р. задачі про

кенігсбергські мости. Вона виникла в прусському містечку

Кенігсберг на річці Прегал, через яку проходили 7 мостів. Серед

жителів Кенігсберга була поширена така задача: чи можна,

починаючи з будь-якої точки (А, B, C або D), здійснити

прогулянку (обхід) через усі мости так, щоб пройти кожен міст

тільки один раз і повернутися у вихідну точку (рис. 4.1 а).

C

A D

B

а б

Рисунок 4.1 – До задачі про кенігсбергські мости

Леонард Ейлер замінив план міста графом (рис. 4.1 б), у

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

з’єднують, – як ребра. Тоді задачу про кенігсберзькі мости можна

сформулювати мовою теорії графів таким чином: чи існує в графі

G цикл, який містить усі ребра цього графа? Інше відоме

формулювання даної задачі виглядає так: чи можна намалювати

фігуру, що зображає граф G, не відриваючи олівця від паперу і не

повторюючи ліній двічі, почавши і закінчивши цю процедуру в

одній з вершин фігури? Вперше відповідь на це питання дав

Л. Ейлер у 1736 р.

42