АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

ОПРЕДЕЛЕНИЕ. Цикл в некотором графе называется циклом Гамильтона, если он содержит все вершины этого графа по одному разу.

Прочитайте:
  1. I. Доход от прироста стоимости при реализации ценных бумаг (инвестор самостоятельно несет ответственность за определение и выплату налогов в бюджет Республики Казахстан)
  2. I. ОПРЕДЕЛЕНИЕ ОСНОВНЫХ ТЕРМИНОВ
  3. I. Определение СКФ по клиренсу креатинина
  4. II. Договорные отношения могущие влиять на определение управомоченного лица
  5. А. Определение группы крови стандартными изогемагглютинирующими сыворотками.
  6. Аборты. Определение, классифиация, диагностика и профилактика.
  7. Ангины: 1) определение, этиология и патогенез 2) классификация 3) патологическая анатомия и дифференциальная диагностика различных форм 4) местные осложнения 5) общие осложнения
  8. Антигены. Определение. Свойства. Виды.
  9. Асептика, антисептика. Определение понятий. Способы проведения.
  10. Б. Определение группы крови с помощью цоликлонов (моноклональных антител)

Цикл в некотором графе называется циклом Гамильтона, если он содержит все вершины этого графа по одному разу.

 

То есть любые две вершины цикла Гамильтона, одна из которых является внутренней вершиной цикла, - разные.

 

Исторически понятие такого цикла относится к головоломке, предложенной в 1859 году Уильямом Гамильтоном. Она называлась задачей о кругосветном путешествии.

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

В общем случае граф может не иметь циклов Гамильтона. Например, граф G 1, изображенный на рис. 5.20 не имеет таких циклов, так как вершина v при всяком прохождении по всем вершинам этого графа должна проходиться не менее двух раз. Граф G 2 имеет цикл Гамильтона. Такой цикл представлен ребрами, изображенными более толстыми линиями.

       
   
 
 

 


v

G 1 G 2

Рис. 5.20

Вершина v графа G называется разделяющей, если удаление из G вершины v вместе с соответствующими ей ребрами разбивает граф на несколько компонент связности.

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

 

Практически важная задача, приводящая к поиску циклов, близких по свойствам к циклам Гамильтона, носит название задачи коммивояжёра.

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

Разновидностью приведенной задачи является задача нахождения цикла Гамильтона.

Для нахождения циклов Гамильтона в произвольных графах можно воспользоваться процедурой перебора вариантов. Для произвольно заданного графа G, имеющего n вершин, достаточно организовать последовательную проверку всех перестановок вершин этого графа. Каждая такая перестановка дополняется вершиной, равной её первому элементу, после чего проверяется свойство полученной последовательности вершин быть циклом Гамильтона в G.

Практическая применимость такого переборного метода сомнительна, поскольку число перестановок вершин, равное n!, уже для небольших по размерам графов является слишком большим.

 

Замечание. Для циклов Гамильтона, в отличие от циклов Эйлера, неизвестны непереборные алгоритмы нахождения таких циклов в произвольных графах. Более того, существующая теория решения комбинаторных задач относит задачу отыскания таких циклов в графах к классу наиболее длительных по времени решения задач.

Поэтому рассмотрение задачи нахождения циклов Гамильтона в графах естественно ограничить рассмотрением отдельных классов графов, для которых могут быть получены простые по сложности проверки условия существования таких циклов.

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

Пусть G = (V, U) - некоторый граф без петель и V = { a 1,..., an }. Будем считать, что n 3.

 


Дата добавления: 2015-09-27 | Просмотры: 435 | Нарушение авторских прав







При использовании материала ссылка на сайт medlec.org обязательна! (0.003 сек.)