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

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

В теорії графів, ейлерів ланцюг (англ. Eulerian path) — ланцюг в графі, що проходить кожне ребро рівно один раз. Схожим чином, ейлерів цикл — ейлерів ланцюг, що починається і завершується в одній вершині. Вперше розглянуті Леонардом Ейлером під час розв'язання відомої задачі кенігсберзьких мостів в 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.