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

Содержание

 

Введение…………………………………………………………… 3

Основные понятия………………………………………………… 4

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

Заключение………………………………………………………… 11

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

          В течение  последних десятилетий были достигнуты  большие успехи  в конструировании  и анализе комбинаторных алгоритмов. С одной стороны, было обнаружено  много новых, более эффективных  методов решения комбинаторных  задач с помощью ЭВМ, с другой — получены теоретические результаты, свидетельствующие все более явно о том, что для широкого класса проблем не существует «достаточно эффективных» алгоритмов. Эффективные комбинаторные алгоритмы находят применение во многих областях нечисленной обработки информации, особенно в дискретной оптимизации и в исследовании операций.

         В настоящей работе представлены  некоторые разделы комбинаторики,  причем особое внимание уделено  основным понятиям теории графов  и алгоритмическому подходу  - рядом с обсуждаемой комбинаторной проблемой приводится алгоритм ее решения. Этот алгоритм представляет собой сжатый вариант программы, написанных на Паскале образном языке.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Основные понятия

 

    В этом разделе приводятся  основные определения и обозначения,  относящиеся к используемым логическим  и теоретико-множественным понятиям, а также представленные в приводимом ниже алгоритме.

        Начнем с  логических и теоретико-множественных  понятий Будем употреблять логические  связки Ú (или), Ù (и), Ø (не), Þ (если . . ., то), Û (тогда и только тогда, когда). Тот факт, что x есть элемент множества X, будем записывать в виде x Î X, его отрицание — в виде x Ï X. Множество тех элементов множества X, которые удовлетворяют условию Φ, будем обозначать через {x Π X: Φ} (или {x: Φ}, если известно, о каком множестве X идет речь), запись же {a₁, . . . , a_n} будет обозначать множество, элементы которого суть a₁, . . . , a_n (в частности, единственным элементом множества {a} является a). Теоретико-множественные операции объединения, пересечения и разности обозначаются соответственно Ç, È и \, пустое множество обозначается Æ. Тот факт, что множество A содержится в множестве B (т.е. A есть подмножество множества B), будет записываться в виде A Í B или B Ê A (всегда имеют место включения ÆÍ A, A Í A); символ «Ì» зарезервирован для случая, когда исключается равенство A = B (при этом будем говорить, что A есть собственное подмножество множества B). Множество всех подмножеств множества X  будем обозначать через r(X), мощность множества X (т.е. число его элементов) — через |X|.

        Последовательность длины n, члены которой суть a₁, . . . , a_n, будем обозначать через ( a₁, . . . , a_n), либо просто через a₁, . . . , a_n. Последовательность (a, b) длины два будем называть упорядоченной парой. Декартово произведение A´B множеств A и B определяется как множество всевозможных пар (a, b), где aÎ A, bÎ B. Под бинарным отношением (с левой областью A и правой областью B) подразумевается произвольное подмножество RÍ A´ B. Если A = B, то будем говорить о бинарном отношении на множестве A. Вместо (a, b)Î R часто пишут aRb.

       По  поводу отношения R на множестве X говорят, что оно:

• (а) рефлексивно, если xRx для каждого xÎ X,

• (б) транзитивно, если (xRy Ù yRz) Þ xRz для произвольных x, y, z Î X,

• (в) симметрично, если xRy Þ yRx для произвольных x, yÎ X,

• (г) антисимметрично, если (xRy Ù yRx) Þ x = y для произвольных x, y Î X.

        Произвольное  бинарное отношение, обладающее  свойствами рефлексивности, транзитивности  и симметричности, называется отношением эквивалентности, а обладающее свойствами рефлексивности, транзитивности и антисимметричности, — отношением частичной упорядоченности. Отношение частичной упорядоченности обычно обозначается через «£», а пара (X, £ ) называется частично упорядоченным множеством. Будем применять также очевидные обозначения, такие как

x ³ y для y £ x,  x < y для x £ y Ù x¹ y и т.д. Примером частично упорядоченного множества может служить множество целых чисел с отношением делимости, множество целых (или вещественных) чисел с

