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

Алгоритм Флери (алгоритм построения эйлерова цикла).

Идем по ребрам графа, соблюдая правила:

1) Удаляем пройденные ребра и изолированные вершины, которые при этом образуются.

2) Идем по мосту только тогда, когда нет других возможностей.

По теореме граф является эйлеровым.

На диаграмме ребра пронумерованы в порядке их прохождения, таким образом эйлеров цикл

52. Гамильтоновы графы. Теорема Дирака.

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

Теорема (Дирак). Если в графе G(V,E) с p вершинами , то граф G является гамильтовым.

Обратное неверно.

Пример. p = 8, , граф является гамильтовым.

Не существует алгоритмов получения гамильтонова цикла, эффективных в вычислительном смысле, то есть требующих полиномиального времени.

Теорема Дирака. Если в графе число вершин и степень каждой вершины , то в графе существует гамильтонов цикл. Условие не является необходимым. Доказательство: Докажем от противного. Пусть есть граф G, , гамильтонова цикла пусть нет. Если гамильтонова цикла нет, то его можно сделать гамильтоновым, добавив вершины и ребра. Обозначение u-добавленная вершина. Пусть граф имеет вид ,

-смежная с Тогда не смежная , иначе можно было бы построить , т.е.вершину не нужно было бы добавлять. Рассуждая дальше, получаем, что число вершин, смежных с , не меньше числа вершин, не смежных с . -число вершин, не смежных с ,

-число вершин, смежных с (степень), , но дано ,

Получаем противоречия , то есть для получения гамильтонова цикла новую вершину не нужно добавлять. Так проверить все добавленные вершины.

53. Гамильтоновы графы. Задача коммивояжера и методы ее решения.

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

Задача коммивояжера. Рассмотрим следующую задачу. Имеется p городов, расстояния между которыми известны. Коммивояжер должен посетить все p городов по одному разу, вернувшись в тот, с которого начал. Требуется найти такой маршрут движения, при котором суммарное пройденное расстояние будет минимальным. Очевидно, что задача сводится к отысканию кратчайшего гамильтонова цикла в полном графе. Рассмотрим методы решения этой задачи.

1. Алгоритм полного перебора. Считая, что коммивояжер всегда выезжает из одного и того же города, сгенерировать p-1! Перестановок остальных вершин и для каждой перестановки вычислить длину пути, выбрав затем из них минимальную. Большая трудоёмкость.

2. Методы сокращения перебора

1)Метод ветвей и границ

3. Приближённые методы.

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

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

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