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

   такой что 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)

g2 =[[0, 0, 0, 1],               

        [0, 0, 0, 1],

        [0, 0, 0, 1],

        [1, 1, 1, 0]]

Hamilt(g2)