В неориентированном графе g эйлерова цепь существует тогда и только тогда когда

Р ₁ ’’

Рисунок 4.21– Граф Г

Тогда, начиная с этой общей вершины х₁, можно построить цикл Р₂ в графе Г₁ аналогично тому, как был построен цикл Р₁. Очевидно, объединив два цикла Р₁ и Р₂, можно получить новый цикл Р₃:

Р₃ = Р ₁ ’ È Р₂ È Р ₁ ’’ _.

Этот цикл будет проходить, начиная с вершины х₀, путь Р ₁ ’ до вершины х₁, далее — цикл Р₂ снова в вершину х₁ и затем – путь Р ₁ ’’ в вершину х₀. Если цикл Р₃ не будет элеровым, то, проделав аналогичные построения, можно получить цикл с еще большим количеством ребер, продолжая процесс до построения эйлерова цикла. Он непременно будет построен в силу конечности исходного графа Г.

В произвольном графе эйлеров цикл, вообще говоря, может не существовать, а если существует, — может быть не единственным.

Таким образом, решая задачу о кенигсбергских мостах, рассматривая граф на рисунке 10.1.2, можно заметить, что степени вершин A, B, C, D равны соответственно 5, 3, 3, 3 являются нечетными. Т.е. в данном графе эйлерова цикла нет.

Эйлеровы графы встречаются достаточно редко.

В любом графе число вершин нечетной степени четно.

Доказательство.

По теореме Эйлера = 2 m, т.е. сумма степеней всех вершин – четное число. Сумма степеней вершин четной степени четна, значит, сумма степеней вершин нечетной степени также четна. Значит, их четное число.

4.6.2 Алгоритм Флёри нахождения эйлерова цикла

Естественно возникает вопрос: как найти хотя бы один эйлеров цикл в эйлеровом графе, пройдя по каждому ребру один раз и вернуться в начало.

Рисунок 4.22 – Граф с эйлеровым циклом

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

Нахождение эйлерова цикла в графе можно осуществить с помощью алгоритма Флёри:

1. Начиная с произвольной вершины х₀ исходного графа Г₀, присваиваем любому инцидентному ей ребру (х₀, х₁) номер 1. Удаляем ребро (х₀, х₁) из множества ребер графа Г₀ , получая граф Г₁ . Переходим в следующую вершину х₁.

2. Пусть х_k — вершина, в которую мы пришли после очередного шага нумерации ребра, получившего номер k. Для дальнейшей нумерации выбираем любое ребро графа Г_k, инцидентное вершине х_k, с учетом следующего правила: ребра, удаление которых из графа Г_k повлечет нарушение его связности, выбираются только тогда, когда другой выбор осуществить нельзя.

3. Алгоритм заканчивает свою работу, когда получен цикл, т.е. выбрано ребро (х, х₀), где х — некоторая вершина графа Г₀.

Иначе – повторяем пункт 2.

4. Если получился цикл, но не ейлеров, то отбрасываем данную последнюю вершину и повторяем пункт 2.

Эйлеровы цепи и циклы

Рассматриваемая задача является одной из самых ста-рей-ших в теории графов. В городе Кенигсберге (ныне Калининград) имелось семь мостов, соединяющих два берега реки Преголь, и два основа на ней друг с другом (рис. 1а). Требуется, начав путешествие из одной точки города прой-ти по всем мостам по одному разу и вернуться в исходную точку.

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

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

Простой критерий существования эйлерова цикла в связном графе дается следующей теоремой.

Теорема 1. (Эйлер) Эйлеров цикл в связном неориентированном графе G(X, E) существует только тогда, когда все его вершины имеют четную степень.

Доказательство. Необходимость. Пусть — эйлеров цикл в связном гра-фе G, x — произвольная вершина этого графа. Через вершину x эйлеров цикл проходит некоторое количество k (k1) раз, причем каждое прохождение, очевидно, включает два ребра, и степень этой вершины равна 2k, т.е. четна, так как x выбрана произвольно, то все вершины в графе G имеют четную сте-пень.

