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

Тема 15.2. Обход графа

Тема 11.5. Методы упрощения логических выражений. Методы решения логических задач | Тема 12.1. Определение предиката | Тема 12.2. Логические операции над предикатами | Тема 12.3. Кванторы | Тема 12.4. Истинные формулы и эквивалентные соотношения | Тема 12.5. Доказательства в логике предикатов | Тема 13.1. Основные определения теории графов | Тема 13.3. Отношения порядка и эквивалентности на графе | Тема 14.1. Граф достижимости | Тема 14.2. Взаимная достижимость, компоненты сильной связности и базы графа |


Читайте также:
  1. Аналогично предыдущему случаю для перевода числа в показательную форму необходимо найти модуль и аргумент. Модуль полученного комплексного числа равен
  2. Больному были приготовлены по рецепту врача глазные капли с этилморфина гидрохлоридом. В каком документе необходимо учесть израсходованный этилморфина гидрохлорид?
  3. В конце рабочего дня кассир должен учесть приходные и расходные операции за день. Какой документ при этом ему необходимо оформить?
  4. В обход границ материальной реальности
  5. В чем для наших соотечественников насущная необходимость предмета «Основы православной культуры»?
  6. В чем состоит христианское совершенство?. Для стяжания его необходима брань.. Четыре вещи, крайне потребные для успеха в сей брани
  7. Веские социальные и экономические аргументы в пользу необходимости улучшать здоровье людей.

Определение: Маршрут, содержащий все рёбра или все вершины графа, и обладающий определёнными свойствами называется обходом графа.

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

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

Существует критерий существования эйлерова цикла в графе.

Теорема Эйлера: Связный граф имеет эйлеров цикл, тогда и только тогда когда каждая его вершина имеет чётную степень.

Задача, которая привела к появлению понятия Эйлерова цикла, широко известна в истории математики. Это так называемая задача о кёнигсбергских мостах. Расположение семи мостов в городе Кёнигсберге в начале XVIII века приведено на рисунке. Требуется обойти город, пройдя через каждый мост ровно один раз, и вернуться в исходную точку.

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

Именно решение данной задачи привело Л. Эйлера к доказательству приведённой выше теоремы. Кстати, согласно ей, данная задача неразрешима, поскольку степени всех вершин графа нечётны.

Теорема. Для того, чтобы связный граф обладал Эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно две вершины нечётной степени.

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

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

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

Определение: Граф называется гамильтоново связным, если любые две его вершины соединены гамильтоновой цепью.

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


Дата добавления: 2015-10-28; просмотров: 44 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Тема 15.1. Деревья| Тема 15.3. Расстояния. Диаметр, радиус и центр графа. Протяжённости.

mybiblioteka.su - 2015-2024 год. (0.007 сек.)