Определение: Степень вершины графа есть число инцидентных (принадлежащих) ей ребер. Граф G – четен, если каждая его вершина имеет четную степень.

Определение: Цикл (контур) в графе (орграфе) G называется Эйлеровым, если он проходит без повторов через все ребра (дуги) графа G. Граф (орграф) G называется Эйлеровым, если он имеет Эйлеров цикл (контур).

Замечание: Эйлеров граф связен ибо Эйлеров цикл связывает все вершины графа. Эйлеров цикл ориентирует ребра графа в направлении обхода цикла.

Теорема Эйлера: пусть G – связный граф, тогда граф G – Эйлеров ⇔ G – четен.

Доказательство (необходимость) ⇒: пусть связный граф G – Эйлеров и C – есть его Эйлеров цикл. Каждое прохождение вершины при движении по циклу приносит 2 (добавляет 2 ребра) в степень этой вершины. Т.к. каждое ребро графа G появляется в цикле один раз, то все вершины в графе G имеют четные степени, т.е. граф G четен.

Достаточность⇐: пусть связный граф G – четен, тогда G имеет простой цикл С. Удалим из G ребра цикла C (сохранив в G их вершины.), снова получим четный граф, т.к. либо от вершины в G удалим два ребра цикла, если эта вершина принадлежит циклу С, либо число ребер в ней не меняется, если вершина не принадлежит С. Из получившегося четного графа, каждая компонента связности которого четна, можно снова выделить цикл и т.д. пока не придем к графу G, у которого нет ребер.

Таким образом граф G допускает представление в виде объединения простых циклов, попарно не пересекающихся по ребрам: G = C1∪C2∪…. ∪Ck. Пусть С’ – есть один из этих простых циклов. Если G состоит только из простого цикла C’, то G – есть Эйлеров граф. Если G имеет другие простые циклы, то в силу связности графа G существует простой цикл C’’ имеющий общую вершину V с циклом C’ (при отсутствии в циклах C’ и C’’ общих ребер), тогда C’UC’’ – есть цикл с началом в вершине V, составленный сначала из ребер цикла C’, затем из ребер цикла C’’. Так циклу C’∪C’’ последовательно принадлежат другие простые циклы, значит, получили цикл, проходящий через все ребра графа G, поэтому этот цикл является Эйлеровым ⇒ граф G – также Эйлеров. Чтд.

Замечание: Теорема и ее Доказательство без изменения переносятся на мультиграфы и псевдографы. При этом петли относятся к одному из циклов, проходя их все при попадании в вершину, на которой эти петли навешаны. Т.к. петля прибавляет к степени вершины 2, то ∀ количество петель на четность вершины не влияет. Аналогичная Теорема справедлива и для орграфов.

Теорема: Связный орграф G – Эйлеров ⇔ для каждой вершины v в G число входящих в V дуг (полустепень захода) равна числу исходящих из V дуг (полустепень исхода).
Без доказательства.

Замечание: (Алгоритм 2): Эйлеров цикл в четном графе можно построить начав его любым ребром, а затем последовательно надстроив его вправо смежным ребром, одновременно удалив выбранные ребра из графа и следя за тем, чтобы при очередном удалении ребра из графа он не распался на несвязные компоненты или не очутились в изолированной вершине, не исчерпав при этом всех ребер графа.

Полные циклы и последовательности де Брейна

Пусть E₂ⁿ – есть множество всех наборов (a₁…a_n) длины n из нулей и единиц.

Определение: Набор из нулей и единиц длины 2ⁿ – есть полный цикл (де Брейна), если множество последовательно прочитанных наборов длины n исчерпывает все множество наборов длины n из нулей и единиц.

Замечание: цикл де Брейна, как и все циклы, располагается по кругу, конец совпадает с началом.

Полный цикл 0011- дает все наборы длины 2: 00,01,11,10

Теорема: для ∀n существует полный цикл де Брейна.
Доказательство: Построим ориентированный псевдограф G следующим образом: вершины в G пометим набороми из 0 и 1 длины (n-1), тогда G имеет 2^n-1 набора вершин. Каждый набор a₁,…,a_n из E₂ⁿ длины n определяет дугу, соединяющую вершины (a₁,…,a_n-1) и (a₂,…,a_n). Граф G связен, ибо ∀ пара вершин (a₁,…,a_n-1) и (b₁,…,b_n-1) в G соединена следующим образом:
(a₁,…,a_n-1) → (a₂,…,a_n-1, b₁) → (a₃,…,a_n-1,b₁,b₂) →….→ (a_n-1, b₁,…,b_n-2) → (b₁,…,b_n-1)

В каждую вершину (a₂,…,a_n) входят две дуги, помеченные наборами (0,a₂,…,a_n) и (1,a₂,…,a_n) и выходит 2 ребра, помеченные наборами (а₂,…,a_n,0), (a₂,…,a_n,1) ⇒ степень каждой вершины в G четна. Полустепени захода и исхода для каждой вершины из G равны ⇒ орграф G – Эйлеров ⇒ он имеет Эйлеров контур, в котором каждая вершина проходится дважды, ибо ее степень равна 4, тогда первые компоненты наборов, которыми помечены вершины в этом обходе, дадут полный цикл де Брёйна.

Замечание: Теорема справедлива и для наборов (a₁, a₂,…,a_n) из E_kⁿ длины n с элементами из E_k = {0,1,…,k-1}

Гамильтоновы графы

Определение: Цикл С в графе G называется Гамильтоновым циклом, если С проходит без повторов вершин через все вершины графа G. Граф G – Гамильтонов, если G имеет Гамильтонов цикл.

Замечание: Определение Гамильтоновых и Эйлеровых графов схожи, но методы их исследования различны. Пока не найдены простые критерии (вместо переборного) гамильтоновости графа. Есть предположение, что их нет. Доказаны лишь некоторые достаточные условия гамильтоновости.

Теорема Поша: если связанный граф G:
1) имеет p ≥ 3 вершин.
2) для ∀n из 1 ≤ n < (p-1)/2 следует условие, что число вершин со степенями ≤ n меньше n 3) из нечетности p следует, что число вершин степени (p-1)/2 меньше (p-1)/2 то G – есть гамильтонов граф. Без доказательства. Замечание: ограничивая условия теоремы Поста, получаем более простые, но менее сильные условия гамильтоновости графа.

Следствие 1(Оре): если число вершин графа G p≥3 и сумма степеней вершин deg(u)+deg(v) ≥ p для ∀ пар несмежных вершин u и v в G, то граф G – гамильтонов.
Следствие 2 (Дирак): если число вершин графа G p≥3 и deg(v)≥p/2 для любой вершины v графа G, то G – Гамильтонов.

Комментарии запрещены.