Достаточность. Воспользуемся индукцией по числу m ребер графа. Эйле-ровы циклы для обычных (не псевдо) графов можно построить начиная с m=3.Легко проверить, что единственный граф с m=3, имеющий все вершины с четными степенями, есть граф K₃ (рис. 2). Существование эйлерова цикла в нем очевидно. Таким образом, для m=3 достаточность условий доказываемой теоремы имеет место. Пусть теперь граф G имеет m>3 ребер, и пусть утверждение справедливо для всех связных графов, имеющих меньше, чем m ребер. Зафиксируем произвольную вершину a графа G и будем искать простой цикл, идущий из a в a. Пусть (a, x) — простая цепь, иду-щая из a в некоторую вершину x. Если x a, то цепь можно продолжить из вершины x в некотором направлении. Через некоторое число таких про-дол—же-ний мы придем в вершину zX, из которой нельзя продлить полу-чен-ную про-стую цепь. Легко видеть, что z = a так как из всех остальных вершин цепь может выйти (четные степени!); a в a она начиналась. Таким образом, нами построен цикл , идущий из a в a. Предположим, что построенный про-стой цикл не содержит всех ребер графа G. Удалим ребра, входящие в цикл , из графа G и рассмотрим полученный граф . В графе все вершины имеют четные степени. Пусть — компо-нен-ты связ-нос-ти графа , содержащие хотя бы по одному ребру. Соглас-но пред-поло-же-нию индукции все эти компоненты обладают эйлеровыми циклами ₁, ₁, …, _k соот-вет-ствен-но. Так как граф G связан, то цепь встре-чает каждую из компонент. Пусть первые встречи цикла с ком-понентами происходят соответственно в вершинах x₁, x₂, …, x_k. Тогда про-стая цепь

является эйлеровым циклом в графе G. Теорема доказана.

Замечание. Очевидно, что приведенное доказательство будет верно и для псевдографов, содержащих петли и кратные ребра (см. рис. 1,а).

Таким образом, задача о кенигсбергских мостах не имеет ре-ше-ния, так как соответствующий граф (см. рис. 1,б) не имеет эйлерова цикла из-за не-четности степеней все вершин.

Отметим, что из существования эйле-ро-ва цикла в неориентированном графе G не следует связность этого графа. Напри-мер, неориентированный граф G на рис. 3 обладает эйлеровым циклом и вместе с тем несвязен.

Совершенно также, как теорема 1, могут быть доказаны следующие два утверждения.

Теорема 2. Связный неориентированный граф G обладает эйлеровой цепью тогда и только тогда, когда число вершин нечетной степени в нем равно 0 или 2, причем если это число равно нулю, то эйлерова цепь будет являться и циклом.

Теорема 3. Сильно связный орграф G(X, E) обладает эйлеровым кон-ту-ром тогда и только тогда, когда для любой вершины xX выполняется

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

Если граф G — эйлеров, то очевидно, что это число равно 1. Пусть теперь G не является эйлеровым графом. Обозначим через k число его вер-шин нечетной степени. По теореме … k четно. Очевидно, что каждая верши-на нечетной степени должна быть концом хотя бы одной из покрывающих G цепей _i. Следовательно, таких цепей будет не менее чем k/2. С другой сто-роны, таким количеством цепей граф G покрыть можно. Чтобы убедиться в этом, расширим G до нового графа , добавив k/2 ребер , соединяющих раз-личные пары вершин нечетной степени. Тогда оказывается эйлеровым графом и имеет эйлеров цикл . После удаления из ребер граф разло-жится на k/2 цепей, покрывающих G. Таким образом, доказана.

Теорема 4. Пусть G — связный граф с k>0 вершинами нечетной степени. Тогда минимальное число непересекающихся по ребрам простых цепей, покрывающих G, равно k/2.

Алгоритм построения эйлерова цикла

Для начала отметим, что теорема 1 также дает метод построения эйлерова цикла. Здесь мы рассмотрим несколько иной алгоритм.

Пусть G(X, E) — связный неорентированный граф, не имеющий вершин нечетной степени. Назовем мостом такое ребро, удаление которого из связного графа разбивает этот граф на две компоненты связности, имеющие хотя бы по одному ребру.

1. Пусть a — произвольная вершина графа G. Возьмем любое ребро e₁=(a, x₁) , инцидентное вершине a, и положим = <e₁>.

