Эйлеров путь

В теории графов эйлерова тропа (или эйлерова тропа ) — это тропа в конечном графе, которая посещает каждое ребро ровно один раз (с возможностью повторного посещения вершин). Точно так же эйлерова цепь или эйлеров цикл — это эйлерова тропа, которая начинается и заканчивается в одной и той же вершине . Впервые они были обсуждены Леонардом Эйлером при решении знаменитой задачи о семи мостах Кенигсберга в 1736 году. Математически эту задачу можно сформулировать следующим образом:

Эйлер доказал, что необходимым условием существования эйлеровых цепей является то, что все вершины в графе имеют четную степень , и заявил без доказательства, что связные графы со всеми вершинами четной степени имеют эйлерову цепь. Первое полное доказательство этого последнего утверждения было опубликовано посмертно в 1873 году Карлом Гирхольцером . ^[1] Это известно как теорема Эйлера:

Термин Эйлеров граф имеет два общих значения в теории графов. Одно значение — это граф с эйлеровым контуром, а другое — граф с каждой вершиной четной степени. Эти определения совпадают для связных графов. ^[2]

Для существования эйлеровых следов необходимо, чтобы ноль или две вершины имели нечетную степень; это означает, что граф Кенигсберга не является эйлеровым. Если нет вершин нечетной степени, то все эйлеровы пути являются цепями. Если вершин нечетной степени ровно две, то все эйлеровы пути начинаются в одной из них, а заканчиваются в другой. Граф, который имеет эйлеров след, но не имеет эйлеровой цепи, называется полуэйлеровым .

Эйлерова тропа [ ^3] или блуждание Эйлера в неориентированном графе — это блуждание, в котором каждое ребро используется ровно один раз. Если такое блуждание существует, граф называется проходимым или полуэйлеровым . ^[4]

Эйлеров цикл , ^[3] Эйлерова схема или эйлеров цикл в неориентированном графе — это цикл , в котором каждое ребро используется ровно один раз. Если такой цикл существует, граф называется эйлеровым или уникурсальным . ^[5] Термин «Эйлеров граф» также иногда используется в более слабом смысле для обозначения графа, в котором каждая вершина имеет четную степень. Для конечных связных графов эти два определения эквивалентны, в то время как, возможно, несвязный граф является эйлеровым в более слабом смысле тогда и только тогда, когда каждая компонента связности имеет эйлеров цикл.

Мультиграфы головоломок « Кенигсбергские мосты » и « Пять комнат » имеют более двух нечетных вершин (выделены оранжевым цветом), поэтому не являются эйлеровыми и, следовательно, головоломки не имеют решений.

Каждая вершина этого графа имеет четную степень . Следовательно, это эйлеров граф. Следование по ребрам в алфавитном порядке дает эйлерову схему/цикл.

Использование эйлеровых следов для решения головоломок, включающих рисование фигуры с непрерывной чертой:
1. Поскольку головоломка Haus vom Nikolaus имеет две нечетные вершины (оранжевые), след должен начинаться в одной и заканчиваться в другой.
2. У Энни Поуп с четырьмя нечетными вершинами нет решения.
3. Если нет нечетных вершин, то след может начинаться где угодно и образует эйлеров цикл.
4. Свободные концы считаются вершинами степени 1.

Орфографические проекции и диаграммы Шлегеля с гамильтоновыми циклами вершин пяти платоновых тел - только октаэдр имеет эйлеров путь или цикл, продолжив свой путь пунктирным.

Бесконечный граф со всеми степенями вершин, равными четырем, но без эйлеровой прямой.

ориентированный граф со всеми четными степенями, не являющийся эйлеровым, который служит контрпримером к утверждению, что достаточным условием для того, чтобы ориентированный граф был эйлеровым, являются все четные степени

этот смешанный граф является эйлеровым. Граф четный, но несимметричный, что доказывает, что четность и симметрия не являются необходимым и достаточным условием для эйлерова смешанного графа.

Таким образом, даже смешанный граф, нарушающий условие сбалансированного множества, не является эйлеровым.

Даже смешанный граф удовлетворяет условию сбалансированного множества и, следовательно, является эйлеровым смешанным графом.