обычным отношением меньше или равно «£», а также множество r(X) с отношением включения Í.

        Если функция  (отображение) f сопоставляет каждому элементу x Î X элемент f(x) Î Y , то будем писать f : X → Y (такая функция может трактоваться как отношение R Í X ´ Y с тем свойством, что для каждого

 x Î X существует в R точно одна пара вида (x, y), y Î Y , для наших же целей достаточно, однако, интуитивного понятия функции). Для произвольных

AÎX, BÎ Y определим

f(A) = {y Î Y : существует такое x Î A, что y = f(x)}

f⁻¹(B) = {x Î X : f(x) Î B}

(вместо f⁻¹({b}) будем просто писать f⁻¹(b)).

        Если f(X) = Y , то будем говорить о функции из X на Y . Функция

f : X → Y называется обратимой (взаимно однозначной), если для произвольных  a, b Î X  верно что a ¹  b Þ f(a) ¹ f(b).

        Мы часто  будем использовать понятие графа.  Под неориентированным графом (или короче графом) будем понимать такую произвольную пару G = (V,E), что E Í{{u, v} : u,v Î V Ù u ¹ v}.

        Ориентированным  графом (или орграфом) будем называть такую произвольную пару G =(V,E), что EÎ V´ V и в обоих случаях множества V и E будем называть

соответственно множеством вершин и множеством ребер графа G.

         Граф обычно  изображается на плоскости в  виде множества точек, соответствующих  вершинам, и соединяющих их линий, соответствующих ребрам (дуги). Линия, изображающая ребро {u, v}, или (u, v), соединяет точки, изображающие вершины u,v причем во втором случае стрелка обозначает направление от u к v (рис. 1.1).

 

 

         

 

 

Рис 1.1: а) неориентированный граф; б) ориентированный граф.

          В контексте  определенного графа G = (V,E) будем часто использовать обозначения u - v, u → v вместо {u, v} Î E и (u, v)Î E соответственно. Если ребро e имеет вид {u, v} или (u, v), то будем говорить, что ребро e инцидентно вершинам u и v, в то время как вершины u и v смежны между собой. Степень вершины определим как число ребер, инцидентных ей. Для вершин орграфа определяются полустепени захода (число заходящих в вершину дуг) и исхода (число выходящих дуг). Степень вершины определяется как сумма полустепеней захода и исхода. Вершину нулевой степени будем называть изолированной (например, вершина v5 на рис.1.1, а)). Путем в графе G = (V,E) назовем последовательность вершин v₀, v1, . . . , v_n, такую, что k ≥ 0 и v_i - v_i+1 (или v_i →v_i +1, если граф G — ориентированный), i = 0, . . . , k - 1. Вершины v₀ и v_k будем называть соответственно началом и концом пути, а число k — длиной пути. Путь, начало и конец которого совпадают, будем называть циклом. Если все вершины пути v₁, . . . , v_k различны, то будем говорить об элементарном пути. Соответственно цикл v₁, . . . , v_k (v₁ = v_k) будем называть элементарным, если вершины v₁, . . . , v_k  различны. Подграфом графа G = (V,E) будем называть такой произвольный граф G¢ = (V¢,E¢), что V¢Í V и E¢Í E.

         Пусть G = (V,E) — произвольный неориентированный граф, и пусть

 vÎ V. Пусть A — множество тех вершин u Î V , к которым существует путь из v. Множество A вместе с ребрами графа G, инцидентными вершинам из A, определяет некоторый подграф, называемый компонентой связности графа G. Очевидно, что множества вершин компонент связности произвольного графа попарно не пересекаются. Например, для графа на рис.1.1, а это суть множества V₁ = {v₁, v₂, v₃, v₄, v₆}, V₂ = {v₅} и V₃ = {v₇, v₈, v₉, v₁₀, v₁₁, v₁₂}.

         Будем говорить, что графы G = (V,E), G¢ = (V¢,E¢) изоморфны, если существует такое взаимно однозначное отображение f из V на V¢, что для произвольных  u, v Î V имеем