2. Рассмотрим подграф G₁(X, E₁). Возьмем в качестве e₂ ребро, инци-дентное вершине x₁ и неинцидентное вершине a, которое также не является мостом в подграфе G₁ (если такое ребро e₂ существует!). Получим простую цепь ₂ = <e₁, e₂>.

3. Пусть e₂ = (x₁, x₂), x a. Рассмотрим подграф G₂(X, E₂) и удалим из него все изо-лированные вер-шины. В полученном подграфе выберем ребро e₃E₂, инцидентное вершине a, которое не является мостом в под-графе (если такое ребро e₃ суще-ству-ет!). Получим простую цепь

Продолжая указанный процесс, мы через конечное число шагов получим эйлеров цикл = <e₁, e₂, …, e_n>, где n — число ребер графа G(X, E).

Предположим, что уже построена простая цепь _k-1 = <e₁, e₂, …, e_k-1> для k2 методом, указанным в алгоритме. Пусть e_k-1 = (x_k-2, x_k-1) и x_k-1 a. Рас-смо-трим подграф , который получается из подграфа G_k-1(X, E_k-1) удалением всех изолированных вершин. Вершина x_k-1 в этом подграфе имеет нечет-ную степень, поэтому существует по крайней мере одно ребро e_kE_k-1, ин-ци-дентное x_k-1. Если это ребро единственное, то оно не является мостом в графе . В противном случае вершина a будет связана с некоторой вер-ши-ной единственной цепью, содержащей ребро e_k, что противоречит суще-ствованию эйлерова цикла в графе G. Поскольку e_k — не мост, то процесс мож-но продолжать, взяв . Если ребро e_k не единственное инци-дентное вершине x_k-1, то среди этих ребер есть по крайней мере одно, не явля-ющееся мостом. В противном случае один из этих мостов можно выбро-сить так, что вершины x_k-1 и a попадут в разные компоненты связности графа . Если x_k-1 принадлежит компоненте M, то в этой компоненте все вер-шины имеют четную степень, поэтому существует эйлеров цикл в M, про-хо-дящий через x_k-1. Этот цикл содержит все ребра, инцидентные x_k-1 и при-над-лежащие , являющиеся одновременно мостами. Получено противоречие, так как ребра из эйлерова цикла мостами быть не могут. Итак, в рассмотренном случае существует ребро e_k, инцидентное вершине x_k-1 и не являющееся мостом. Значит, и в этом случае процесс можно продолжать, взяв

Из предыдущего следует, что процесс нельзя продолжать тогда и только тогда, когда мы попадем в вершину a, причем степень вершины a относительно непройденных ребер равна нулю. Докажем, что в этом случае построенный цикл — простой цикл. Покажем, что содержит все ребра графа G. Если не все ребра графа G принадлежат , то не принадлежащие ребра порождают компоненты связности C₁, …, C_m (m1) в подграфе . Пусть компонента C_i, 1im соединяется с циклом в вершине y_i. Если существует ребро e , такое, что e=(y_i, a), то при построении цикла было нарушено правило выбора ребра e, что невозможно. Если часть цикла , соединяющая y_i и a, состоит более чем из одного ребра, то первое ребро этой части было мостом, и поэтому было нарушено правило вы-бора , что невозможно. Итак, непройденных ребер быть не может, поэ-тому — эйлеров цикл.

7. ЭЙЛЕРОВЫ ЦЕПИ И ЦИКЛЫ

Рассматриваемая в этой главе задача является одной из самых старейших в теории графов. В городе Кенигсберге (ныне Калининград) имелось семь мостов, соединяющих два берега реки Преголь, и два основа на ней друг с другом (рис. 7.1а). Требуется, начав путешествие из одной точки города пройти по всем мостам по одному разу и вернуться в исходную точку.

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

Определение 7.1. Эйлеровой цепью в неориентированном графе G называется простая цепь, содержащая все ребра графа G . Эйлеровым циклом называется замкнутая Эйлерова цепь. Аналогично, эйлеров путь в орграфе G — это простой путь, содержащий все дуги графа G . Эйлеров контур в орграфе G — это замкнутый эйлеров путь. Граф, в котором существует эйлеров цикл, называется эйлеровым .

