Курсовая работа: Гамильтоновы графы и сложность отыскания гамильтоновых циклов

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 = {x 1, x 2, … , 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 (x 1 ) и Г (x )S {x * } для некоторой другой вершины x * , то x * не может быть добавлена к S , так как тогда в остающемся подграфе не может существовать никакой цепи между x и x 1 . Цепь, определяемая множеством S {x * }, не может поэтому привести к гамильтонову циклу, а в качестве кандидата на добавление к множеству S следует рассмотреть другую вершину, отличную от x * .

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

Заключение

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

Список литературы

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

2. Белов В.В. Теория графов: Учеб. пособие для студ.высш.техн.учеб. заведений.-М.: Высш.школа, 1976.-392с.

3. Культин Н.Б. Программирование в TurboPascal 7.0 и Delphi.- Санкт-Петербург:BHV, 1998.-240c.

4. В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования, 1998 г.

5. Ф.А. Новиков. Дискретная математика для программистов, Питер, 2001 г.

6. В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999 г.

7. О. Оре. Теория графов, Наука, 1982 г.

8. www.codenet.ru

9. www.algolist.ru

Приложение

Программа отыскания гамильтонова цикла в графе:

Uses

dos,crt;

VAR a,b:array[1..100,1..100] of integer;