Эйлеров и гамильтонов цикл
Гамильтоновы пути и циклы
Гамильтоновым циклом ( путем ) называют простой цикл (путь), содержащий все вершины графа. В графе, изображенном на рис. 8.1 слева, гамильтоновым циклом является, например, последовательность , , , , , . В графе, изображенном в центре, нет гамильтоновых циклов, но есть гамильтоновы пути, например, . В правом графе нет и гамильтоновых путей.
Рис. 8.1.
Внешне определение гамильтонова цикла похоже на определение эйлерова цикла. Однако есть кардинальное различие в сложности решения соответствующих задач распознавания и построения. Мы видели, что имеется достаточно простой критерий существования эйлерова цикла и эффективный алгоритм его построения. Для гамильтоновых же циклов (и путей) неизвестно никаких просто проверяемых необходимых и достаточных условий их существования, а все известные алгоритмы требуют для некоторых графов перебора большого числа вариантов.
Гамильтонов цикл представляет собой, с комбинаторной точки зрения, просто перестановку вершин графа. При этом в качестве начальной вершины цикла можно выбрать любую вершину, так что можно рассматривать перестановки с фиксированным первым элементом. Самый бесхитростный план поиска гамильтонова цикла состоит в последовательном рассмотрении всех этих перестановок и проверке для каждой из них, представляет ли она цикл в данном графе. Такой способ действий уже при не очень большом числе вершин становится практически неосуществимым ввиду быстрого роста числа перестановок – имеется ! перестановок из элементов с фиксированным первым элементом.
Более рациональный подход состоит в рассмотрении всевозможных простых путей, начинающихся в произвольно выбранной стартовой вершине , до тех пор, пока не будет обнаружен гамильтонов цикл или все возможные пути не будут исследованы. По сути дела, речь тоже идет о переборе перестановок, но значительно сокращенном – если, например, вершина не смежна с вершиной , то все ! перестановок, у которых на первом месте стоит , а на втором , не рассматриваются.
Рассмотрим этот алгоритм подробнее. Будем считать, что граф задан окрестностями вершин: для каждой вершины задано множество вершин, смежных с . На каждом шаге алгоритма имеется уже построенный отрезок пути, он хранится в стеке PATH. Для каждой вершины , входящей в PATH, хранится множество всех вершин, смежных с , которые еще не рассматривались в качестве возможных продолжений пути из вершины . Когда вершина добавляется к пути, множество полагается равным . В дальнейшем рассмотренные вершины удаляются из этого множества. Очередной шаг состоит в исследовании окрестности последней вершины пути PATH. Если и в имеются вершины, не принадлежащие пути, то одна из таких вершин добавляется к пути. В противном случае вершина исключается из стека. Когда после добавления к пути очередной вершины оказывается, что путь содержит все вершины графа, остается проверить, смежны ли первая и последняя вершины пути, и при утвердительном ответе выдать очередной гамильтонов цикл.
Алгоритм 2. Поиск гамильтоновых циклов
- выбрать произвольно вершину
- while do
- if
- then взять
- if вершина не находится в PATH
- then
- if PATH содержит все вершины
- then if смежна с
- then выдать цикл
- else удалить вершину из PATH
Этот алгоритм очень похож на алгоритм поиска в глубину и отличается от него по существу только тем, что открытая вершина, когда вся ее окрестность исследована, не закрывается, а опять становится новой (исключается из стека). В начале все вершины новые. Процесс заканчивается, когда все вершины опять станут новыми. На самом деле это и есть поиск в глубину, только не в самом графе, а в дереве путей. Вершинами этого дерева являются всевозможные простые пути, начинающиеся в вершине , а ребро дерева соединяет два пути, один из которых получается из другого добавлением одной вершины в конце. На рис. 8.2 показаны граф и его дерево путей из вершины .
Рис. 8.2.
Источник
Граф Кёнигсбергских мостов. Этот граф не является полуэйлеровым, поэтому решения не существует
Каждая вершина этого графа имеет чётную степень, поэтому этот граф – эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл
Эйлеров путь (эйлерова цепь) в графе – это путь, проходящий по всем рёбрам графа и притом только по одному разу. (ср. Гамильтонов путь)
Эйлеров цикл – эйлеров путь, являющийся циклом, то есть замкнутый путь, проходящий через каждое ребро графа ровно по одному разу.
Эйлеров граф – граф, содержащий эйлеров цикл.
Полуэйлеров граф – граф, содержащий эйлеров путь.
Существование эйлерова цикла и эйлерова пути[править | править код]
В неориентированном графе[править | править код]
Согласно теореме, доказанной Эйлером, эйлеров цикл существует тогда и только тогда, когда граф связный или будет являться связным, если удалить из него все изолированные вершины, и в нём отсутствуют вершины нечётной степени.
Эйлеров путь в графе существует тогда и только тогда, когда граф связный и содержит не более двух вершин нечётной степени.[1][2] Ввиду леммы о рукопожатиях, число вершин с нечётной степенью должно быть чётным. А значит эйлеров путь существует только тогда, когда это число равно нулю или двум. Причём, когда оно равно нулю, эйлеров путь вырождается в эйлеров цикл.
В ориентированном графе[править | править код]
Ориентированный граф содержит эйлеров цикл тогда и только тогда, когда он сильно связан или среди его компонент сильной связности только одна содержит ребра (а все остальные являются изолированными вершинами) и для каждой вершины графа её входящая степень равна её исходящей степени , то есть в вершину входит столько же ребер, сколько из неё и выходит: .
Так как эйлеров цикл является частным случаем эйлерова пути, то очевидно, что ориентированный граф содержит эйлеров путь тогда и только тогда, когда он содержит либо эйлеров цикл, либо эйлеров путь, не являющийся циклом. Ориентированный граф содержит эйлеров путь, не являющийся циклом, тогда и только тогда, когда существуют две вершины и (начальная и конечная вершины пути соответственно) такие, что их полустепени захода и полустепени исхода связаны равенствами и , а все остальные вершины имеют одинаковые полустепени исхода и захода: [3].
Поиск эйлерова пути в графе[править | править код]
Можно всегда свести задачу поиска эйлерова пути к задаче поиска эйлерова цикла. Действительно, предположим, что эйлерова цикла не существует, а эйлеров путь существует. Тогда в графе будет ровно 2 вершины нечётной степени. Соединим эти вершины ребром, и получим граф, в котором все вершины чётной степени, и эйлеров цикл в нём существует. Найдём в этом графе эйлеров цикл (алгоритмом, описанным ниже), а затем удалим из ответа несуществующее ребро.
Поиск эйлерова цикла в графе[править | править код]
Алгоритм Флёри[править | править код]
Основной источник: M. Fleury. Deux problèmes de Géométrie de situation (фр.) // Journal de mathématiques élémentaires [et spéciales]. – Paris: C. Delagrave, 1883. – Vol. 2, livr. 2nd ser.. – P. 257-261.
Алгоритм был предложен Флёри в 1883 году.
Пусть задан граф . Начинаем с некоторой вершины и каждый раз вычеркиваем пройденное ребро. Не проходим по ребру, если удаление этого ребра приводит к разбиению графа на две связные компоненты (не считая изолированных вершин), т.е. необходимо проверять, является ли ребро мостом или нет.
Этот алгоритм неэффективен: время работы оригинального алгоритма O(|E|2). Если использовать более эффективный алгоритм для поиска мостов[4], то время выполнения можно снизить до , однако это всё равно медленнее, чем другие алгоритмы.
Алгоритм может быть распространен на ориентированные графы.
Алгоритм на основе циклов[править | править код]
Будем рассматривать самый общий случай – случай ориентированного мультиграфа, возможно, с петлями. Также мы предполагаем, что эйлеров цикл в графе существует (и состоит хотя бы из одной вершины). Для поиска эйлерова цикла воспользуемся тем, что эйлеров цикл – это объединение всех простых циклов графа. Следовательно, наша задача – эффективно найти все циклы и эффективно объединить их в один.
Реализовать это можно, например, так, рекурсивно:
procedure find_all_cycles (v) var массив cycles 1. пока есть цикл, проходящий через v, находим его добавляем все вершины найденного цикла в массив cycles (сохраняя порядок обхода) удаляем цикл из графа 2. идем по элементам массива cycles каждый элемент cycles[i] добавляем к ответу из каждого элемента рекурсивно вызываем себя: find_all_cycles (cycles[i])
Достаточно вызвать эту процедуру из любой вершины графа, и она найдёт все циклы в графе, удалит их из графа и объединит их в один эйлеров цикл.
Для поиска цикла на шаге 1 используем поиск в глубину.
Сложность полученного алгоритма – O(M), то есть линейная относительно количества рёбер М в данном графе.
Примечания[править | править код]
См. также[править | править код]
- Гамильтонов цикл
- Граф (математика)
- Задача о ходе коня
- Дискретная математика
- Проблема семи мостов Кёнигсберга
- Список объектов, названных в честь Леонарда Эйлера
Ссылки[править | править код]
- Реализация алгоритма поиска эйлерова цикла (краткие описания и программы на C++)
- Реализация алгоритма поиска эйлерова цикла на codenet.ru
- Теория графов и комбинаторика
- Графы. Циклы и разрезы (ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ, Визуализаторы)
- Е. Гик. «Шахматы и математика» Конь-хамелеон
- Weisstein, Eric W. Eulerian Circuit (англ.) на сайте Wolfram MathWorld.
Источник
Аннотация: Построение эйлерова цикла. Гамильтоновы пути и циклы.
Построение эйлерова цикла
Напомним, что эйлеровым циклом называется замкнутый маршрут, в котором каждое ребро графа встречается точно один раз. Согласно теореме 5 из “Маршруты, связность, расстояния” , для существования такого маршрута в связном графе необходимо и достаточно, чтобы степени всех вершин были четными. Теперь рассмотрим алгоритм, который находит эйлеров цикл в заданном графе при условии, что условия связности и четности степеней выполнены.
Этот алгоритм похож на алгоритм поиска в глубину: начиная с произвольно выбранной стартовой вершины , строим путь, выбирая каждый раз для дальнейшего продвижения еще не пройденное ребро. Главное отличие от поиска в глубину состоит в том, что как пройденные помечаются именно ребра, а не вершины. Поэтому одна и та же вершина может посещаться несколько раз, но каждое ребро проходится не более одного раза, так что в полученном маршруте ребра не будут повторяться. Вершины пути накапливаются в стеке . Через некоторое количество шагов неизбежно наступит тупик – все ребра, инцидентные активной (последней посещенной) вершине , уже пройдены. Так как степени всех вершин графа четны, в этот момент и пройденные ребра образуют цикл, но он может включать не все ребра графа. Для обнаружения еще не пройденных ребер возвращаемся по пройденному пути, перекладывая вершины из стека в другой стек , пока не встретим вершину , которой инцидентно непройденное ребро. Так как граф связен, такая вершина обязательно встретится. Тогда возобновляем движение вперед по непройденным ребрам, пока не дойдем до нового тупика и т.д. Процесс заканчивается, когда в очередном тупике обнаруживается, что пуст. В этот момент в стеке находится последовательность вершин эйлерова цикла.
Алгоритм 1. Построение эйлерова цикла
- выбрать произвольно вершину
- while do
- if имеется непройденное ребро
- then пометить ребро как пройденное
- else переместить вершину из в
Для обоснования алгоритма заметим сначала, что первой в стек помещается вершина , и она будет последней перемещена из в . Следовательно, она будет последней вершиной в стеке . Далее, как было отмечено выше, первый раз, когда обнаружится, что все инцидентные активной вершине ребра пройдены (т.е. будет выполняться ветвь else в строке 8), активной будет стартовая вершина . Значит, эта вершина будет первой перемещена из в . Итак, по окончании работы алгоритма в начале и в конце последовательности вершин, содержащейся в стеке , находится вершина . Иначе говоря, если эта последовательность представляет маршрут (а далее будет показано, что так оно и есть), то этот маршрут замкнут.
Далее отметим, что в конечном итоге каждое ребро будет пройдено. Действительно, допустим, что в момент окончания работы алгоритма имеются еще не пройденные ребра. Поскольку граф связен, должно существовать хотя бы одно непройденное ребро, инцидентное посещенной вершине. Но тогда эта вершина не могла быть удалена из стека , и не мог стать пустым.
Будем говорить, что ребро представлено в стеке ( или ), если в какой-то момент работы алгоритма в стеке рядом находятся вершины и . Ясно, что каждое ребро графа будет представлено в стеке и что каждые две вершины, расположенные рядом в этом стеке, образуют ребро. Допустим, в какой-то момент из стека в стек перемещается вершина , а непосредственно под ней в стеке находится вершина . Возможно, что вершина будет перемещена из в при следующем повторении цикла while, тогда ребро будет представлено в стеке . Другая возможность – между перемещением вершины и следующим перемещением, т.е. следующим выполнением ветви else, будет несколько раз выполнена ветвь then (строки 6,,7). Это означает, что будет пройдена некоторая последовательность ребер, начинающаяся в вершине . Ввиду четности степеней эта последовательность может закончиться только в вершине . Значит, и в этом случае следующей за вершиной будет перемещена из в вершина . В любом случае ребро будет представлено в стеке . Из этого рассуждения видно, что последовательность вершин в стеке является маршрутом и что каждое ребро графа в конечном итоге будет содержаться в этом маршруте, причем один раз.
При каждом повторении цикла while в рассмотренном алгоритме либо проходится одно ребро, либо одна вершина перемещается из в . Последнее можно трактовать как прохождение уже пройденного однажды ребра в обратном направлении. Каждое ребро в каждом направлении будет пройдено один раз, поэтому общая трудоемкость этого алгоритма оценивается как . Необходимо только оговориться, что этот вывод, как и аналогичные заключения об алгоритмах обхода в первых разделах этой главы, справедлив лишь при определенных предположениях о том, как задан граф. Способ задания должен обеспечить возможность быстрого просмотра множества ребер, инцидентных данной вершине. Подходящим является, например, задание графа списками инцидентности, в которых для каждой вершины перечисляются инцидентные ей ребра. Необходимо также иметь возможность быстро пометить ребро как пройденное или проверить, пройдено ли данное ребро. Для этого подходящей структурой может служить характеристический массив на множестве ребер.
Источник
может ли кто-нибудь сказать мне разницу между гамильтоновым путем и путем Эйлера. Они похожи!
43
автор: Md. Abu Nafee Ibna Zahid
8 ответов
An Эйлеров путь – это путь, который пересекает каждое ребро ровно один раз без повторения, если он заканчивается в начальной вершине, то это цикл Эйлера.
A путь гамильтониана проходит через каждую вершину (обратите внимание не на каждое ребро), ровно один раз, если она заканчивается в начальной вершине, то это Гамильтонов цикл.
в пути Эйлера вы можете пройти через вершину более одного раза.
в Гамильтоновом пути вы не можете пройти через все стыки.
Эйлеров путь должен посетить каждый edge ровно один раз, в то время как Гамильтонов путь должен посетить каждый вершинный ровно один раз.
Определения Теории Графов
(в порядке убывания общности)
прогулка: последовательность ребер, где конец одного ребра обозначает начало следующего ребра
след: прогулка, которая не повторяет ни края. Все тропы-это тропы.
путь: прогулка, где каждая вершина проходит ровно один раз. (пути, используемые для ссылки на open теперь определение изменилось) свойство пересечения вершин только один раз означает, что ребра также пересекаются только один раз, поэтому все пути являются тропами.
Гамильтоновы пути и эйлеровы тропы
путь гамильтониана посещение каждая вершина в графе (ровно один раз, потому что это путь)
Эйлера след посещение каждое ребро в графе ровно один раз (поскольку это тропа, вершины вполне могут пересекаться не один раз.)
Гамильтонов путь посещает каждый узел (или вершину) ровно один раз, а Эйлеров путь пересекает каждое ребро ровно один раз.
Они связаны, но не являются ни зависимыми, ни взаимоисключающими. Если граф имеет цикл Эурлера, он может или не может также иметь Гамильтонов циль и наоборот.
циклы Эйлера посетить каждый edge в графа ровно один раз. Если в графе есть вершины с более чем двумя ребрами, то по определению цикл будет проходить через эти вершины не один раз. В результате вершины могут повторяться, но ребра не может.
Гамильтоновы циклы посетить каждый вершинный на графике ровно один раз (аналогично проблеме коммивояжера). В результате ни ребра, ни вершины не могут быть повторены.
Я буду использовать общий пример в биологии; реконструкция генома путем создания образцов ДНК.
de-novo assembly
чтобы построить геном из коротких считываний, необходимо построить график этих считываний. Мы делаем это, разбивая считывания на k-мер и собирая их в график.
мы можем восстановить геном, посетив каждый узел один раз, как на диаграмме. Это известно как гамильтониан путь.
к сожалению, построение такого пути NP-сложно. Невозможно вывести эффективный алгоритм его решения. Вместо этого в биоинформатике мы строим Эйлеров цикл, где ребро представляет собой перекрытие.
путь Эйлера-это путь, который использует каждый край графа ровно один раз.и у него должно быть ровно две нечетные вершины.путь начинается и заканчивается в другой вершине. Гамильтонов цикл-это цикл, содержащий каждую вершину графа, поэтому вы не можете использовать все ребра графа.
путь Эйлера-это граф, использующий каждое ребро (Примечание) графа только один раз. Схема Эйлера-это путь Эйлера, который возвращает ему начальную точку после покрытия всех краев.
в то время как путь Гамильтона-это граф, который охватывает все вершины(Примечание) ровно один раз. Когда этот путь возвращается к своей начальной точке, этот путь называется цепью Гамильтона.
Источник
: 4 4 . : . 3. , 20032 4 1. 4 1. 5 2. 5 3. 6 4. 8 5. 9 2. 11 1. 11 2. 11 3. 13 4. . 15 5. 15 6. 16 8. 18 9. 19 10. 21 3. 23 1. 24 2. 26 3. 27 4. 29 5. 30 6. 35 7. 35 8. 37 9. 39 41 , . ( ). , , , , , . G(V,E) : v0 ,e1 , en ,vn , . v0 = vn , , . , . ( , ) , . ; . . , . , . , , . , , , . , ” “. , ( ), . , . , , , . 1.. ( ), , , . ( ), , , . , , (, ). , . , – , . : – , , , . , , . 2., ? -, : , . -, . . 1 . G , , . . . , . , G , . . G , . x0 , , x0 . , . , . G , , xi , – . , , – , (0 ), . xi , Ԓ, xi . Ԓ, . x0 xi , Ԓ , , xi x0 . , Ԓ . xj , . Ԓ, xj , , . . , , : . #1. G . #2. G , , 2 . . 3.. , , , . , , .. . . : G(V,E), . , [v] , v. : . S:= { } select vV { } v→S { v S} while S≠ do v←S; v→S {v } if [v]= then v←S; yield v else select u[v] { } u→S { u } [v]:=[v]{u}; [u]:=[u]{v} { (v,u)} end if end while . . , , , , , . , , . , v , . , , S. , . v , , , . , , . : 1. v vu 1. u. 2. w – , 1 k – , . w, , . k+1 . , . : , , .. . : . 2. G(V,E) . G(V,E). , , : 1. ( , ); 2. , . . , . v, u, v ≠ u. v u, , G1 v u. #2 1 G1 P v u. u P G1 , u G2 , , . ( v = u, , , u). , . , G , , u, , , , 2). 4., , . , 1. , G ? , G , . 2. G . , G , ( nj c(aj ), nj , aj , c(aj ) ) . , G , , 2) , , : 1. . . , . G , . c(aj ) . G, G . . 2. . , , , . , ( , ..). 3. , . ( ) . 2) . 5.G(X,A). X ( X+ ) , ( X- =XX+ ) . di xiX A (.. ) 2m. , , . di , |X- | . M ( μij ) G xi xj X- , , .. X- X- . μij M 1/2|X- | , . , , μij , ( ). μijM G- (M). G μij , G- (M) ( μij ) , .. 3. , G, M, G- (M) , G. , (xi , xj ) G l , G- (M) l ( l-1 ) xi xj , G- (M). . . G, , xi , . (, , ). (xi , xk ). dk xk G dk , (xi ,xk ) , xi xk . dk , dk , xk (.. ). , , . , xi , xi xr X-. xr. xi X-. M G, , , , G-(M) , . , , , M* ( ), . , G, , G M*. , G-(M*). :1. [cij ] G. , |X- |* |X- | D =[dij ], dij , xiX- xjX-. 2. M* X-, ( D ). . 3. xα xβ, μαβ ( xα xβ), dαβ, 1. G, μαβ, M*, G-(M*). 4. G-(M*), [cij] ( ), , G. (xi,xj) xi xj G-(M*). , . , 2 , μij μpq (, xi xj xp xq ) . (xa , xb ), xi xq ( xi xb xb xq ) xp xj ( xp xa xa xj ) 2cab , , . , G- (M* ) , .. G . 1859 . , , . , 20 . 1., , , . , , , . , . . , , . , . . G , . , , v1 ,,vp G u1 ,,up {(vi ,ui )}{(ui ,vi+1 )}. v d(v), , . do (v) di (v) . 2., , . , NP-. : G , . . . G(V,E) c n (n ≥ 3) d(v) ≥ n/2 vV, G . . . G . G u1 , ,un , G , G:= G + u1 + + un . v, u1 , w, ,v G, vG, u1G, u1G. v u1 , G . wG, w {u1 ,,un }, u1 . , v w, u1 . , v,u1 ,w, ,u,w, ,v w, w, v v, v,v, ,w,w, ,v u1 , w, ,v . , G, v, , w. w G d(w) ≥ p/2+n , d(v) ≥ p/2+n. ( v) n+p-1. , : n+p-1 = d(v)+d(V) ≥ d(w)+d(v) ≥ p/2+n+p/2+n = 2n+p. , 0 ≥ n+1, , n > 0. . G(V,E) n ≥ 3 u v : d(u)+d(v) ≥ n (u,v)E, G . G : : d(vk ) ≥ k+1 k < n/2. : d(vi ) ≤ i d(vk ) ≤ k => d(vi )+d(vk )≥n (k≠i) : d(vk ) ≤ k ≤ n/2 => d(vn-k ) ≥ n-k. , , , H(p) p , G(p) p . , , (, ) . , , .
N = 8; d(vi ) = 3; 3 ≥ 8/2 = 4 , : M = (1, 2, 3, 4, 5, 6, 7, 8, 1) 3.. n , . pi ( pj ), (pi ,pj ). . , , n . , pi (i=1,2,,n), . , , . , , , .. ? . 1. G, G ( ), . 2. G, C=[cij ], , . , G , , . . , , . , . , .. , () , . , , .. , (1) (2). , G , . , .. , , G (.. 1). , G . 1). G1 [cij ] , . . . , (1) . G1 . 1 , ĉ1 . G1 , ĉ1 , G2 . G2 2 , ĉ2 . G2 , ĉ2 , , Gm+1 , . m Gm ( ĉm ) , Gm+1 , G1 , , ĉm . , . , , G G1 , G, , G, , . G1 ( ), G . , G . , , , . , (1) (2) ( ) (1) , (2), . 4. ., , G . , , , , . , . , , . . . , , , . 5.. x1 , x2 , ,xk-1 , xk x2 *x3 * xk-1 , x1 xk . B=[β(i,j)] (nn)- , β(i,j) xj , xi xj . , PL = [pL (i ,j)], pL (i,j) L (L≥1) xi xj xi ≠xj . pL (i,i)=0 i. B*PL = PL+1 = [pL+1 (s,t)] .. pL+1 (s,t) xs xt l+1. xk xt , pL (k,t), , , , , pL (k,t) xs . , pL+1 (s,t) , xs ( ), pL+1 (s,t). PL+1 =[pL+1 (s,t)], 0, L+1. B*PL+1 , PL+2 .., Pn-1 , ( n-1) . Pn-1 G, . , , B*Pn-1 ( ). , P (.. P1 ) A , . . (.. L ) PL L, . , L , , L+1, , , L, L . , , L , , PL , L, . . , , B*Pn-1 , pn-1 (1,1). PL , PL . n . , PL/1, , 20 , 4. IBM 360/65 120 000 . , 1.8 . . 6., , , , , , , . ( , ), . . , , . (kn)- 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. xr . 2. , S, n-1, .. . 2) : 1. G (xr ,x1 ), . 2. (xr ,x1 ) . (1) (2b) , (2a) ( ), ( ) . xr S, S = {x1 ,a,b,c, ,xr-1 }, S , xr , xr-1 M. , .. , S x1 , S, S . , , , . . :
“2” 1) S = {1} 2) S = {1, 2} 3) S = {1, 2, 3} 4) S = {1, 2, 3, 4} 5) S = {1, 2, 3, 4, 5} – 4→3 4→5 6) S = {1, 2, 3, 4} 7) S = {1, 2, 3} 3→1 3→2 3→4 8) S = {1, 2} 9) S = {1} “3” 10) S = {1, 3} 3→2 11) S = {1, 3, 2} 2→1 12) S = {1, 3} 2→3 13) S = {1, 3, 4} 3→4 4→5 14) S = {1, 3, 4, 5, 4} 5→ 15) S = {1, 3, 4} 16) S = {1, 3} 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 = 8.. , S = {x1 ,x2 , ,xr } , S, x*S. , , G(X,) , . 1. xXS, x(xr ) -1 (x) S, , S x* , x, x , , , . , x , S . 2. xXS, x-1 (x1 ) (x) S{x* } x* , x* S, x x1 . , S {x* }, , S , x* . (a) (b) , , , ( 20 ) . , 2 . 9., , , . S0 (S0 , ) – . , , S0 , . , , ; . . , S0 S1 , S2 , . – ( , ). , , , , . , ( , ), , (- , ). , , (, S0 ), G (. S0 ), , , , . , . , , G, , . Gk (Xk ,k ), k , . S0 ( ), xj , , .. Gk , S0 e(S0 ) xj . xj S0 : 1. Gk , .. 1. , xj e(S0 ), (e(S0 ), xj ); 2. , xj S0 ; 3. , xj Sj , , Sj S0 . 2. , , Gk (Xk ,k ). x Gk , S0 , S1 , , , .. |-1k (x)|=1, , v= -1k (x), (v, x). x Gk , , , .. |k (x)|=1, , x, (x, k (x)). , . 2 , . 3. Gk , , .. , . , , Gk+1 , Gk . , xj S0 ( ) x 2 , . xj S0 xj , S0 , k [e(S0 )]. , k [e(S0 )] (.. e(S0 ) S0 ..). , 1 2 k, Gk+1 Gk k, . ( ) 2 , , . ( , ), . , 2 ( ) Gk . , , , . , .. ( k) 2 , . xj S0 . 1, 2, 3 , . 10., . , , . , . 200 , . . 1 ; 3 5. , , , . , 1 , . , T n 3 5, : T = 0.8510-4 100.155n ( CDC6600). . ( ) n. 3 5 2. , , ( 20 ) 50% . . 3, ( ). , . , , . , , , 3 5, . , 1-3, . , . , 20 3 5, 2 , , .1
.2 : T0 – , T1 –
( 18). 1.2 , 0.07 . CDC6600. ( – ) . 1934 , , . ( ) , . , . , , NP- . 1.. ( ) , 1,2,3..n . . , () ? , . , jÎ=(1,2,,n). t=(j1 ,,jn , j1 ), j1 ,,jn ; j1 , , . ij . n2 xij , 0, i- j- 1 . (1) (2). (1) (2) n n2 (3). (3) , t, F , : (4) . , ij , : o , .. jÎ: Cij ³ 0; Cjj = ∞ (5) ( ), o , .. i, j: ij = ji (6) o , .. : Cij + Cjk ³ Cik (7) . , , , (5)-(7) . (7) (, ij , : , ). : , (7) , – . (5)-(7) . . t=(j1 ,j2 ,,jn ,j1 ) t=(j1 ,jn ,,j2 ,j1 ) . (n-1)! j1 , n-1 (n-1)! . . , .. : t t. , X . , , (i,j) , xij =0 , xij =1. , 0, , . . ( ). , (1-4) . (2) , ; (3) – ; (4) – , N , . (4) . , , (4) T R , R . , NR £ (N -1), R < N, R ¹ 0. , , N. , Ui , , , (4). Xij (j- i-) (4) Ui -Uj £ N-1, Ui Uj . R- i- j-, Xij = 1. Ui Uj Ui = R, Uj = R+1, (4) : Ui -Uj +NXij £ R-(R-1)+N = N-1 , Ui Uj , , N , (4) . , (1)-(4) . : n , (i,j)= ij . . , – , . , , . . , . 2., , , . , . , . , , . , , . . 2, . 1. 2, 3, 4; , . , . , . , . , , , , 1000 ? , , , . , , , . fB – , fA – , . , fA / fB ≥1, , . , : fA /fB ≥ 1+nε (8) , , ε≥0, , , . ε . (8), , ε. , , . G(V,E) : G , fB = n. , , . , , , , . , 1+nε. fA ³ (n-1)+(1+nε) fA /fB = 1+nε, .. ε (8). ε , ε . . , , . 1980 . – , . , (7). 3.. . . – , , . 5. , d[1,3] £ d[1,2]+d[2,3] d[3,5] £ d[3,4]+d[4,5]. , : d[1,3]+d[3,5]£d[1,2]+d[2,3]+d[3,4]+d[4,5]. : d[1,5] £ d[1,3]+d[3,5]. , d[1,5] £ d[1,2]+d[2,3]+d[3,4]+d[4,5] , , , ( ) . , . . 1. . G , . 2. G, 1, . 3. , 1, , . , . 1 . , .5. . . 1. ( 1) 1(4)3-(3)5-(5)4(11)6(10)2(6)1, , . 39, . 5. 2. , . 6 , 1-2-1-3-4-3-5-6-5-3-1, 1-2-3-4-5-6-1 43, . 6. . 1. . fB . LHC fB . , . . . LMT LHC . fB > LHC ³ LMT (9)
, , 2LMT > fA (10) (9) (10), 2fB > 2LHC ³2LMT ³ fA (11) .. 2fB >fA , fA /fB >1+e; e=1. . , , , . , . 4., e=1. , , brute-force enumeration – , . , . , n (n-1)!/2 (n-1)! , , , :
, (, ) m . , (.. ) . , (a1 ,,an ) (b1 ,,bn ), k ≤ n ak < bk i > k ai = bi . (), . : , ( ). , . , u=(u1 ,u2 ,,um ) u1 ,u2 ,,um v=(v1 ,v2 ,,vb ). u1 v1, uv, u1 =v1, .. . , , , 15. 1-2-3-4-5, 1-2-3-5-4, , 5-4-3-2-1. . : , 1-3-5-4-2. , , , ( 3 5). , Pi-1 , – , , Pi Pn . , Pi-1 , , , Pi-1 < Pi . , , , . Pj , j > i-1. Pi- 1 Pi Pn , Pj . , 1-4-2-3-5. 1-4-2-5-3 ( , ) .. , n n . , , 1-3-5-4-2 3-5-4-2-1 ( ) , 1, 3. 1 . (n-1)! , .. ( – 1-3-5-4-2 1-2-4-5-3). , 1 , , 1-2-6-5-4-3-1 36. 5., . , , . .. , , , , . : ( , ) , , . , () (), . .N . i j , “”. , , . ., ω0 . , ω1ij , (i,j), ω1not ij . , . ω1ij ω1not ij , .. (ω0 )<=1ij , (ω0 )<=1not ij 1ij 1not ij , , . ω1ij ω1not ij ω2ij ω2ij . 2ij 2not ij .. , . . . , . , , , , , . , . . , . (). ( ) , . . , , , , . . . . , , , . θij . cij i j (i,j) . . , (i,j) i j, . , (i,j) cij .
1 : , . , , , . ( , . . 3), , , , , (. .4). , i i . , 27, 7, 34. ( ) , , , . 2. , i- j-. , . ( ), ( ); , , . . 2 36, , . . 2. , .. , , , , . , , , , 0 34. , 34. . . . (1,2) . , 1 2 0. 1 2? 2 , ; 1 ( 6). , 1 , ; 3 0. , 1+0=1: 1 2, 1. . . 5 ( , , ). ( , , , (1,2)). , (1,2). (1,2) (1,2). , 1, 35 . , . 6 . (2,1), . . (1,2) (2,1) .
.6 1 , , , 35. .6. : ; , (1,2); , (1,2). . : – . C[1,2] . 7. (3,1) 3. , . 7
3 5+3=38. . 7 C[1,2] 3 1, C(1,2),(3,1) . 8. (2,3), (1,2) (3,1), .. [3,1,2] (2,3). 1 (. 9), , (.. , (1,2) (3,1)) 36 . C[(1,2),(3,1)] 3 (6,5). 38+3=41. 6 5, (5,6), . . 10. . , (.8). . 10, (2,6), 36+3=39, , . 11. (5,3), [3,1,2,6,5] (5,3). , 22 , (4,3) (5,4). , . : 1→2→6→5→4→3→1 36. , . , , 36 , . . , . . , , [Not(1,2)], .. 1,2, 1 ( 34+1=35). 3 (1,3), 35+3 36 . , (3,1) . 1, 36 . , . , . , . 2. , , n = 100. . , , , . 6., . . . , 1959. : , . . Dik dik i- k- ; , dik , . O(n2 ). , n . j,k. D[j,k]. j,,k. m. j,m,k. ( j,m m,k) . . , , . . , , . 7.. 9-10 . , ( , , ). 1-2-4-5-3-1, 1-2-3-4-5-1. , : , , . , . , . . , , . T[n+1], , , . . T[1], T[2], T[3] .., T[n+1]=T[1] ( ). , “i [1,2..n] C[T[i],p]+ C[p,T[i+1]]C[T[I],T[i+1]] = min, p T[i] T[i+1]. , . , , .
. , . 11. . 13. , . , 1-3-7-5-4-8-6-2-1. : D=6+7+5+2+6+5+ 13+13=57. , .. , , . ( , 1 1-3-4-5-7-8-6-2-1 58). , . , , n n . 6 . , , , , . 5-6 . , . , , , ( ). 8.( ), , , . . – , . , . . : , – ( ). . – ( ) , – . , . , , . : , , . , . , , . . , . – , . – -. , , . (TSP – traveling salesman problem). , , . , 30 , ( ). ( 30 ) – , j- j- . , 30 , . , . . ( ) , . . , 1030 , . , , , . . , , . , , . , . , ( – ). , . , , , . , . , , , . . – , – . , . , , – , , . , , . 9., . , (). . ( ) , . , (. . 1). . , (1, 2, 3, 4, 5) (0, 0, 0, 0, 0) , (1, 2, 3, 0, 0) (0, 0, 0, 4, 5). – . 1. (), .. . , . . , , . ( ), . . . , , . , . . . , , . , , , . , . , . 20 . . 20, , . . , , , , . . . , , , , 510%. 25 . , . , ( ) – 5%, 1%. 90% . , 75 ( ). 1. .. , .. , .. . , 1998 . 2. . . : , , 1978 . 3. .. . , , 2001 . 4. .. . , , 1999 . 5. . . , , 1982 . 6. www.codenet.ru 7. www.algolist.ru 1000 76 43 38 51 42 19 80 42 1000 49 26 78 52 39 87 48 28 1000 36 53 44 68 61 72 31 29 1000 42 49 50 38 30 52 38 47 1000 64 75 82 66 51 83 51 22 1000 37 71 77 62 93 54 69 38 1000 26 42 58 66 76 41 52 83 1000 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Источник