Теоретические аспекты построения гамильтоновa цикла

Рассматривается несколько подходов к решению проблемы построения гамильтонова цикла в плоском графе, которая часто возникает при компьютерном моделировании различных задач производственного планирования, маршрутизации данных и других. Розглядається декілька підходів до вирішення проблеми побудови га...

Full description

Saved in:

Bibliographic Details
Published in:	Теорія оптимальних рішень
Date:	2011
Main Author:	Павленко, В.Б.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2011
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/46787
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Теоретические аспекты построения гамильтоновa цикла / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 150-155. — Бібліогр.: 5 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859721532921610240
author	Павленко, В.Б.
author_facet	Павленко, В.Б.
citation_txt	Теоретические аспекты построения гамильтоновa цикла / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 150-155. — Бібліогр.: 5 назв. — рос.
collection	DSpace DC
container_title	Теорія оптимальних рішень
description	Рассматривается несколько подходов к решению проблемы построения гамильтонова цикла в плоском графе, которая часто возникает при компьютерном моделировании различных задач производственного планирования, маршрутизации данных и других. Розглядається декілька підходів до вирішення проблеми побудови гамільтонова цикла в плоскому графі, яка часто виникає при комп'ютерному моделюванні різних завдань планування, маршрутизації даних та інших. Сonsider several approaches to solving the problem of constructing a Hamiltonian cycle in a planar graph, which often arises in computer modeling of the various tasks of planning, routing data, and others.
first_indexed	2025-12-01T10:27:22Z
format	Article
fulltext	150 Теорія оптимальних рішень. 2011, № 10 ÒÅÎÐIß ÎÏÒÈÌÀËÜÍÈÕ ÐIØÅÍÜ Рассматривается несколько под- ходов к решению проблемы по- строения гамильтонова цикла в плоском графе, которая часто возникает при компьютерном моделировании различных задач производственного планирования, маршрутизации данных и других. _____________________________  В.Б. Павленко, 2011 ÓÄÊ 519.1 Â.Á. ÏÀÂËÅÍÊÎ ÒÅÎÐÅÒÈ×ÅÑÊÈÅ ÀÑÏÅÊÒÛ ÏÎÑÒÐÎÅÍÈß ÃÀÌÈËÜÒÎÍÎÂÀ ÖÈÊËÀ Введение. При рассмотрении задач планиро- вания производства, экономии природных ресурсов, задачи коммивояжера, задачи о хо- де коня и многих других задач, а также ме- тодов их решения (включая эвристические и генетические алгоритмы) приходится столк- нуться с проблемой нахождения пути, кото- рый проходил бы через все точки только один раз, т. е. «гамильтонова пути». При компьютерном моделировании этих задач необходимо убедится, что граф действитель- но имеет гамильтонов цикл. Эта задача часто бывает сложной и имеет несколько путей возможного решения. Свое название гамильтонов цикл получил от задачи «Кругосветное путешествие» пред- ложенной ирландским математиком Вилья- мом Гамильтоном в 1859 году. Нужно было, выйдя из исходной вершины графа, обойти все его вершины и вернуться в исходную точку. Граф представлял собой укладку до- декаэдра, узловые вершины которого симво- лизировали крупнейшие города Земли, а рёбра – соединяющие их дороги. Позднее задача трансформировалась – не- обходимо найти простой цикл, содержащий все вершины графа. Такой цикл называют гамильтоновым циклом, а содержащий его граф – гамильтоновым графом. Граф, кото- рый содержит простой путь, проходящий че- рез каждую его вершину, называется полу- гамильтоновым. Ясно, что всякий гамильто- нов граф является полугамильтоновым [1]. Заметим, что гамильтонов цикл существует далеко не в каждом графе. ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ПОСТРОЕНИЯ ГАМИЛЬТОНОВА ЦИКЛА Теорія оптимальних рішень. 2011, № 10 151 Задача проверки существования гамильтонова цикла является NP-полной (т. е., к которой можно свести любую другую задачу из класса NP за полиномиаль- ное время). Это делает NP-полные задачи в некотором смысле «самыми слож- ными» задачами в классе NP, и если для какой-то из них будет найден «быст- рый» алгоритм решения, то и любая другая задача из класса NP может быть ре- шена так же «быстро». Критерии существования гамильтонова цикла. Проблема поиска гамиль- тонова цикла является одной из наиболее известных NP-полных проблем теории графов. Очевидно, что если генерировать все n! различных последовательностей вершин и для каждой из них проверить, определяет ли она гамильтонов путь, то это потребует n!n шагов. Этот процесс может затратить огромное количество времени. Для решения этой проблемы существуют несколько подходов. Условие Дирака, предложенное в 1952 г. Полем Дираком. Если в простом графе G с (n≥3) вершинами ( ) 2 n p υ ≥ для любой вершины υ , то граф G является гамильтоновым [2]. Условие Оре, которое было предложено в 1960 г. норвежским математиком Ойстином Оре. Пусть p – количество вершин в данном графе. Если для любой пары несмеж- ных вершин x, y выполняется неравенство ( ) ( )d x d y p+ ≥ , т. е. степени любых двух несмежных вершин не меньше общего числа вершин в графе, то такой граф называется графом Оре. Граф Оре - гамильтонов. Теорема Бонди – Хватала. Граф является гамильтоновым тогда и только то- гда, когда его замыкание – гамильтонов граф. Эта теорема обобщает утверждения Дирака и Оре. Для графа G с n вершина- ми замыкание определяется добавлением в G ребра (u,v) для каждой пары не- смежных вершин u и v, сумма степеней которых не меньше n. Условие Поша. Пусть для графа [ , ]G A B= построена функция целого не- отрицательного аргумента х (то есть, функция в каждом целом неотрицательном х принимает значение, равное количеству вершин графа G, степень которых не превышает x) вида ( ) \|{ \| ( ) } \|f x a A d a x= ∈ ≤ . Такую функцию называют функ- цией Поша. Пусть p – количество вершин в данном графе [ , ]G A B= , ( )f x – его функ- ция Поша, а х – целое число. Графом Поша называется граф [ , ]G A B= , удовлетворяющий следующим условиям: 1) для 1 1 2 p x − ≤ ≤ выполняется неравенство ( )f x x< ; В. Б. ПАВЛЕНКО 152 Теорія оптимальних рішень. 2011, № 10 2) если 1 2 p − – целое число, то при 1 2 p x − = имеет место неравенство 1 ( ) 2 p f x − ≤ . Нетрудно заметить, что всякий граф Дирака является графом Поша. То же верно и в отношении графов Оре: каждый граф Оре является графом Поша. Об- ратное в обоих случаях неверно. Следуя вышеизложенному, можно утверждать, что задача построения га- мильтонова цикла сводится к построению цепи, которая будет удовлетворять одному из критериев существования гамильтонова цикла. Гамильтонов цикл легко искать, если граф имеет вид замкнутых контуров, соединенных более чем через две точки друг с другом. Однако не всегда можно определить внешний вид графа (скажем из-за количества вершин). Поэтому необходимо искать раз- личные методы, позволяющие построить гамильтонов цикл, не опираясь на раз- мер графа. Различные методы построения гамильтонова цикла. Известно, что почти все графы гамильтоновы, т. е. 1 )( )( lim = ∞→ pG pH p , где H(p) – множество гамильтоно- вых графов с p вершинами, а G(p) – множество всех графов с p вершинами. Та- ким образом, задача отыскания гамильтонова цикла или эквивалентная задача коммивояжера являются практически востребованными, но для нее неизвестен (и, скорее всего не существует) эффективный алгоритм решения [3]. Также на сегодня не существует никакого простого критерия или алгебраи- ческого метода, позволяющего ответить на вопрос, существует или нет в произ- вольном графе G гамильтонов цикл. Критерии существования, данные выше, представляют теоретический интерес, но являются слишком общими и не при- годны для произвольных графов, встречающихся на практике. Гамильтонов цикл представляет собой, с комбинаторной точки зрения, по- следовательность вершин графа или ее перестановку. При этом в качестве на- чальной вершины цикла можно выбрать любую вершину, так что можно рас- сматривать перестановки с фиксированным первым элементом. Самый бесхит- ростный план поиска гамильтонова цикла состоит в последовательном рассмот- рении всех этих перестановок и проверке для каждой из них, представляет ли она цикл в данном графе. Такой способ действий уже при не очень большом числе вершин становится практически неосуществимым ввиду быстрого роста числа перестановок (имеем (n-1)! перестановок из n элементов с фиксирован- ным первым элементом). Более рациональный подход состоит в рассмотрении всевозможных простых путей, начинающихся в произвольно выбранной стартовой вершине a, до тех пор, пока не будет обнаружен гамильтонов цикл или все возможные пути не бу- дут исследованы. По сути, речь также идет о переборе перестановок, но значи- ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ПОСТРОЕНИЯ ГАМИЛЬТОНОВА ЦИКЛА Теорія оптимальних рішень. 2011, № 10 153 тельно сокращенном (например, если вершина b не смежна с вершиной a, то все (n-2)! перестановок, у которых на первом месте стоит a, а на втором b, не рас- сматриваются). Графический метод работает лишь в простых случаях, а алгебраические ме- тоды определения гамильтоновых циклов не могут быть применены с более чем несколькими десятками вершин, так как они требуют слишком большого време- ни работы и большой памяти компьютера. В 1980 г. Асано Т., Кайкучи С., и Сэйто Н. предложили свой эффективный алгоритм для поиска гамильтонова цикла в произвольном 4-связном максималь- ном планарном графе. Для построения гамильтоновых циклов здесь использова- лась упрощенная версия доказательства теоремы Уитни: каждый 4-связный мак- симальный планарный граф имеет гамильтонов цикл. Несмотря на поддержку финансированием и помощь министерства образования, науки и культуры Япо- нии, к сожалению, подробные исследования этого метода не проводились [4]. На данный момент наиболее приемлемым является способ Робертса и Фло- реса, который не предъявляет чрезмерных требований к памяти компьютера, но время его выполнения зависит экспоненциально от числа вершин в графе. Одна- ко другой неявный метод перебора имеет для большинства типов графов очень небольшой показатель роста времени вычислений в зависимости от числа вер- шин. Он может быть использован для нахождения гамильтоновых циклов в очень больших графах. В противоположность алгебраическим методам, с помощью которых пыта- ются найти сразу все гамильтоновы циклы и при реализации которых приходит- ся хранить все цепи, которые могут оказаться частями таких циклов, метод пе- ребора имеет дело с одной цепью, непрерывно продлеваемой до того момента, когда либо отыскивается гамильтонов цикл, либо становится ясно, что эта цепь не может привести к гамильтонову циклу. Тогда цепь модифицируется некото- рым систематическим способом (который гарантирует, что, в конце концов, бу- дут исчерпаны все возможности), после чего продолжается поиск гамильтонова цикла. Этот метод не предъявляет чрезмерных требований к памяти компьюте- ра, для поиска требуется очень небольшой объем памяти и за один запуск алго- ритма находится один гамильтонов цикл. Этот метод может быть использован для нахождения гамильтоновых циклов в очень больших графах. Также для этого метода есть небольшое улучшение, которое позволяет не- много сократить расчеты, однако после внимательного изучения операций алго- ритма становится очевидным, что по сути улучшенный вариант алгоритма Ро- бертса и Флореса не намного лучше первоначального варианта этого алгоритма. Необходимое время вычисления в нем все еще зависит (более или менее) экспо- ненциально от n. Вычисления при использовании этих двух алгоритмов для не- ориентированных графов со степенями вершин 3 - 5 на практике показывают, что «улучшенный» вариант в действительности хуже для графов малых разме- ров, хотя для больших графов (с более чем 20 вершинами) он позволяет сэконо- В. Б. ПАВЛЕНКО 154 Теорія оптимальних рішень. 2011, № 10 мить более 50 % времени вычисления. Все дело в том, что даже после сделанно- го улучшения не слишком много внимания уделяется оставшейся части графа, в которой берется последовательность вершин, продолжающих построенную цепь. В этом случае используют мультицепной алгоритм, который в качестве своей основы использует метод Роберта и Флореса и отличается от него наличи- ем операции возвращения (когда начальная вершина поиска удаляется и заменя- ется другой вершиной) [5]. На практике мультицепной алгоритм показывает высокие показатели эффек- тивности. Время его работы растет очень медленно в зависимости от числа вер- шин и поэтому алгоритм применим для очень больших графов. Другим преимуществом этого метода является очень слабая вариация време- ни для различных графов одинакового размера, и поэтому можно оценить с ра- зумной степенью доверительности время вычисления, необходимое для различ- ных задач. Кроме того, эксперименты показывают, что для графов, степени вершин ко- торых лежат в вышеприведенных пределах 3 – 5, метод по существу не чувстви- телен к степеням вершин. Небезынтересно сказать несколько слов о вычислениях с тремя алгоритмами, когда искались все гамильтоновы циклы. На практике редко применяют все три алгоритма сразу. Это не повышает точность оценки, а сложность расчетов и громоздкость программы увеличивается. Более того, ошибка в вычислениях также растет – как правило, это 5 – 10 %. Этот недостаток компенсируется для комбинаторных задач относительно высокой скоростью работы. Заключение. Применение алгоритмов построения гамильтоновых цепей имеет важное практическое значение и используется при изучении различных задач планирования, транспортных и коммуникационных систем, в частности, для маршрутизации данных в Интернете, при компьютерном моделировании различных практических задач, проблем экономики и разработке систем с во- зобновляемыми источниками энергии. К сожалению, на сегодня не существует универсального метода построения гамильтонова цикла, а существующие методы способны решать лишь отдель- ные поставленные цели. Так, имея множество преимуществ, метод Робертса и Флореса уступает более быстрому мультицепному методу, который во много раз сложнее в реализации. ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ПОСТРОЕНИЯ ГАМИЛЬТОНОВА ЦИКЛА Теорія оптимальних рішень. 2011, № 10 155 В. Б. Павленко ТЕОРЕТИЧНІ АСПЕКТИ ПОБУДОВИ ГАМІЛЬТОНОВА ЦИКЛА Розглядається декілька підходів до вирішення проблеми побудови гамільтонова цикла в пло- скому графі, яка часто виникає при комп'ютерному моделюванні різних завдань планування, маршрутизації даних та інших. V. B. Pavlenko METHOD THEORETICAL ASPECTS OF CONSTRUCTING A HAMILTONIAN CYCLE Сonsider several approaches to solving the problem of constructing a Hamiltonian cycle in a planar graph, which often arises in computer modeling of the various tasks of planning, routing data, and others. 1. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, опитимизация. – М.: Наука, 1981. – 341 с. 2. Дойбер В. А., Косточка А. В., Закс Х.. Более короткое доказательство теоремы Дирака о числе ребер в хроматически критических графах // Дискретный анализ и исследова- ние операций. Новосибирский гос. ун-т, 1996. – С. 28–34. 3. Харари Ф. Теория графов. – М.: Мир, 1973. – 300 с. 4. A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs [Електронний ресурс] / T. Asano, S. Kikuchi, N. Saito. // Discrete Applied Mathematics. – 2002. – № 7. – С. 15. – Режим доступу до журнала: http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYW-45FKTSV- 45&_user=10&_origUdi=B6WH3-4D7JN6P- 57&_fmt=high&_coverDate=01%2F31%2F1984&_rdoc=1&_orig=article&_origin=article &_zone=related_art&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5= 1742246037e33694e1e29159fc9f520f 5. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 с. Получено 07.04.2011
id	nasplib_isofts_kiev_ua-123456789-46787
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	XXXX-0013
language	Russian
last_indexed	2025-12-01T10:27:22Z
publishDate	2011
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Павленко, В.Б. 2013-07-06T17:35:13Z 2013-07-06T17:35:13Z 2011 Теоретические аспекты построения гамильтоновa цикла / В.Б. Павленко // Теорія оптимальних рішень: Зб. наук. пр. — 2011. — № 10. — С. 150-155. — Бібліогр.: 5 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/46787 519.1 Рассматривается несколько подходов к решению проблемы построения гамильтонова цикла в плоском графе, которая часто возникает при компьютерном моделировании различных задач производственного планирования, маршрутизации данных и других. Розглядається декілька підходів до вирішення проблеми побудови гамільтонова цикла в плоскому графі, яка часто виникає при комп'ютерному моделюванні різних завдань планування, маршрутизації даних та інших. Сonsider several approaches to solving the problem of constructing a Hamiltonian cycle in a planar graph, which often arises in computer modeling of the various tasks of planning, routing data, and others. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Теоретические аспекты построения гамильтоновa цикла Теоретичні аспекти побудови гамільтонова цикла Method theoretical aspects of constructing a hamiltonian cycle Article published earlier
spellingShingle	Теоретические аспекты построения гамильтоновa цикла Павленко, В.Б.
title	Теоретические аспекты построения гамильтоновa цикла
title_alt	Теоретичні аспекти побудови гамільтонова цикла Method theoretical aspects of constructing a hamiltonian cycle
title_full	Теоретические аспекты построения гамильтоновa цикла
title_fullStr	Теоретические аспекты построения гамильтоновa цикла
title_full_unstemmed	Теоретические аспекты построения гамильтоновa цикла
title_short	Теоретические аспекты построения гамильтоновa цикла
title_sort	теоретические аспекты построения гамильтоновa цикла
url	https://nasplib.isofts.kiev.ua/handle/123456789/46787
work_keys_str_mv	AT pavlenkovb teoretičeskieaspektypostroeniâgamilʹtonovacikla AT pavlenkovb teoretičníaspektipobudovigamílʹtonovacikla AT pavlenkovb methodtheoreticalaspectsofconstructingahamiltoniancycle

Теоретические аспекты построения гамильтоновa цикла

Institution

Similar Items