Найти двойной Эйлер

Question

Нужны только некоторые указания о том, как определить, является ли граф двойным Эйлером? Это означает, что есть 2 схемы, если объединить, мы посетим все ребра в графе. Я могу предположить, что граф содержит схему Эйлера.

EDIT

Ответ @ Евгений Клюев

Граф имеет 2 цикла Эйлера, если он содержит хотя бы одну вершину с 4 или более ребрами.

Answer 1

Вот тезис о ДВОЙНЫХ ЭУЛЕРИЙСКИХ ГРАФАХ С ПРИЛОЖЕНИЯМИ ДЛЯ ДИЗАЙНА VLSI Андре Фримена .

Схема Эйлера \ Путь:

• Ненаправленный граф имеет цикл Эйлера тогда и только тогда, когда каждая вершина имеет четную степень, и все ее вершины с ненулевой степенью принадлежат одному связному компоненту.

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

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

• Ориентированный граф имеет эйлеров цикл, если и только если каждая вершина имеет одинаковую степень и степень отсутствия, и все его вершины с ненулевой степенью принадлежат одной сильно связной компоненте. Эквивалентно, ориентированный граф имеет эйлеров цикл, если и только если он может быть разложен на ребро-непересекающиеся ориентированные циклы, и все его вершины с ненулевой степенью принадлежат одному сильно связному компоненту.

• Ориентированный граф имеет эйлерову тропу тогда и только тогда, когда не более одной вершины имеет (out-градус) - (в градусах) = 1, не более одной вершины имеет (в градусах) - (out-градусно) степень) = 1, каждая другая вершина имеет одинаковую степень и степень, и все ее вершины с ненулевой степенью принадлежат одному связному компоненту основного неориентированного графа.

Источник: Википедия: Эйлерова дорожка