Содержание

Введение…………………………………………………………… 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₁₂}.