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

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

Прочитайте:
  1. c) Алгоритм люмбальной пункции
  2. АЛГОРИТМ
  3. АЛГОРИТМ
  4. Алгоритм аспирации содержимого трахеобронхиального дерева через интубационную и трахеостомическую трубку у больных, находящихся на ИВЛ
  5. Алгоритм виконання маніпуляції
  6. Алгоритм виконання маніпуляції
  7. Алгоритм виконання маніпуляції
  8. Алгоритм виконання маніпуляції
  9. Алгоритм виконання маніпуляції
  10. Алгоритм виконання маніпуляції

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

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 | Просмотры: 2480 | Нарушение авторских прав







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