Ейлерів ланцюг: відмінності між версіями

Ейлер довів, що необхідною умовою існування ейлероваейлерового циклу є парність степеня кожної вершини графа, і ствердив без доведення, що [[зв'язний граф]] з усіма вершинами з парними степенями має ейлерів цикл. Перше повне доведення цього твердження в 1873 оприлюднив Карл Гьехолзер.<ref>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.</ref>

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

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

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