Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Определение






Если граф имеет простой цикл, содержащий все вершины графа, то цикл называется Гамильтоновым, а граф – Гамильтоновым графом.

Ясно, что Гамильтоновым, может быть только связный граф.

Необходимые и достаточные условия Гамильтонова графа неизвестны. Известны только некоторые достаточные условия.

 

Теорема Хватала (В.Хватал, 1972 г.)

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

 

Теорема Оре (О.Оре, 1960г.)

Если для любой пары и несмежных вершин графа порядка выполняется неравенство , то - гамильтонов граф.

 

Теорема Дирака (следствие теоремы Оре) (Г. Дирак, 1952 г.)

Если для любой вершины графа порядка выполняется неравенство , то - гамильтонов граф.

 

Для нахождения Гамильтонова цикла не существует эффективного алгоритма его нахождения.

Если в графе G=(V, E) порядка n фиксировать одну вершину и обход всегда начинать с нее, то всякому Гамильтонову циклу очевидным образом будет соответствовать перестановка элементов множества V. Тем самым, чтобы найти Гамильтонов цикл или убедиться в его отсутствии, нужно произвести (n-1)! перестановок. Если граф G – Гамильтонов, то проделать этот перебор в полном объеме придется только в случае крайнего невезения – когда нужная, то есть соответствующая Гамильтонову циклу перестановка окажется последней в этом процессе. Если же G – не Гамильтонов граф, то чтобы убедится в отсутствии Гамильтонова цикла, придется перебрать все

(n-1)! Перестановоки, то есть задача относится к классу NP.

 

Как мы уже показали – в природе почти нет эйлеровых графов и эффективный алгоритм отыскания эйлеровых циклов редко оказывается применимым на практике. С другой стороны можно показать, что почти все графы – гамильтоновы, то есть

, где

S(р) – множество всех графов с р вершинами, а Н(р) – множество гамильтоновых графов с р вершинами

 

Пример

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

 

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


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал