Графы и алгоритмы

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

Разбить на страницы
Показывать лекцию целиком

Построение эйлерова цикла

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

Этот алгоритм похож на алгоритм поиска в глубину: начиная с произвольно выбранной стартовой вершины $$a$$, строим путь, выбирая каждый раз для дальнейшего продвижения еще не пройденное ребро. Главное отличие от поиска в глубину состоит в том, что как пройденные помечаются именно ребра, а не вершины. Поэтому одна и та же вершина может посещаться несколько раз, но каждое ребро проходится не более одного раза, так что в полученном маршруте ребра не будут повторяться. Вершины пути накапливаются в стеке $$S$$. Через некоторое количество шагов неизбежно наступит тупик - все ребра, инцидентные активной (последней посещенной) вершине $$x$$, уже пройдены. Так как степени всех вершин графа четны, в этот момент $$x=a$$ и пройденные ребра образуют цикл, но он может включать не все ребра графа. Для обнаружения еще не пройденных ребер возвращаемся по пройденному пути, перекладывая вершины из стека $$S$$ в другой стек $$C$$, пока не встретим вершину $$x$$, которой инцидентно непройденное ребро. Так как граф связен, такая вершина обязательно встретится. Тогда возобновляем движение вперед по непройденным ребрам, пока не дойдем до нового тупика и т.д. Процесс заканчивается, когда в очередном тупике обнаруживается, что $$S$$ пуст. В этот момент в стеке $$C$$ находится последовательность вершин эйлерова цикла.

Алгоритм 1. Построение эйлерова цикла

  • выбрать произвольно вершину $$a$$
  • $$a\Rightarrow S$$
  • while $$S\ne \emptyset$$ do
  • $$x:=top(S)$$
  • if имеется непройденное ребро $$(x,y)$$
  • then пометить ребро $$(x,y)$$ как пройденное
  • $$y\Rightarrow S$$
  • else переместить вершину $$x$$ из $$S$$ в $$C$$
    •

    Для обоснования алгоритма заметим сначала, что первой в стек $$S$$ помещается вершина $$a$$, и она будет последней перемещена из $$S$$ в $$C$$. Следовательно, она будет последней вершиной в стеке $$C$$. Далее, как было отмечено выше, первый раз, когда обнаружится, что все инцидентные активной вершине ребра пройдены (т.е. будет выполняться ветвь else в строке 8), активной будет стартовая вершина $$a$$. Значит, эта вершина будет первой перемещена из $$S$$ в $$C$$. Итак, по окончании работы алгоритма в начале и в конце последовательности вершин, содержащейся в стеке $$C$$, находится вершина $$a$$. Иначе говоря, если эта последовательность представляет маршрут (а далее будет показано, что так оно и есть), то этот маршрут замкнут.

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

    Будем говорить, что ребро $$(x,y)$$ представлено в стеке ( $$S$$ или $$C$$ ), если в какой-то момент работы алгоритма в стеке рядом находятся вершины $$x$$ и $$y$$. Ясно, что каждое ребро графа будет представлено в стеке $$S$$ и что каждые две вершины, расположенные рядом в этом стеке, образуют ребро. Допустим, в какой-то момент из стека $$S$$ в стек $$C$$ перемещается вершина $$x$$, а непосредственно под ней в стеке $$S$$ находится вершина $$y$$. Возможно, что вершина $$y$$ будет перемещена из $$S$$ в $$C$$ при следующем повторении цикла while, тогда ребро $$(x,y)$$ будет представлено в стеке $$C$$. Другая возможность - между перемещением вершины $$x$$ и следующим перемещением, т.е. следующим выполнением ветви else, будет несколько раз выполнена ветвь then (строки 6,\,7). Это означает, что будет пройдена некоторая последовательность ребер, начинающаяся в вершине $$y$$. Ввиду четности степеней эта последовательность может закончиться только в вершине $$y$$. Значит, и в этом случае следующей за вершиной $$x$$ будет перемещена из $$S$$ в $$C$$ вершина $$y$$. В любом случае ребро $$(x,y)$$ будет представлено в стеке $$C$$. Из этого рассуждения видно, что последовательность вершин в стеке $$C$$ является маршрутом и что каждое ребро графа в конечном итоге будет содержаться в этом маршруте, причем один раз.

    При каждом повторении цикла while в рассмотренном алгоритме либо проходится одно ребро, либо одна вершина перемещается из $$S$$ в $$C$$. Последнее можно трактовать как прохождение уже пройденного однажды ребра в обратном направлении. Каждое ребро в каждом направлении будет пройдено один раз, поэтому общая трудоемкость этого алгоритма оценивается как $$O(m)$$. Необходимо только оговориться, что этот вывод, как и аналогичные заключения об алгоритмах обхода в первых разделах этой главы, справедлив лишь при определенных предположениях о том, как задан граф. Способ задания должен обеспечить возможность быстрого просмотра множества ребер, инцидентных данной вершине. Подходящим является, например, задание графа списками инцидентности, в которых для каждой вершины перечисляются инцидентные ей ребра. Необходимо также иметь возможность быстро пометить ребро как пройденное или проверить, пройдено ли данное ребро. Для этого подходящей структурой может служить характеристический массив на множестве ребер.

    Гамильтоновы пути и циклы

    Гамильтоновым циклом ( путем ) называют простой цикл (путь), содержащий все вершины графа. В графе, изображенном на рис. 8.1 слева, гамильтоновым циклом является, например, последовательность $$1$$, $$2$$, $$3$$, $$5$$, $$4$$, $$1$$. В графе, изображенном в центре, нет гамильтоновых циклов, но есть гамильтоновы пути, например, $$2,1,3,5,4$$. В правом графе нет и гамильтоновых путей.

    (рис 8.1)

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

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

    Более рациональный подход состоит в рассмотрении всевозможных простых путей, начинающихся в произвольно выбранной стартовой вершине $$a$$, до тех пор, пока не будет обнаружен гамильтонов цикл или все возможные пути не будут исследованы. По сути дела, речь тоже идет о переборе перестановок, но значительно сокращенном - если, например, вершина $$b$$ не смежна с вершиной $$a$$, то все $$(n-2)$$! перестановок, у которых на первом месте стоит $$a$$, а на втором $$b$$, не рассматриваются.

    Рассмотрим этот алгоритм подробнее. Будем считать, что граф задан окрестностями вершин: для каждой вершины $$x$$ задано множество вершин, смежных с $$x$$. На каждом шаге алгоритма имеется уже построенный отрезок пути, он хранится в стеке PATH. Для каждой вершины $$x$$, входящей в PATH, хранится множество $$N(x)$$ всех вершин, смежных с $$x$$, которые еще не рассматривались в качестве возможных продолжений пути из вершины $$x$$. Когда вершина $$x$$ добавляется к пути, множество $$N(x)$$ полагается равным $$V(x)$$. В дальнейшем рассмотренные вершины удаляются из этого множества. Очередной шаг состоит в исследовании окрестности последней вершины $$x$$ пути PATH. Если $$N(x)\ne \varnothing$$ и в $$N(x)$$ имеются вершины, не принадлежащие пути, то одна из таких вершин добавляется к пути. В противном случае вершина $$x$$ исключается из стека. Когда после добавления к пути очередной вершины оказывается, что путь содержит все вершины графа, остается проверить, смежны ли первая и последняя вершины пути, и при утвердительном ответе выдать очередной гамильтонов цикл.

    Алгоритм 2. Поиск гамильтоновых циклов

  • выбрать произвольно вершину $$a$$
  • $$a\Rightarrow PATH$$
  • $$N(a):=V(a)$$
  • while $$PATH\ne \varnothing$$ do
  • $$x\, :={\rm top}(PATH)$$
  • if $$N(x)\ne \varnothing$$
  • then взять $$y\in N(x)$$
  • $$N(x):=N(x)-y$$
  • if вершина $$y$$ не находится в PATH
  • then $$y\Rightarrow PATH$$
  • $$N(y):=V(y)$$
  • if PATH содержит все вершины
  • then if $$y$$ смежна с $$a$$
  • then выдать цикл
  • else удалить вершину $$x$$ из PATH
    •

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

    (рис 8.2)

    В худшем случае время работы этого алгоритма тоже растет с факториальной скоростью. Например, для графа $$K_{n-1} +K_{1}$$ (граф с двумя компонентами связности, одна из которых - полный граф с $$n-1$$ вершиной, другая - изолированная вершина), если в качестве стартовой выбрана не изолированная вершина, то будут рассмотрены все $${(n-2)!}$$ простых путей длины $$n-2$$ в большой компоненте. Вместе с тем, если перед поиском гамильтонова цикла исходный граф проверить на связность, то ответ будет получен быстро. Можно пойти дальше и при обходе дерева путей поверять на связность каждый встречающийся "остаточный граф", т.е. граф, получающийся из исходного удалением всех вершин рассматриваемого пути. Если этот граф несвязен, то этот путь не может быть продолжен до гамильтонова пути. Поэтому можно не исследовать соответствующую ветвь дерева, а вернуться к рассмотрению более короткого пути, удалив последнюю вершину (т.е. сделать "шаг назад" в поиске в глубину). Можно пойти еще дальше и заметить, что если некоторая вершина $$x$$ DFS-дерева с корнем $$a$$ является развилкой, т.е. имеет не менее двух сыновей, то в подграфе исходного графа, полученном удалением всех предков этой вершины, кроме нее самой, она будет шарниром. Поэтому путь от $$a$$ до $$x$$ в DFS-дереве не может быть продолжен до гамильтонова пути. Эти соображения приводят к следующей модификации алгоритма: обходим граф поиском в глубину с построением DFS-дерева, затем находим в этом дереве самую нижнюю развилку (развилку с наименьшим глубинным номером). Если ни одной развилки нет, то само DFS-дерево представляет собой гамильтонов путь и остается только проверить наличие ребра, соединяющего начало и конец пути. Если же $$x$$ - развилка, то возвращаемся из $$x$$ в предшествующую вершину пути, помечаем все вершины, кроме собственных предков вершины $$x$$, как непосещенные и возобновляем поиск в глубину с этого места.

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

    Пусть граф $$G$$ задан матрицей смежности $$A=\left\| A(i,j)\right\|$$. Выберем произвольно стартовую вершину $$a$$ и определим для каждого $$k=0,1\ldots, n-2$$ функцию $$H_{k} (x,X)$$, где значениями переменной $$x$$ являются вершины, отличные от $$a$$, а значениями переменной $$X$$ - $$k$$ -элементные подмножества множества $$VG-\{ a\}$$, причем вершина $$x$$ не должна принадлежать множеству $$X$$. Эти функции определяются так: полагаем $$H_{k} (x,X)=1$$, если существует простой путь длины $$k+1$$ из вершины $$a$$ в вершину $$x$$, проходящий только через вершины из множества $$X$$, и $$H_{k} (x,X)=0$$, если такого пути не существует. Тогда

    $$H_{0} (x,\varnothing)=A(a,x) \qquad \text{для всех } x,$$

    а для $$k>0$$

    $$H_{k} (x,X)=\mathop{\vee}\limits_{y\in X} H_{k-1} (y,X-y)A(y,x). }$$

    Таким образом, зная все значения функции $$H_{k-1}$$, мы можем вычислить все значения функции $$H_{k}$$, причем для вычисления одного значения требуется выполнить $$2k-1$$ логических операций. Общее количество логических операций для вычисления всех этих функций составит

    $$(n-1)\suml_{k=1}^{n-2}\begin{pmatrix} {n-2} \\ k \end{pmatrix} (2k-1)=(n-1)(2^{n-2} (n-3)+1)=O(n^{2} 2^{n}).$$

    После того, как будет вычислена функция $$H_{n-2}$$, останется только для всех $$x$$, для которых $$H_{n-2} (x,X)=1$$ ( $$X$$ в этом случае определяется однозначно), выяснить, чему равно $$A(x,a)$$ - если хотя бы в одном случае это 1, то гамильтонов цикл существует. Очевидный недостаток данного алгоритма - необходимость хранения большого количества промежуточной информации.

    Страницы:

    Построение эйлерова цикла

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

    Этот алгоритм похож на алгоритм поиска в глубину: начиная с произвольно выбранной стартовой вершины $$a$$, строим путь, выбирая каждый раз для дальнейшего продвижения еще не пройденное ребро. Главное отличие от поиска в глубину состоит в том, что как пройденные помечаются именно ребра, а не вершины. Поэтому одна и та же вершина может посещаться несколько раз, но каждое ребро проходится не более одного раза, так что в полученном маршруте ребра не будут повторяться. Вершины пути накапливаются в стеке $$S$$. Через некоторое количество шагов неизбежно наступит тупик - все ребра, инцидентные активной (последней посещенной) вершине $$x$$, уже пройдены. Так как степени всех вершин графа четны, в этот момент $$x=a$$ и пройденные ребра образуют цикл, но он может включать не все ребра графа. Для обнаружения еще не пройденных ребер возвращаемся по пройденному пути, перекладывая вершины из стека $$S$$ в другой стек $$C$$, пока не встретим вершину $$x$$, которой инцидентно непройденное ребро. Так как граф связен, такая вершина обязательно встретится. Тогда возобновляем движение вперед по непройденным ребрам, пока не дойдем до нового тупика и т.д. Процесс заканчивается, когда в очередном тупике обнаруживается, что $$S$$ пуст. В этот момент в стеке $$C$$ находится последовательность вершин эйлерова цикла.

    Алгоритм 1. Построение эйлерова цикла

  • выбрать произвольно вершину $$a$$
  • $$a\Rightarrow S$$
  • while $$S\ne \emptyset$$ do
  • $$x:=top(S)$$
  • if имеется непройденное ребро $$(x,y)$$
  • then пометить ребро $$(x,y)$$ как пройденное
  • $$y\Rightarrow S$$
  • else переместить вершину $$x$$ из $$S$$ в $$C$$
    •

    Для обоснования алгоритма заметим сначала, что первой в стек $$S$$ помещается вершина $$a$$, и она будет последней перемещена из $$S$$ в $$C$$. Следовательно, она будет последней вершиной в стеке $$C$$. Далее, как было отмечено выше, первый раз, когда обнаружится, что все инцидентные активной вершине ребра пройдены (т.е. будет выполняться ветвь else в строке 8), активной будет стартовая вершина $$a$$. Значит, эта вершина будет первой перемещена из $$S$$ в $$C$$. Итак, по окончании работы алгоритма в начале и в конце последовательности вершин, содержащейся в стеке $$C$$, находится вершина $$a$$. Иначе говоря, если эта последовательность представляет маршрут (а далее будет показано, что так оно и есть), то этот маршрут замкнут.

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

    Будем говорить, что ребро $$(x,y)$$ представлено в стеке ( $$S$$ или $$C$$ ), если в какой-то момент работы алгоритма в стеке рядом находятся вершины $$x$$ и $$y$$. Ясно, что каждое ребро графа будет представлено в стеке $$S$$ и что каждые две вершины, расположенные рядом в этом стеке, образуют ребро. Допустим, в какой-то момент из стека $$S$$ в стек $$C$$ перемещается вершина $$x$$, а непосредственно под ней в стеке $$S$$ находится вершина $$y$$. Возможно, что вершина $$y$$ будет перемещена из $$S$$ в $$C$$ при следующем повторении цикла while, тогда ребро $$(x,y)$$ будет представлено в стеке $$C$$. Другая возможность - между перемещением вершины $$x$$ и следующим перемещением, т.е. следующим выполнением ветви else, будет несколько раз выполнена ветвь then (строки 6,\,7). Это означает, что будет пройдена некоторая последовательность ребер, начинающаяся в вершине $$y$$. Ввиду четности степеней эта последовательность может закончиться только в вершине $$y$$. Значит, и в этом случае следующей за вершиной $$x$$ будет перемещена из $$S$$ в $$C$$ вершина $$y$$. В любом случае ребро $$(x,y)$$ будет представлено в стеке $$C$$. Из этого рассуждения видно, что последовательность вершин в стеке $$C$$ является маршрутом и что каждое ребро графа в конечном итоге будет содержаться в этом маршруте, причем один раз.

    При каждом повторении цикла while в рассмотренном алгоритме либо проходится одно ребро, либо одна вершина перемещается из $$S$$ в $$C$$. Последнее можно трактовать как прохождение уже пройденного однажды ребра в обратном направлении. Каждое ребро в каждом направлении будет пройдено один раз, поэтому общая трудоемкость этого алгоритма оценивается как $$O(m)$$. Необходимо только оговориться, что этот вывод, как и аналогичные заключения об алгоритмах обхода в первых разделах этой главы, справедлив лишь при определенных предположениях о том, как задан граф. Способ задания должен обеспечить возможность быстрого просмотра множества ребер, инцидентных данной вершине. Подходящим является, например, задание графа списками инцидентности, в которых для каждой вершины перечисляются инцидентные ей ребра. Необходимо также иметь возможность быстро пометить ребро как пройденное или проверить, пройдено ли данное ребро. Для этого подходящей структурой может служить характеристический массив на множестве ребер.

    Гамильтоновы пути и циклы

    Гамильтоновым циклом ( путем ) называют простой цикл (путь), содержащий все вершины графа. В графе, изображенном на рис. 8.1 слева, гамильтоновым циклом является, например, последовательность $$1$$, $$2$$, $$3$$, $$5$$, $$4$$, $$1$$. В графе, изображенном в центре, нет гамильтоновых циклов, но есть гамильтоновы пути, например, $$2,1,3,5,4$$. В правом графе нет и гамильтоновых путей.

    (рис 8.1)

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

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

    Более рациональный подход состоит в рассмотрении всевозможных простых путей, начинающихся в произвольно выбранной стартовой вершине $$a$$, до тех пор, пока не будет обнаружен гамильтонов цикл или все возможные пути не будут исследованы. По сути дела, речь тоже идет о переборе перестановок, но значительно сокращенном - если, например, вершина $$b$$ не смежна с вершиной $$a$$, то все $$(n-2)$$! перестановок, у которых на первом месте стоит $$a$$, а на втором $$b$$, не рассматриваются.

    Рассмотрим этот алгоритм подробнее. Будем считать, что граф задан окрестностями вершин: для каждой вершины $$x$$ задано множество вершин, смежных с $$x$$. На каждом шаге алгоритма имеется уже построенный отрезок пути, он хранится в стеке PATH. Для каждой вершины $$x$$, входящей в PATH, хранится множество $$N(x)$$ всех вершин, смежных с $$x$$, которые еще не рассматривались в качестве возможных продолжений пути из вершины $$x$$. Когда вершина $$x$$ добавляется к пути, множество $$N(x)$$ полагается равным $$V(x)$$. В дальнейшем рассмотренные вершины удаляются из этого множества. Очередной шаг состоит в исследовании окрестности последней вершины $$x$$ пути PATH. Если $$N(x)\ne \varnothing$$ и в $$N(x)$$ имеются вершины, не принадлежащие пути, то одна из таких вершин добавляется к пути. В противном случае вершина $$x$$ исключается из стека. Когда после добавления к пути очередной вершины оказывается, что путь содержит все вершины графа, остается проверить, смежны ли первая и последняя вершины пути, и при утвердительном ответе выдать очередной гамильтонов цикл.

    Алгоритм 2. Поиск гамильтоновых циклов

  • выбрать произвольно вершину $$a$$
  • $$a\Rightarrow PATH$$
  • $$N(a):=V(a)$$
  • while $$PATH\ne \varnothing$$ do
  • $$x\, :={\rm top}(PATH)$$
  • if $$N(x)\ne \varnothing$$
  • then взять $$y\in N(x)$$
  • $$N(x):=N(x)-y$$
  • if вершина $$y$$ не находится в PATH
  • then $$y\Rightarrow PATH$$
  • $$N(y):=V(y)$$
  • if PATH содержит все вершины
  • then if $$y$$ смежна с $$a$$
  • then выдать цикл
  • else удалить вершину $$x$$ из PATH
    •

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

    (рис 8.2)

    В худшем случае время работы этого алгоритма тоже растет с факториальной скоростью. Например, для графа $$K_{n-1} +K_{1}$$ (граф с двумя компонентами связности, одна из которых - полный граф с $$n-1$$ вершиной, другая - изолированная вершина), если в качестве стартовой выбрана не изолированная вершина, то будут рассмотрены все $${(n-2)!}$$ простых путей длины $$n-2$$ в большой компоненте. Вместе с тем, если перед поиском гамильтонова цикла исходный граф проверить на связность, то ответ будет получен быстро. Можно пойти дальше и при обходе дерева путей поверять на связность каждый встречающийся "остаточный граф", т.е. граф, получающийся из исходного удалением всех вершин рассматриваемого пути. Если этот граф несвязен, то этот путь не может быть продолжен до гамильтонова пути. Поэтому можно не исследовать соответствующую ветвь дерева, а вернуться к рассмотрению более короткого пути, удалив последнюю вершину (т.е. сделать "шаг назад" в поиске в глубину). Можно пойти еще дальше и заметить, что если некоторая вершина $$x$$ DFS-дерева с корнем $$a$$ является развилкой, т.е. имеет не менее двух сыновей, то в подграфе исходного графа, полученном удалением всех предков этой вершины, кроме нее самой, она будет шарниром. Поэтому путь от $$a$$ до $$x$$ в DFS-дереве не может быть продолжен до гамильтонова пути. Эти соображения приводят к следующей модификации алгоритма: обходим граф поиском в глубину с построением DFS-дерева, затем находим в этом дереве самую нижнюю развилку (развилку с наименьшим глубинным номером). Если ни одной развилки нет, то само DFS-дерево представляет собой гамильтонов путь и остается только проверить наличие ребра, соединяющего начало и конец пути. Если же $$x$$ - развилка, то возвращаемся из $$x$$ в предшествующую вершину пути, помечаем все вершины, кроме собственных предков вершины $$x$$, как непосещенные и возобновляем поиск в глубину с этого места.

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

    Пусть граф $$G$$ задан матрицей смежности $$A=\left\| A(i,j)\right\|$$. Выберем произвольно стартовую вершину $$a$$ и определим для каждого $$k=0,1\ldots, n-2$$ функцию $$H_{k} (x,X)$$, где значениями переменной $$x$$ являются вершины, отличные от $$a$$, а значениями переменной $$X$$ - $$k$$ -элементные подмножества множества $$VG-\{ a\}$$, причем вершина $$x$$ не должна принадлежать множеству $$X$$. Эти функции определяются так: полагаем $$H_{k} (x,X)=1$$, если существует простой путь длины $$k+1$$ из вершины $$a$$ в вершину $$x$$, проходящий только через вершины из множества $$X$$, и $$H_{k} (x,X)=0$$, если такого пути не существует. Тогда

    $$H_{0} (x,\varnothing)=A(a,x) \qquad \text{для всех } x,$$

    а для $$k>0$$

    $$H_{k} (x,X)=\mathop{\vee}\limits_{y\in X} H_{k-1} (y,X-y)A(y,x). }$$

    Таким образом, зная все значения функции $$H_{k-1}$$, мы можем вычислить все значения функции $$H_{k}$$, причем для вычисления одного значения требуется выполнить $$2k-1$$ логических операций. Общее количество логических операций для вычисления всех этих функций составит

    $$(n-1)\suml_{k=1}^{n-2}\begin{pmatrix} {n-2} \\ k \end{pmatrix} (2k-1)=(n-1)(2^{n-2} (n-3)+1)=O(n^{2} 2^{n}).$$

    После того, как будет вычислена функция $$H_{n-2}$$, останется только для всех $$x$$, для которых $$H_{n-2} (x,X)=1$$ ( $$X$$ в этом случае определяется однозначно), выяснить, чему равно $$A(x,a)$$ - если хотя бы в одном случае это 1, то гамильтонов цикл существует. Очевидный недостаток данного алгоритма - необходимость хранения большого количества промежуточной информации.

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^