Алгоритм Робертса и Флореса

Содержание

1 Теоретическая часть        4

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

1.2 Алгоритм перебора Робертса и Флореса        5

2 Алгоритмическая часть        10

2.1 Алгоритм метода Робертса и Флореса        10

2.2 Блок - схема        11

2.3 Текст функции поиска гамильтоновых циклов        13

3 Примеры        16

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

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

1. Теоретическая часть

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

Простой цикл называется Гамильтоновым, если он содержит каждую вершину графа. И граф называется гамильтоновым, если он содержит гамильтонов цикл.

Из истории:

В 1859 г. ирландский математик В. Гамильтон придумал игру, которая называется "Кругосветное путешествие". Каждая из 20 вершин додекаэдра было приписано название крупного города мира. Требовалось посетить все города ровно 1 раз и вернуться в исходный город.

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

Достаточные условия существования гамильтонова цикла в графе.

1. Теорема Дирака (1952 г.).

Если число вершин графа p ≥ 3 и для любой вершины выполняется условие ∀ vi, i =1, р; deg vi ≥ p/2 (степень) и граф G - Гамильтонов

2. Теорема Оре (1960 г.).

Если число вершин графа G p ≥ 3 и для любых двух несмежных вершин u и v выполняется неравенство:

deg u + deg v ≥ p;     !∃(u, v) ∈ E, то граф G Гамильтонов.

Пример:

[pic 1]

P = 8; deg vi = 3; 3 ≥ 8/2 = 4 не Гамильтонов граф, но существует Гамильтонов цикл: M = (1, 2, 3, 4, 5, 6, 7, 8, 2)

[pic 2]

Дерево полного перебора: строится дерево слева направо:

[pic 3]

(1, 2, 3, 4, 3)

(1, 5, 4, 3, 2, 1)

Задача коммивояжера - это обобщенная задача о поиске Гамильтонова цикла в графе.

Задача.

Построить маршрут (цикл, цепь) во взвешенном графе G min веса, проходящий, по крайней мере, 1 раз по каждой вершине исходного графа.
Если он существует (цикл, маршрут), то задача сводится к задаче о поиске Гамильтонова цикла.

Задача китайского почтальона - это обобщение задачи о поиске Эйлерового цикла в графе.

1. Алгоритм перебора Робертса и Флореса

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

Следующая схема перебора, использующая обычную технику возвращения, была первоначально предложена Робертсом и Флоресом. Начинают с построения (k×n)–матрицы M=[mij], где элемент mij есть i–я вершина (скажем xq), для которой в графе G(X, Г) существует дуга (xj, xq). Вершины xq во множестве Г(xj) можно упорядочить произвольно, образовав элементы j–го столбца матрицы M. Число строк k матрицы M будет равно наибольшей полустепени исхода вершины.

Метод состоит в следующем. Некоторая начальная вершина (скажем, x1) выбирается в качестве отправной и образует первый элемент множества S, которое каждый раз будет хранить уже найденные вершины строящейся цепи. К S добавляется первая вершина (например, вершина a) в столбце x1. Затем к множеству S добавляется первая возможная вершина (например, вершина b) в столбце a, потом добавляется к S первая возможная вершина (например, вершина c) в столбце b и т.д. Под «возможной» вершиной мы понимаем вершину, еще не принадлежащую S. Существуют две причины, препятствующие включению некоторой вершины на шаге r во множество S = {x1,a,b,c, … ,xr–1,xr}. Или (1) в столбце хr нет возможной вершины, или (2) цепь, определяемая последовательностью вершин в S, имеет длину n – 1, т. е. является гамильтоновой цепью.