Эйлеровым путем в графе называется произвольный путь, проходящий через каждое ребро графа в точности один раз, т.е. путь v₁, ..., v_m+1, такой что каждое ребро e ОE появляется в последовательности v₁, ..., v_m+1 в точности один раз как e = {v_i, v_i+1} для некоторого i.

Если v₁ = v_m+1, то такой путь называется эйлеровым циклом. Задача существования эйлерова пути в заданном графе была решена Эйлером в 1736 году, и представленное им необходимое и достаточное условие существования такого пути считается первой в истории теоремой теории графов.
 
 

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

Доказательство. Доказательство достаточности условия теоремы будет следствием анализа алгоритма нахождения эйлерова пути, который будет описан ниже. Необходимость условия очевидна, так как если вершина v, отличная от вершины v₁ и v_m+1, появляется в эйлеровом пути k раз, то это означает, что степень этой вершины в графе составляет 2k. Отсюда следует, что вершины нечетной степени, если они существуют, являются концами эйлерова пути. Здесь следует отметить, что не существует графов с одной только вершиной нечетной степени. Действительно, обозначая степень вершины v через d(v), имеем
 
 

ибо в указанной сумме каждое ребро {u, v} считается дважды: один раз в d(u) и один раз в d(v). Отсюда следует, что число вершин всегда четно.
 
 

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

Предположим, что u и v - единственные вершины нечетной степени связного графа G = < V, E>, и образуем граф G* добавлением дополнительной вершины t и ребер {u, t} и {v, t} (или просто {u, v}, если {u, v}ПE ). Тогда G* - связный граф без вершин нечетной степени, а эйлеровы пути в G будут в очевидном взаимно однозначном соответствии с эйлеровыми циклами в G*. В силу этого дальше мы будем заниматься только эйлеровыми циклами.
 
 

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

Исходные данные: связный граф G = < V, E>без вершин нечетной степени, представленный списками ЗАПИСЬ [v], v О V.

Результаты: Эйлеров цикл, представленный последовательностью вершин в стеке СЕ.
 
 

begin

CTEK := Ж ; СЕ := Ж ;

v:= произвольная вершина графа;

CTEKЬ v;

while CTEK ╧ Жdo

begin v:= top (CTEK); { v = верхний элемент стека }

if ЗАПИСЬ [v] ╧ Ж then

begin u:= первая вершина списка ЗАПИСЬ [v];

CTEKЬ u;

{ удалить ребро {v, u} из графа }

ЗАПИСЬ [v] := ЗАПИСЬ [v] \ {u};

ЗАПИСЬ [u] := ЗАПИСЬ [u] \ {v};

v := u

end

else { ЗАПИСЬ [v] = Ж }

begin v Ь CTEK ; СЕЬ v;

end

end

end
 
 
 
 

Принцип действия этого алгоритма можно объяснить следующим образом: пусть v₀ - вершина, выбранная в третьей строке. Цикл начинает строить путь с началом в v₀, причем вершины этого пути помещаются в CTEK, а ребра удаляются из графа.

Эти действия продолжаются вплоть до того момента, когда путь нельзя удлинить, включив в него новую вершину, т.е. когда ЗАПИСЬ [v] = Ж.

Отметим, что тогда должно быть v = v₀, так как в любом другом случае это означало бы, что степень вершины v нечетная.

Таким образом, из нашего графа был удален цикл, а вершины этого цикла находятся в стеке CTEK.

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

Вершина v =v₀ переносится теперь из стека CTEK в стек CE, а ╚очередной╩ вершиной v становится верхний элемент стека CTEK.

Процесс повторяется, начиная с этой вершины (если ЗАПИСЬ [v] ╧Ж), в результате чего вследствие четности степени всех вершин находится и помещается в стек CTEK некоторый цикл, проходящий через вершину v.

Это продолжается до того момента, пока CTEK не станет пустым.

Очевидно, что вершины, помещаемые в стек CE, образуют некоторый путь, причем вершина v переносится в стек CE только тогда, когда ЗАПИСЬ [v] = Ж, т.е. когда все ребра, инцидентные с этой вершиной, представлены (парами соседних вершин) в одном из стеков. Отсюда легко следует, что по окончании алгоритма стек CE содержит эйлеров цикл.