{u, v}Π E Û {f(u), f(v)} Î E¢ ((u, v) Î E Û (f(u), f(v)) Î Е¢

в случае ориентированных  графов. Обычно изоморфные графы не различаются между собой.

        Для произвольного вещественного  числа x мы будем употреблять обозначения éxù и ëxû  соответственно для наибольшего целого числа, не превосходящего x, и для наименьшего целого числа, не меньшего x, например ë3.5û = 3, é3.5ù = 4, ë-3.5û = -4, é-3.5ù = -3.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

        Перейдем теперь к понятиям, связанным  с алгоритмами. Алгоритмы будем  обычно записывать на языке программирования, являющимся неформальной версией языка Паскаль. Если реализация какого-либо фрагмента программы очевидна, но трудоемка и затемняет идею алгоритма, то такой фрагмент будем иногда заменять описанием на естественном языке. Мы будем также применять неформальные конструкции, такие как, например, циклы (for x Î X do P (выполнять команду P для всех элементов x множества X в произвольной последовательности)) и т.д. Будем обычно опускать описания типов и переменных. Переменная, появляющаяся в процедуре, рассматривается как локальная для данной процедуры, исключая тот случай, когда в комментарии сказано что-либо иное. Строки программы нумеруются так, чтобы можно было указать на «цикл 17», «блок 9» и т.д.

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

 

Рис 1.2: а) Гамильтонов  путь в графе; б) Граф, в котором  не существует гамильтонова пути.

 

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

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

         Вернемся к конкретной задаче  существования гамильтонова пути. Очевидный алгоритм, который мы можем применить, это «полный перебор всех возможностей».

         Опишем теперь общий метод,  позволяющий значительно сократить  число шагов в алгоритмах типа  полного перебора всех возможностей. Чтобы применить этот метод,  искомое решение должно иметь вид последовательности  (x₁, . . . , x_n). Основная идея метода состоит в том, что мы строим наше решение последовательно, начиная с пустой последовательности ε (длины 0). Вообще, имея данное частичное решение (x₁, . . . , x_n), мы стараемся найти такое допустимое значение x_i+1, относительно которого мы не можем сразу заключить, что

(x₁, . . . , x_i, x_i +1) можно расширить до некоторого решения  (либо

(x₁, . . . , x_i+1) уже является решением). Если такое предполагаемое, но еще не использованное значение x_i+1 существует, то мы добавляем его к нашему частичному решению  и продолжаем процесс для последовательности (x₁, . . . , x_i, x_i+1). Если его не существует, то мы возвращаемся к нашему частичному решению (x₁, . . . , x_i−1) и продолжаем наш процесс, отыскивая новое, еще не использованное допустимое значение x_i¢ — отсюда название «алгоритм с возвратом» (англ.: backtracking).

        Точнее говоря, мы предполагаем, что для каждого k > 0 существует некоторое множество A_k, из которого мы будем выбирать кандидатов для k-й координаты частичного решения. Очевидно, что множества A_k должны быть определены таким образом, что для каждого целочисленного решения (x₁, . . . , x_n) нашей задачи и для каждого k ≤ n множество A_k содержало элемент xk (на практике мы не можем вообще исключить ситуацию, когда множество A_k содержит некоторые «лишние» элементы, не появляющиеся в k-й координате ни одного целочисленного решения).              Мы предполагаем также, что существует некоторая простая функция, которая произвольному частичному решению (x₁, . . . , x_i) ставит в соответствие значение P(x₁, . . . , x_i) (истина либо ложь) таким образом, что если P(x₁, . . . , xi)=ложь, то последовательность (x₁, . . . , x_i) несомненно нельзя расширить до решения. Если P(x₁, . . . , xi)=истина, то мы говорим, что значение xi допустимо (для частичного решения (x₁, . . . , x_i−1), но это отнюдь не означает, что (x₁, . . . , x_i−1), обязательно расширяется до полного решения. Этот процесс можно записать в виде следующей схемы:

 

 

 

 

 

1 begin

2 k := 1;

3 while k > 0 do

4 if существует еще  не использованный элемент y Î A_k,