Ейлерів ланцюг
В теорії графів, ейлерів ланцюг — ланцюг в графі, що проходить кожне ребро рівно один раз. Схожим чином, ейлерів цикл — ейлерів ланцюг, що починається і завершується в одній вершині. Вперше розглянуті Леонардом Ейлером під час розв'язання відомої задачі кенігсберзьких мостів в 1736. Матматично задача звучить так:
- Чи можливо, для графа на малюнку праворуч, побудувати ланцюг (або цикл), що проходить кожне ребро рівно однин раз?
Ейлер довів, що необхідною умовою існування ейлерова циклу є парність степеня кожної вершини графа, і ствердив без доведення, що зв'язний граф з усіма вершинами з парними степенями має ейлерів цикл. Перше повне доведення цього твердження в 1873 оприлюднив Карл Гьехолзер.[1]
Зміст |
Ейлерів граф [ред.]
Термін ейлерів граф має два загальні значення в теорії графів. Одне значення це наявність в графі ейлерова циклу, друге це те, що всі вершини графа мають парний степінь.
Для існування ейлерова ланцюга необхідно, щоб не більше ніж дві вершини мали непарний степінь; це значить, що граф Кенігсберга не ейлерів. Якщо не існує вершин непарних степенів, всі ейлеріві ланцюги є циклами. якщо рівно дві вершини мають непарний степінь, всі ейлерові ланцюги починаються в одній і завершуються в іншій. Іноді граф, що має ейлерів ланцюг, але не має ейлерова циклу називається напів-ейлеровим.
Визначення [ред.]
Ейлерів ланцюг або ейлерів шлях в неорієнтованому графі це ланцюг (шлях), що проходить кожне ребро рівно один раз.
Ейлерів цикл в неорієнтованому графі це цикл, що проходить кожне ребро рівно один раз.
Для орієнтованих графів ланцюг заміняється на шлях або орієнтованийй шлях і цикл на орієнтований цикл.
Визначення і властивості ейлерових ланцюгів, циклів і графів залишаються вірними і у випадку мультиграфа.
Властивості [ред.]
- Зв'язний неорієнтований граф є ейлеровим тоді і тільки тоді, коли кожна вершина графа має парний степінь.
- Неорієнтований граф є ейлеровим, якщо він зв'язний і може бути розбитим на реберно-неперетинні цикли.
- Якщо неорієнтований граф G ейлерів, тоді його лінійний граф L(G) також ейлерів.
- Орієнтований граф ейлерів якщо він сильно зв'язний і кожна вершина має однаковий вхідний і вихідний степінь.
- Орієнтований граф ейлерів, якщо він сильно зв'язний і може бути розбитим на реберно-неперетинні цикли.
- Ейлерів ланцюг існує в орієнтованому графі тоді і тільки тоді, коли відповідний неорієнтований граф зв'язний, не більше ніж одна вершина має вихідний степінь - вхідний степінь = 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.
 |
ВікіСховище має мультимедійні дані за темою: Ейлерів ланцюг |