Оценим теперь вычислительную сложность этого алгоритма. Для этого отметим, что каждая итерация главного цикла либо помещает вершину в стек CTEK и удаляет ребро из графа, либо переносит вершину из стека CTEK в стек CE. Таким образом, число итераций этого цикла - О(m). В свою очередь число шагов в каждой итерации ограничено константой. Здесь предполагаем, что каждый из списков инцидентности ЗАПИСЬ [v], v О V, реализован таким образом, что каждая вершина в этом списке содержит указатели на предыдущую и последующую вершины, и вершина u в списке ЗАПИСЬ [v] содержит указатель на вершину v в списке ЗАПИСЬ [u]. Это дает возможность устранить ребро {u, v} за время, ограниченное константой. Из приведенных выше рассуждений можно сделать вывод, что общая сложность алгоритма есть О(m). Очевидно, что этот алгоритм оптимальный, так как уже одно выписывание эйлерова цикла требует W (m) шагов.
 
 

Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок, например:

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

Многие результаты середины 19 века, относящиеся к теории графов, были получены при решении практических проблем.

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

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

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

Наряду с термином граф в начале 20 века употреблялись в качестве синонимов и другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт.

В проблематике теории графов можно выделить направления, носящие более комбинаторный или более геометрический характер.

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

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

Примером результата о существовании графа с фиксированными свойствами может служить критерий существования графа с заданными степенями вершин (степень вершины v есть число ребер, инцидентных v): набор целых чисел 0 ё d₁ё d_{2 ё}... ё d_n, сумма которых четна, является набором степеней вершин графа без петель и кратных ребер тогда и только тогда, когда для любого числа r, 1 ё r ё n - 1, выполняется условие
 
 

Примерами задач о подсчете являются задачи о нахождении количеств неизоморфных графов с одинаковым числом вершин и (или) ребер. Получены асимптотические формулы для числа неизоморфных деревьев с n вершинами и для числа неизоморфных графов без петель и кратных ребер с n вершинами.

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

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

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

Получено

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

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

Найдены критерии и построены эффективные алгоритмы установления k - связности графа.

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

наименьшее число цветов, достаточное для раскраски ребер любого графа без петель с максимальной степенью вершин s , равно [ 3 s/ 2 ] , а для раскраски вершин любого графа без петель и кратных ребер достаточно s  + 1 цветов.
 
 

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

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

каждая конечная абстрактная группа есть группа автоморфизмов (симметрий) некоторого графа.
 
 

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

Как одна из математических моделей теории вероятностей изучаются случайные графы. Это понятие возникает, например, в результате задания для каждой пары вершин v_i и v_j вероятности p_ij существования ребра между ними (с вероятностью q_ij = 1 - p_ij этого ребра нет). Многие свойства были изучены для ╚ почти всех╩ графов, т.е. когда всех p_ij = 1/2.
 
 

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

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

Не известен также алгоритм, который проверял бы существование гамильтонова пути в произвольном графе, используя число шагов, ограниченное многочленом от переменной n (числа вершин в графе).

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

Проблема существования гамильтонова пути принадлежит к классу так называемых NP-полных задач. Это широкий касс задач, включающий фундаментальные задачи из теории графов, логики, теории чисел, дискретной оптимизации и других дисциплин, ни для одной из которых не известен полиномиальный алгоритм (т.е. с числом шагов, ограниченным полиномом от размерности задачи), причем существование полиномиального алгоритма для хотя бы одной из них автоматически влекло бы за собой существование полиномиальных алгоритмов для всех этих задач. Именно факт фундаментальности многих NP-полных задач в различных областях и то, что, несмотря на независимые друг от друга усилия специалистов в этих областях, не удалось найти полиномиального алгоритма ни для одной из этих задач, склоняет к предположению, что такого алгоритма не существует.

Вернемся к конкретной задаче существования гамильтонова пути. Очевидный алгоритм, который мы можем применить, это полный перебор всех возможностей: генерируем все n! различных последовательностей вершин и для каждой из них проверяем, определяет ли она гамильтонов путь. Такие действия требуют по меньшей мере n! n шагов, но функция от n подобного вида растет быстрее, чем произвольный многочлен, и даже быстрее, чем произвольная экспоненциальная функция вида aⁿ, a > 1, ибо
 
 

Опишем теперь общий метод, позволяющий значительно сократить число шагов в алгоритмах типа полного перебора всех возможностей. Чтобы применить этот метод, искомое решение должно иметь вид последовательности бx₁, . . ., x_nс .