Простой критерий существования эйлерова цикла в связном графе дается следующей теоремой.

Теорема 7.1. (Эйлер) Эйлеров цикл в связном неориентированном графе G ( X , E ) существует только тогда, когда все его вершины имеют четную степень.

Доказательство. Необходимость. Пусть μ — эйлеров цикл в связном графе G , x — произвольная вершина этого графа. Через вершину x эйлеров цикл проходит некоторое количество k ( k ≥ 1) раз, причем каждое прохождение, очевидно, включает два ребра, и степень этой вершины равна 2 k , т.е. четна, так как x выбрана произвольно, то все вершины в графе G имеют четную степень.

Достаточность. Воспользуемся индукцией по числу m ребер графа. Эйлеровы циклы для обычных (не псевдо) графов можно построить начиная с m =3.Легко проверить, что единственный граф с m =3, имеющий все вершины с четными степенями, есть граф K 3 (рис. 7.2). Существование эйлерова цикла в нем очевидно. Таким образом, для m =3 достаточность условий доказываемой теоремы имеет место. Пусть теперь граф G имеет m >3 ребер, и пусть утверждение справедливо для всех связных графов, имеющих меньше, чем m ребер. Зафиксируем произвольную вершину a графа

G и будем искать простой цикл, иду-

щий из a в a . Пусть μ ( a , x ) — простая

цепь, идущая из a в некоторую верши-

ну x . Если x ≠ a , то цепь μ можно про-

должить из вершины x в некотором на-

правлении. Через некоторое число та-

ких продолжений мы придем в верши-

ну z X , из которой нельзя продлить

полученную простую цепь. Легко ви-

деть, что z = a так как из всех остальных вершин цепь может выйти (четные степени!); a в a она начиналась. Таким образом, нами построен цикл μ , идущий из a в a . Предположим, что построенный простой цикл не содержит всех ребер графа G . Удалим ребра, входящие в цикл μ , из графа G и рассмотрим полученный граф G ′ ( X , E ′ ) . В графе G ′ все вершины имеют

четные степени. Пусть G 1 ′ , G 2 ′ . G k ′ — компоненты связности графа G ′ , содержащие хотя бы по одному ребру. Согласно предположению индукции все эти компоненты обладают эйлеровыми циклами μ 1 , μ 1 , …, μ k соответственно. Так как граф G связан, то цепь μ встречает каждую из компонент G 1 ′ , G 2 ′ . G k ′ . Пусть первые встречи цикла μ с компонентами

G 1 ′ , G 2 ′ . G k ′ происходят соответственно в вершинах x 1 , x 2 , …, x k . Тогда простая цепь

ν ( a , a )= μ ( a , x 1 ) U μ 1 ( x 1 , x 1 ) U μ ( x 1 , x 2 ) U … U μ k ( x k , x k ) U μ ( x k , a )

является эйлеровым циклом в графе G . Теорема доказана.

Замечание. Очевидно, что приведенное доказательство будет верно и для псевдографов, содержащих петли и кратные ребра (см. рис. 7.1,а).

Таким образом, задача о кенигсбергских мостах не имеет решения, так как соответствующий граф (см. рис. 7.1,б) не имеет эйлерова цикла из-за нечетности степеней все вершин.

Отметим, что из существования эйле-

рова цикла в неориентированном гра-

фе G не следует связность этого графа.

Например, неориентированный граф

G на рис. 7. 3 обладает эйлеровым циклом и вместе с тем несвязен. Совершенно также, как теорема 7.1, могут быть доказаны следующие

Теорема 7.2. Связный неориентированный граф G обладает эйлеровой цепью тогда и только тогда, когда число вершин нечетной степени в нем равно 0 или 2, причем если это число равно нулю, то эйлерова цепь будет являться и циклом.

Теорема 7.3. Сильно связный орграф G ( X , E ) обладает эйлеровым контуром тогда и только тогда, когда для любой вершины x X выполняется

Можно также обобщить задачу, которую решал Эйлер следующим образом. Будем говорить что множество не пересекающихся по ребрам про-

стых цепей < μ i , i = 1, m >( μ i Iμ j = , i ≠ j ) графа G покрывает его, если

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

