Эйлеровы и гамильтоновы графы

Связный граф G=(X, U) эйлеровым, если существует замкнутая цепь (цикл), проходящая через каждое ребро графа один раз.

Рис.18. Неэйлеров граф Рис.19. Полуэйлеров граф Рис.20. Эйлеров граф

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

Рассмотрим условие существования эйлерова цикла.

Конечный граф G является эйлеровым, если он связан и все его локальные степени четные (рис.20). Заметим, что граф является полуэйлеровым, если в нем не более двух вершин имеют нечетные локальные степени.

Идея алгоритма Флери построения эйлеровой цепи в эйлеровом графе. Пусть G – эйлеров граф. Тогда необходимо выйти из произвольной вершины и проходить по ребрам G соблюдая правила:

1. Стирать ребра по мере их прохождения и стирать изолированные вершины.

2. По мосту можно проходить только тогда, когда нет других возможностей.

При программировании использовать 2 стека.

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

Теорема 1. Если в графе с n (n  3) вершин для любой пары несмежных вершин x_i, x_j (x_i)+  (x_j) n, то граф имеет гамильтонов цикл.

Теорема 2. В графе без гамильтонова цикла длина его наибольших простых цепей удовлетворяет неравенству ℓ ≥  (x_n1) +  (x_n2), где  (x_n1) и  (x_n2) – две наименьшие локальные степени графа.

Рисунок 21 Рисунок 22

Если в графе G существует висячая вершина, то гамильтонов цикл отсутствует. Если граф G полный, то он содержит гамильтонов цикл.

Деревья

Связный граф без циклов называется деревом и обозначается Т = (Х, U), | X | = n , | T | = n-1. Начальную вершину называют корнем, из которого выходят ребра, называемые ветвями дерева. Любые две вершины дерева связаны единственной цепью. В любом связном графе G можно выделить некоторое дерево Т.

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

Для одного и того же связного графа можно выделить некоторое множество покрывающих его деревьев.

Теорема 3. Число t покрывающих деревьев в полном графе K_n составляет t=n^n-2. Множество деревьев называется лесом.

Задачи выделения эйлеровых и гамильтоновых циклов, а также покрывающих деревьев, связаны с задачами о лабиринте, коммивояжере, с построением деревьев минимальной точности. Задача о лабиринте в терминах теории графов формулируется как задача отыскания в связном графе G=(X, U), маршрута с наименьшим числом ребер, который начинается в заданной вершине х_iХ и приводит в искомую вершину х_jХ.

Метод Тремо

От вершины х_i необходимо перейти ко всем вершинам, находящимся на расстоянии 1 дин. Каждое ребро u_i = (х_i, x_ℓ) помечается один раз, когда оно смежно с вершинами х_i, x_ℓ в вершине х_i это ребро помечается как “открытое”. Если окажется, что нет ребер инцидентных x_ℓ кроме u_i, то, вернувшись в х_i ребро u_i помечается как “закрытое”. Если некоторое другое ребро u’_i = (х_i, x_ℓ) также ведет из х_i в x_ℓ оно также помечается как закрытое.

Для попадания в вершины, находящиеся на расстоянии 2, берется открытое ребро u = (х_i, x_ℓ) и снова помечается. В x_ℓ открытые ребра проходятся и помечаются как закрытые, если они ведут к пройденным вершинам и так со всеми открытыми ребрами. Если искомая вершина расположена на расстоянии n, то при ее достижении все открытые ребра будут помечены n раз.

Рисунок 7.23

Задача 2. Пусть необходимо проложить сеть проводов между терминалами при условии, что количество затраченного провода должно быть минимальным т.е. построить граф типа дерево.

Задача состоит в нахождении одного из n^n-2 деревьев.

Пусть G=(X, U) связной граф, и каждому ребру u_iU ставится в соответствие некоторое неотрицательное число ν_i, называемое мерой. Необходимо найти покрывающее дерево Т, для которого сумма мер, взятая по всем ребрам минимальна.

Метод Краскала

1. В связном графе G=(X, U), | X | = n, определяется ребро с наименьшей мерой.

2. Строится по индукции последовательность ребер u₂, u₃,…, u_n-1, причем на каждом шаге выбирается ребро с наименьшей мерой, не совпадающее с выбранными и не образующее циклов с предыдущими ребрами u_i.Полученный подграф Т графа G является искомым деревом.

(х₂х₆)=1

(х₆х₃)=2

(х₃х₅)=1

(х₃х₁)=2

(х₂х₄)=1