Основная идея метода состоит в том, что мы строим наше решение последовательно, начиная с пустой последовательности e (длины 0). Вообще, имея данное частичное решение бx₁, . . ., x_iс , мы стараемся найти такое допустимое значение x_i+1, относительно которого мы не можем сразу заключить, что бx₁, . . ., x_i, x_i+1сможно расширить до некоторого решения (либо бx₁, . . ., x_i, x_i+1с уже является решением).

Если такое предполагаемое, но еще не использованное значение x_i+1 существует, то мы добавляем его к нашему частичному решению и продолжаем процесс для последовательности бx₁, . . ., x_i, x_i+1с. Если его не существует, то мы возвращаемся к нашему частичному решению бx₁, . . ., x_i-1с и продолжаем наш процесс, отыскивая новое, еще не использованное допустимое значение x╒_i - отсюда название ╚алгоритм с возвратом╩ (англ.: backtracking).

Точнее говоря, мы предполагаем, что для каждого k > 0 существует некоторое множество A_k, из которого мы будем выбирать кандидатов для k-й координаты частичного решения.

Очевидно, что множества A_k должны быть определены таким образом, что для каждого целочисленного решения бx₁, . . ., x_nснашей задачи и для каждого kё n множество A_k содержало элемент x_k (на практике мы не можем вообще исключить ситуацию, когда множество A_k содержит некоторые ╚лишние╩ элементы, не появляющиеся в k-й координате ни одного целочисленного решения). Мы предполагаем также, что существует некоторая простая функция, которая произвольному частичному решению бx₁, . . ., x_iс ставит в соответствие значение P(x₁, . . ., x_i) (истина либо ложь) таким образом, что если P(x₁, . . ., x_i) = ложь, то последовательность бx₁, . . ., x_iс несомненно нельзя расширить до решения. Если P(x₁, . . ., x_i) = истина, то мы говорим, что значение x_i допустимо (для частичного решения бx₁, . . ., x_i-1с), но это отнюдь не означает, что бx₁, . . ., x_i-1с обязательно расширяется до полного решения. Этот процесс можно записать в виде следующей схемы:
 
 

begin

k:= 1;

while k > 0 do

if существует еще неиспользованный элемент y О A_k

такой, что P(X[1], . . ., X[k - 1], y) then

begin X[k] := y; { элемент y уже использован }

if б X[1], . . ., X[k]с является целочисленным решением then

write(X[1], . . ., X[k]);

k:= k +1;

end

else { возврат на более короткое частичное решение; все элементы

множества A_k вновь становятся неиспользованными }

k:= k - 1

end
 
 

Этот алгоритм находит все решения в предположении, что множества A_k конечные и что существует n, такое что P(x₁, . . ., x_n) = ложь для всех x₁О A₁, . . ., x_nО A_n (последнее условие означает, что все решения имеют длину меньше n).

Покажем наличие более общего свойства:

Пусть s > 0, и пусть бx₁, . . ., x_s-1с - некоторое частичное решение, построенное алгоритмом. Рассмотрим первую итерацию цикла, для которой k = s, X[i] = x_i, 1 ё  i ёs. Начиная с этой итерации, алгоритм генерирует все целочисленные решения, являющиеся расширением последовательности бx₁, . . ., x_s-1си приходит к состоянию, когда k = s - 1.

Очевидно, что для s = 1 приведенное выше свойство означает просто корректность алгоритма.

Доказательство этого свойства в общем виде проводится по ╚индукции назад╩ относительно s. Оно имеет место для s = n, потому что не существует ни одного допустимого элемента для бx₁, . . ., x_s-1с и сразу же выполняется второе условие условного оператора (по else), т.е. переменная k принимает значение s - 1.

Предположим теперь правильность нашего свойства для некоторого s > 1. Покажем его правильность для  s - 1. Пусть бx₁, . . ., x_s-2с - произвольное частичное решение, построенное нашим алгоритмом; рассмотрим первую итерацию цикла, для которой k = s - 1, X[i] = x_i, 1 ё i ёs - 1. Если существует элемент y, допустимый для бx₁, . . ., x_s-2с , то построение дает частичное решение бx₁, ..., x_s-2, yс и переменная k принимает значение s. Затем согласно нашему индуктивному предположению будут сгенерированы все решения, являющиеся расширением последовательности бx₁, ..., x_s-2, yс , и мы приходим к состоянию, когда k = s - 1, после чего процесс повторяется для следующего неиспользованного элемента y, допустимого для бx₁, . . ., x_s-2с , пока не будут использованы все такие элементы (такая ситуация может появиться сразу с самого начала). Переменная k  уменьшается тогда на 1 и принимает значение  s - 2. Из приведенных выше рассуждений следует, что алгоритм правильно порождает все решения, являющиеся расширением последовательности бx₁, . . ., x_s-2с, что завершает доказательство шага индукции.

Доказанное свойство приводит непосредственно к следующему простому и очевидному рекурсивному варианту схемы алгоритма с возвратом:
 
 

procedure AP(k)

{генерирование всех решений, являющихся расширением последовательности

X[1], . . ., X[k - 1]: массив X - глобальный}

begin

for y О A_k такого, что P(X[1], . . ., X[k - 1], y) do

begin X[k] := y;

if X[1], . . ., X[k] есть целочисленное решение then write(X[1], . . ., X[k]);

AP(k +1);

end

end
 
 

Генерирование всех целочисленных решений можно вызвать вызовом AP(1). Представление алгоритма с возвратом мы начали с несколько более сложного нерекурсивного варианта только потому, что в рекурсивном варианте ╚возврат╩ не появляется в явном виде, будучи частью реализации механизма рекурсии.

Применим теперь алгоритм с возвратом для нахождения гамильтонова цикла в графе G = <V, E> . Каждый такой цикл можно представить последовательностью бx₁, x₂, . . ., x_n+1с, причем x₁ = x_n+1 = v₀, где v₀ - некоторая фиксированная вершина графа, x_i - x_i+1 для 1 ё i ё n и x_i ╧x_j для 1 ёi < j ё n. Согласно этим условиям мы можем положить:

A_k = V,

P б x₁, ..., x_k-1, yс Ы yО ЗАПИСЬ [x_k-1] Щ y О {x₁, ..., x_k-1}.
 
 

Алгоритм нахождения всех гамильтоновых циклов в графе

Данные: Граф G = <V, E>, представленный списками инцидентности ЗАПИСЬ[v], vО V.

Результаты: Список всех гамильтоновых циклов графа G.
 
 

procedure ГАМИЛЬТ(k)

{генерирование всех гамильтоновых циклов, являющихся расширением

последовательности X[1], . . ., X[k - 1]: массив X - глобальный}

begin

for y О ЗАПИСЬ [X[k - 1]] do

if (k = n +1) and (y = v0) then write(X[1], . . ., X[n], v0)

else if DOP[y] then

begin X[k] := y; DOP[y] := ложь;

ГАМИЛЬТ (k +1);

DOP[y] := истина

end

end; { ГАМИЛЬТ }

begin { главная программа }

for v О V do DOP[v] := истина; {инициализация}

X[1] := v0; {v0 = произвольная фиксированная вершина графа}

DOP[v0] := ложь;

ГАМИЛЬТ (2);

end
 
 

Работу этого алгоритма, так же как и произвольного алгоритма с возвратом, можно проиллюстрировать процессом поиска в некотором дереве. Каждая вершина дерева естественным образом соответствует некоторой последовательности бx₁, ..., x_kс, причем вершины, соответствующие последовательностям вида бx₁, ..., x_k, yс являются сыновьями этой вершины ( корень соответствует пустой последовательности e ). Рассмотрим полное дерево D, состоящее из всех возможных последовательностей вида бx₁, ..., x_kс, где 0 ё k ёn и x_i ОA_i для 1 ёi ё k, и временно допустим, что каждый элемент y ОA_k  является допустимым для бx₁, ..., x_k -1с, если k ё n, и ни один элемент не является допустимым для бx₁, ..., x_k -1с, если k > n; другими словами, P(x₁, ..., x_k-1, x_k) =  истина, если kё n, и P(x₁, ..., x_k-1, x_k) =  ложь, если k ё n (x_iО A_i для 1 ё i ёk). Тогда нетрудно отметить, что вызов AP(1) вызывает поиск в глубину во всем дереве D (начиная от корня e). Для случая менее тривиальной функции P, определяющей допустимость вершин, процесс поиска ╚опускает╩ рассмотрение вершин поддерева с корнем в каждой встреченной ╚недопустимой╩ вершине, т.е. вершине, соответствующей последовательности бx₁, ..., x_kс, для которой P(x₁, ..., x_k) =  ложь). В этом, собственно говоря, заключается эффективность алгоритма с возвратом в отношении полного перебора всех возможностей.

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