Если граф G — эйлеров, то очевидно, что это число равно 1. Пусть теперь G не является эйлеровым графом. Обозначим через k число его вершин нечетной степени. По теореме … k четно. Очевидно, что каждая вершина нечетной степени должна быть концом хотя бы одной из покрывающих G цепей μ i . Следовательно, таких цепей будет не менее чем k /2. С другой стороны, таким количеством цепей граф G покрыть можно. Чтобы убедиться в этом, расширим G до нового графа G ′ , добавив k /2 ребер E ′ , соединяющих различные пары вершин нечетной степени. Тогда G ′ оказывается эйлеровым графом и имеет эйлеров цикл μ′ . После удаления из μ′ ребер E ′ граф разложится на k /2 цепей, покрывающих G . Таким образом, доказана

Теорема 7.4. Пусть G — связный граф с k >0 вершинами нечетной степени. Тогда минимальное число непересекающихся по ребрам простых цепей, покрывающих G , равно k /2.

Алгоритм построения эйлерова цикла

Для начала отметим, что теорема 7.1 также дает метод построения эйлерова цикла. Здесь мы рассмотрим несколько иной алгоритм.

Пусть G ( X , E ) — связный неорентированный граф, не имеющий вершин нечетной степени. Назовем мостом такое ребро, удаление которого из связного графа разбивает этот граф на две компоненты связности, имеющие хотя бы по одному ребру.

1 ° . Пусть a — произвольная вершина графа G . Возьмем любое ребро e 1 =( a , x 1 ) , инцидентное вершине a, и положим μ = < e 1 >.

2 ° . Рассмотрим подграф G 1 ( X , E\ μ 1 ). Возьмем в качестве e 2 ребро, инцидентное вершине x 1 и неинцидентное вершине a , которое также не является мостом в подграфе G 1 (если такое ребро e 2 существует!). Получим про-

3 ° . Пусть e 2 = ( x 1 , x 2 ), x ≠ a . Рассмотрим подграф G 2 ( X , E\ μ 2 ) и удалим из него все изолированные вершины. В полученном подграфе G 2 ′ выберем

ребро e 3 E\ μ 2 , инцидентное вершине a , которое не является мостом в подграфе G 2 ′ (если такое ребро e 3 существует!). Получим простую цепь

Продолжая указанный процесс, мы через конечное число шагов получим эйлеров цикл μ = < e 1 , e 2 , …, e n >, где n — число ребер графа G ( X , E ).

Обоснование алгоритма

Предположим, что уже построена простая цепь μ k -1 = < e 1 , e 2 , …, e k -1 >для

k ≥ 2 методом, указанным в алгоритме. Пусть e k -1 = ( x k -2 , x k -1 ) и x k -1 ≠ a . Рассмотрим подграф G k ′ − 1 , который получается из подграфа G k -1 ( X , E\ μ k -1 )

удалением всех изолированных вершин. Вершина x k -1 в этом подграфе G k ′ − 1 имеет нечетную степень, поэтому существует по крайней мере одно

ребро e k E\ μ k -1 , инцидентное x k -1 . Если это ребро единственное, то оно не является мостом в графе G k ′ − 1 . В противном случае вершина a будет свя-

зана с некоторой вершиной y G k ′ − 1 единственной цепью, содержащей

ребро e k , что противоречит существованию эйлерова цикла в графе G . Поскольку e k — не мост, то процесс можно продолжать, взяв μ k =μ k − 1 U < e k >.

Если ребро e k не единственное инцидентное вершине x k -1 , то среди этих ребер есть по крайней мере одно, не являющееся мостом. В противном случае один из этих мостов e k ′ можно выбросить так, что вершины x k -1 и a

попадут в разные компоненты связности графа G k ′ − 1 . Если x k -1 принадле-

жит компоненте M , то в этой компоненте все вершины имеют четную степень, поэтому существует эйлеров цикл в M , проходящий через x k -1 . Этот цикл содержит все ребра, инцидентные x k -1 и принадлежащие

( E \ μ k − 1 ) \ < e k ′ >, являющиеся одновременно мостами. Получено противо-

