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

17) S = {1}

"5"

18) S = {1, 5}

19) S = {1, 5, 4}

20) S = {1, 5, 4, 3}

21) S = {1, 5, 4, 3, 2} - Г

22) S = {1, 5, 4, 3}

23) S = {1, 5, 4}

24) S = {1, 5}

25) S = {1}

26) S = Ø 

2.2.1 Улучшение  метода Робертса и Флореса

Рассмотрим улучшение основного  переборного метода Робертса и Флореса. Допустим, что на некотором этапе  поиска построенная цепь задается множеством S = {x1, x2, , xr} и что следующей вершиной, которую предполагается добавить к S, является x* S. Рассмотрим теперь две следующие ситуации, в которых вершина является изолированной в подграфе, остающемся после удаления из G(X,Г) всех вершин, образующих построенную до этого цепь.

a)  Если существует такая вершина x X\S, что x Г(xr) и Г-1(x)   S, то, добавляя к S любую вершину x*, отличную от x, мы не сможем в последующем достигнуть вершины x ни из какой конечной вершины построенной цепи, и, значит, эта цепь не сможет привести нас к построению гамильтонова цикла. Таким образом, в этом случае x является единственной вершиной, которую можно добавить к S для продолжения цепи.

b)  Если существует такая вершина x X\S, что x Г-1(x1) и Г(x)  S {x*} для некоторой другой вершины x*, то x* не может быть добавлена к S, так как тогда в остающемся подграфе не может существовать никакой цепи между x и x1. Цепь, определяемая множеством S   {x*}, не может поэтому привести к гамильтонову циклу, а в качестве кандидата на добавление к множеству Sследует рассмотреть другую вершину, отличную от x*.

Проверка условий (a) и (b) будет, конечно, замедлять итеративную  процедуру, и для небольших графов (менее чем с 20 вершинами) не получается никакого улучшения первоначального  алгоритма Робертса и Флореса. Но для больших графов эта проверка приводит к заметному сокращению необходимого времени вычислений, уменьшая его обычно в 2 или более раз.

Заключение

В данной работе мы познакомились  с основными понятиями, определениями  и результатами, связанными с гамильтоновыми графами и циклами. Так же мы рассмотрели  ту часть теории сложности, которая  затрагивает задачи отыскания гамильтонова цикла. И в итоги проведённых  изучений была написана программа отыскания  гамильтонова цикла в графе.