Тема 7.5 Эйлеровы и гамильтоновы графы.
Классической в теории графов является следующая задача. В городе Кенигсберге имеется два острова, соединенных семью мостами с берегами реки Преголь и друг с другом так, как показано на рисунке.
Задача состоит в следующем: осуществить прогулку по городу таким образом, чтобы, пройдя по одному разу по каждому мосту, вернуться обратно. Решение этой задачи сводится к нахождению некоторого специального маршрута в графе.
Пусть G – псевдограф.
Цепь (цикл) в G называется эйлеровой (эйлеровым), если она (он) проходит по одному разу через каждое ребро псевдографа G.
Поставим в соответствие схеме мультиграф G, изображенный на рисунке,
в котором каждой части суши соответствует вершина, а каждому мосту – ребро, соединяющее соответствующие вершины. На языке теории графов задача звучит следующим образом: найти эйлеров цикл в мультиграфе G.
Граф является эйлеровым, если он содержит эйлеров цикл.
Теорема. Связный граф является эйлеровым тогда и только тогда, когда каждая вершина имеет четную локальную степень.
Теорема. Связный граф содержит эйлерову цепь тогда и только тогда, когда ровно две вершины имеют нечетную локальную степень.
Рассмотрим алгоритм построения эйлеровой цепи в данном эйлеровом графе. Этот метод известен под названием алгоритма Флёри.
Теорема. Пусть G – эйлеров граф; тогда следующая процедура всегда возможна и приводит к эйлеровой цепи графа G. Выходя из произвольной вершины и, идем по ребрам графа произвольным образом, соблюдая лишь следующие правила:
· стираем ребра по мере их прохождения и стираем также изолированные вершины, которые при этом образуются;
· на каждом этапе идем по мосту только тогда, когда нет других возможностей.
Любой простой полный граф с нечетным количеством вершин является эйлеровым. Любой циклический граф является эйлеровым. Граф, являющийся колесом, не является эйлеровым.
Критерий эйлеровости: Для того, чтобы граф являлся эйлеровым необходимо и достаточно, чтобы он был связным и все его вершины имели четную степень.
Цепь (цикл) в G называется гамильтоновой (гамильтоновыми), если она (он) проходит по одному разу через каждую вершину псевдографа G.
Граф является гамильтоновым, если он содержит гамильтонов цикл.
С понятием гамильтоновых циклов тесно связана так называемая задача коммивояжера: в нагруженном графе G определить гамильтонов цикл минимальной длины (иными словами, коммерсант должен совершить поездку по городам и вернуться обратно, побывав в каждом городе ровно один раз, и при этом стоимость такой поездки должна быть минимальной).
Приведем теорему Дирака, которая отвечает на вопрос: существует ли в графе гамильтонов цикл.
Теорема. Если в простом графе с n (³ 3) вершинами локальная степень каждой вершины не менее n/2, то граф является гамильтоновым.
Любой простой полный граф является гамильтоновым. Любой циклический граф является гамильтоновым. Граф, являющийся колесом, является гамильтоновым.
Критерии гамильтоновости:
1. любой полный граф является гамильтоновым
2. если в графе, кроме простого цикла, проходящего через все его вершины, содержатся и другие ребра, то граф является гамильтоновым.
3. если для любых двух вершин А и В графа с m вершинами выполняется: степень А + степень В ≤ m, то граф является гамильтоновым.
4. если граф с m вершинами и любая степень больше либо равна m/2, то граф является гамильтоновым.
Дата добавления: 2016-07-22; просмотров: 1853;