Ейлерів ланцюг

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Граф кенігсберзьких мостів. Це не Ейлерів граф, відповідно, розв'язок не існує
Кожна вершина цього графа має парну степінь, значить це Ейлерів граф. Обхід ребер в абетковому порядку дає ейлерів цикл

В теорії графів, ейлерів ланцюг — ланцюг в графі, що проходить кожне ребро рівно один раз. Схожим чином, ейлерів цикл — ейлерів ланцюг, що починається і завершується в одній вершині. Вперше розглянуті Леонардом Ейлером під час розв'язання відомої задачі кенігсберзьких мостів в 1736. Математично задача звучить так:

Чи можливо, для графа на малюнку праворуч, побудувати ланцюг (або цикл), що проходить кожне ребро рівно однин раз?

Ейлер довів, що необхідною умовою існування ейлерового циклу є парність степеня кожної вершини графа, і ствердив без доведення, що зв'язний граф з усіма вершинами з парними степенями має ейлерів цикл. Перше повне доведення цього твердження в 1873 оприлюднив Карл Гьехолзер.[1]

Ейлерів граф[ред.ред. код]

Термін ейлерів граф має два загальні значення в теорії графів. Одне значення це наявність в графі ейлерового циклу, друге це те, що всі вершини графа мають парний степінь.

Для існування ейлерового ланцюга необхідно, щоб не більше ніж дві вершини мали непарний степінь; це означає, що граф мостів Кенігсберга не ейлерів. Якщо не існує вершин непарних степенів, всі ейлеріві ланцюги є циклами. Якщо рівно дві вершини мають непарний степінь, всі ейлерові ланцюги починаються в одній і завершуються в іншій. Іноді граф, що має ейлерів ланцюг, але не має ейлерового циклу називається напів-ейлеровим.

Визначення[ред.ред. код]

Ейлерів ланцюг або ейлерів шлях в неорієнтованому графі це ланцюг (шлях), що проходить кожне ребро рівно один раз.

Ейлерів цикл в неорієнтованому графі це цикл, що проходить кожне ребро рівно один раз.

Для орієнтованих графів ланцюг заміняється на шлях або орієнтованийй шлях і цикл на орієнтований цикл.

Визначення і властивості ейлерових ланцюгів, циклів і графів залишаються правильними і у випадку мультиграфа.

Властивості[ред.ред. код]

  • Зв'язний неорієнтований граф є ейлеровим тоді і тільки тоді, коли кожна вершина графа має парний степінь.
  • Неорієнтований граф є ейлеровим, якщо він зв'язний і може бути розбитим на реберно-неперетинні цикли.
  • Якщо неорієнтований граф G ейлерів, тоді його лінійний граф L(G) також ейлерів.
  • Орієнтований граф ейлерів якщо він сильно зв'язний і кожна вершина має однаковий вхідний і вихідний степінь.
  • Орієнтований граф ейлерів, якщо він сильно зв'язний і може бути розбитим на реберно-неперетинні цикли.
  • Ейлерів ланцюг існує в орієнтованому графі тоді і тільки тоді, коли відповідний неорієнтований граф зв'язний, не більше ніж одна вершина має вихідний степінь - вхідний степінь = 1, не більше ніж одна вершина має вхідний степінь - вихідний степінь = 1, а всі інші вершини мають рівні вхідні і вихідні степені.
  • Неорієнтований граф напів-ейлерів, якщо не більше ніж дві вершини в графі мають непарний степінь.


Примітки[ред.ред. код]

  1. N. L. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory 1736-1936, Clarendon Press, Oxford, 1976, 8-9, ISBN 0-19-853901-0.