Ейлерів ланцюг
теорія графів / З Вікіпедії, безкоштовно encyclopedia
Шановний Wikiwand AI, Давайте зробимо це простіше, відповівши на ключові запитання:
Чи можете ви надати найпопулярніші факти та статистику про Ейлерів ланцюг?
Підсумуйте цю статтю для 10-річної дитини
ПОКАЗАТИ ВСІ ЗАПИТАННЯ
У теорії графів, ланцюг Ейлера (англ. Eulerian path) — ланцюг у графі, який проходить кожне ребро рівно один раз. Схожим чином, цикл Ейлера — ланцюг Ейлера, який розпочинається та завершується в одній вершині. Вперше розглянуті Леонардом Ейлером під час розв'язання відомої задачі кенігсберзьких мостів в 1736. Математично задача звучить так:
- Чи можливо для графу на малюнку праворуч побудувати ланцюг (або цикл), який проходить кожне ребро рівно один раз?
Ейлер довів, що необхідна умова існування циклу — парність степеня кожної вершини графу, і ствердив без доведення, що зв'язний граф з усіма вершинами з парними степенями має цикл Ейлера. Перше повне доведення цього твердження в 1873 оприлюднив Карл Гіргольцер.[1]