речие, так как ребра из эйлерова цикла мостами быть не могут. Итак, в рассмотренном случае существует ребро e k , инцидентное вершине x k -1 и не являющееся мостом. Значит, и в этом случае процесс можно продолжать, взяв

Из предыдущего следует, что процесс нельзя продолжать тогда и только тогда, когда мы попадем в вершину a , причем степень вершины a относительно непройденных ребер равна нулю. Докажем, что в этом случае построенный цикл μ — простой цикл. Покажем, что μ содержит все ребра графа G . Если не все ребра графа G принадлежат μ , то не принадлежащие μ ребра порождают компоненты связности C 1 , …, C m ( m ≥ 1) в подграфе G ′ ( X , E \ μ ). Пусть компонента C i , 1 ≤ i ≤ m соединяется с циклом μ в вер-

шине y i . Если существует ребро e μ , такое, что e =( y i , a ), то при построении цикла μ было нарушено правило выбора ребра e , что невозможно. Если часть цикла μ , соединяющая y i и a , состоит более чем из одного ребра, то первое ребро этой части e ′ = ( y i , y i + 1 ) было мостом, и поэтому было нарушено правило выбора e ′ , что невозможно. Итак, непройденных ребер быть не может, поэтому μ — эйлеров цикл.

8.НАХОЖДЕНИЕ КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ

В этом параграфе рассматриваются ориентированные графы G ( X , E ) каждой дуге e E которого ставится в соответствие вещественное число l ( e ). Т.е. на множестве Е создана функция l : E → R . Такой граф принято называть нагруженным . Само число l называется весом дуги.

Можно увидеть аналогию между, например, картой автомобильных или железных дорог. Тогда множество вершин Х будет соответствовать городам, множество дуг – магистралям, соединяющим города, а веса – расстояниям. (На практике, при этом, фактически получится неориентированный граф).

В связи с изложенной аналогией будем называть веса дуг расстояниями.

Определение 8.1. Пусть имеется последовательность вершин x 0 , x 1 , …, x n , которая определяет путь в нагруженном графе G ( X , E ), тогда длина этого

пути определяется как ∑ l ( x i − 1 , x i ) .

Естественный интерес представляет нахождение кратчайшего пути между двумя заданными вершинами x и y.

Алгоритм Форда отыскания кратчайшего пути.

Будем предполагать, что все расстояния в графе положительны. (Если это не так, то ко всем весам можно всегда добавить такую константу, что все эти веса станут положительными).

Пусть мы ищем путь от вершины x 0 к вершине x n . Будем каждой вершине x i ставить в соответствие некоторое число λ i по следующим правилам. 1 ° Положим λ 0 = 0, λ i = ∞ (достаточно большое число) для i > 0.

Проверить, является ли неориентированный graph эйлеровым

Для заданного неориентированного Graph проверьте, имеет ли он эйлеров путь или нет. Другими словами, проверьте, можно ли построить путь, который проходит через каждое ребро ровно один раз.

1. Эйлерова тропа (или эйлерова тропа, или эйлерова прогулка)

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

1. Ровно ноль или две вершины имеют нечетную степень, и
2. Все его вершины с ненулевой степенью принадлежат одной компоненте связности.

Следующий graph не является эйлеровым, поскольку четыре вершины имеют нечетную степень вхождения (0, 2, 3, 5):

2. Эйлерова схема (или эйлеров цикл, или эйлеров цикл)

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

1. Каждая вершина имеет четную степень и
2. Все его вершины с ненулевой степенью принадлежат одной компоненте связности.

Например, следующий graph имеет эйлеров цикл, так как каждая вершина имеет четную степень:

3. Полуэйлерова

Граф, который имеет эйлеров след, но не имеет эйлеровой цепи, называется полуэйлеровым. Неориентированный graph является полуэйлеровым тогда и только тогда, когда

1. ровно две вершины имеют нечетную степень и
2. Все его вершины с ненулевой степенью принадлежат одной компоненте связности.

Следующий graph является полуэйлеровым, поскольку существует ровно две вершины с нечетной степенью вхождения (0, 1):

Следующая реализация на C++, Java и Python проверяет, является ли данный graph эйлеровым и содержит ли он эйлеров цикл: