Алгоритм поиска гамильтонова пути в графе

         Будем говорить, что графы G = (V,E), G¢ = (V¢,E¢) изоморфны, если существует такое взаимно однозначное отображение f из V на V¢, что для произвольных  u, v Î V имеем

{u, v}Π E Û {f(u), f(v)} Î E¢ ((u, v) Î E Û (f(u), f(v)) Î Е¢

в случае ориентированных графов. Обычно изоморфные графы не различаются между собой.

        Для произвольного вещественного  числа x мы будем употреблять обозначения éxù и ëxû  соответственно для наибольшего целого числа, не превосходящего x, и для наименьшего целого числа, не меньшего x, например ë3.5û = 3, é3.5ù = 4, ë-3.5û = -4, é-3.5ù = -3.

Алгоритм  поиска гамильтонова пути в графе

 

        Перейдем теперь к понятиям, связанным  с алгоритмами. Алгоритмы будем  обычно записывать на языке программирования, являющимся неформальной версией языка Паскаль. Если реализация какого-либо фрагмента программы очевидна, но трудоемка и затемняет идею алгоритма, то такой фрагмент будем иногда заменять описанием на естественном языке. Мы будем также применять неформальные конструкции, такие как, например, циклы (for x Î X do P (выполнять команду P для всех элементов x множества X в произвольной последовательности)) и т.д. Будем обычно опускать описания типов и переменных. Переменная, появляющаяся в процедуре, рассматривается как локальная для данной процедуры, исключая тот случай, когда в комментарии сказано что-либо иное. Строки программы нумеруются так, чтобы можно было указать на «цикл 17», «блок 9» и т.д.

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

Рис 1.2: а) Гамильтонов  путь в графе; б) Граф, в котором  не существует гамильтонова пути. 

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

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

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

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

(x₁, . . . , x_i, x_i +1) можно расширить до некоторого решения  (либо

(x₁, . . . , 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 содержало элемент xk (на практике мы не можем вообще исключить ситуацию, когда множество A_k содержит некоторые «лишние» элементы, не появляющиеся в k-й координате ни одного целочисленного решения).              Мы предполагаем также, что существует некоторая простая функция, которая произвольному частичному решению (x₁, . . . , x_i) ставит в соответствие значение P(x₁, . . . , x_i) (истина либо ложь) таким образом, что если P(x₁, . . . , xi)=ложь, то последовательность (x₁, . . . , x_i) несомненно нельзя расширить до решения. Если P(x₁, . . . , xi)=истина, то мы говорим, что значение xi допустимо (для частичного решения (x₁, . . . , x_i−1), но это отнюдь не означает, что (x₁, . . . , x_i−1), обязательно расширяется до полного решения. Этот процесс можно записать в виде следующей схемы: 
 
 
 
 

1 begin

2 k := 1;

3 while k > 0 do

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

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

   then

5 begin X[k] := y; (* элемент y использован*)

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

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

8 k := k + 1

9 end

10 else (* возврат  на более короткое частичное   решение;

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

11 k := k − 1

12 end 

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

         Алгоритм, организованный на языке  Python, представлен в Приложении 1. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Заключение 

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

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

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

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

Список  использованной литературы 

1. Липский В., Комбинаторика для программистов., 1988, Москва

2. Кристофидес  Н., Теория графов. Алгоритмический  подход., 1978, Москва

3. Татт У., Теория графов.,  1988, Москва 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Приложение 1. 

def Hamilt(G):

    n = len(G)

    k = 0

    res = []

    cur = 0

    used = [False for i in range(n)]

    while (k >= 0):

        flag = False

        for i in range(cur, n):

            if not used[i] and ((k == 0) or (G[res[k-1]][i] == 1)):

                res.append(i)

                used[i] = True

                k = k + 1

                cur = 0

                flag = True

                break

        if (k == n):

            print res

            break

        if not flag:

            if (k > 0):

                cur = res[-1] + 1

                used[res[-1]] = False

                del(res[-1])

            k = k - 1

    if (k < 0):

        print "No solution." 

примеры: 

g1 =[[0, 0, 1, 1],                             

        [0, 0, 1, 1],

        [1, 1, 0, 1],

        [1, 1, 1, 0]]

Hamilt(g1)