Основы дискретной математики

Рисунок 3.15 – Эйлеров цикл

Задача Эйлера о Кенигсбергских мостах [19]: необходимо выйти из любой точки города и вернуться в нее, при этом пройдя по каждому мосту только один раз. Эйлер свел эту задачу к графу: существует ли в конечном графе такой цикл, в котором каждое ребро участвует только один раз? Цикл, в котором к

аждое ребро графа G участвует всего один раз, называется эйлеровым циклом. Граф, содержащий эйлеров цикл, называется эйлеровым.

Дальнейшее развитие задачи об Эйлеровом цикле

Припишем ребрам графа длину μ (ai, aj). Требуется найти путь в графе, который проходит через все ребра и имеет наименьшую длину.

Пример.

Рисунок 3.16 – Граф

S – стартовая вершина. Из вершины S надо пройти по всем ребрам так, чтобы маршрут имел минимальную длину. Очевидно, что длина маршрута будет минимальной, если каждое ребро будет пройдено всего один раз – т. е. маршрут будет эйлеровым циклом.

Все локальные степени – четные, значит граф эйлеров.

Варианты прохождения по циклу:

1) (sa) (ab) (bc) (cd) (db) (ds)

2) (sa) (ab) (bd) (dc) (cb) (bs)

3) (sb) (bc) (cd) (db) (ba) (as)

4) (sb) (bd) (dc) (cb) (ba) (as)

Длина эйлерова цикла – 22. Любой из вариантов 1–4 содержит каждое ребро графа, следовательно, длина одинакова для всех циклов 1–4. Длина эйлерова цикла не зависит от того, какая вершина будет выбрана за исходную.

Задача поиска эйлерова цикла – это задача о: – поиске наилучшего способа прохождения бригады по дорогам; – прохождении с/х техники по полям.

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

Алгоритм нахождения эйлерова цикла для неориентированного графа [19]:

Дан эйлеров граф – т. е. граф с четными локальными степенями.

Найдем первое ребро х, инцидентное вершине S. Затем найдем ребро, смежное с ребром х, которое не образует цикл и еще не было использовано. Продолжим этот процесс до тех пор, пока не вернемся в вершину S. Если в построенный цикл С1 вошли все ребра графа – задача решена.

Если в построенный цикл С1 вошли не все ребра – строим цикл С2, состоящий из неиспользованных ребер и начинающийся с произвольного неиспользованного ребра.

Таким образом, строим циклы С2, С3,….Образование циклов продолжается до тех пор, пока не будут использованы все ребра.

Все циклы Сi необходимо объединить в один цикл. Условие объединения циклов С1 и С2 – наличие у них общей вершины х. Начинаем движение с любой вершины и двигаемся по циклу С1 до тех пор, пока не дойдем до х. Затем проходим ребро. С» и возвращаемся в х. Продолжаем обход по оставшимся ребрам до возвращения к исходной точке. Эта процедура легко обобщается на случай любого числа объединяемых циклов.

Циклы Эйлера для ориентированного графа

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

Строятся циклы Сi с учетом ориентации ребер, и затем все циклы объединяются в один.

Гамильтонов цикл (задача о коммивояжере)

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

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

Гамильтонов цикл наименьшей длины называется оптимальным гамильтоновым циклом (ОГЦ)

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

Решением задачи о коммивояжере не всегда является ОГЦ.

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

Рисунок 3.17 – Ребра, входящие в гамильтонов цикл С

К сожалению, алгоритм решения данной задачи, дающий оптимальное решение, пока не известен. Для сложных сетей число гамильтоновых циклов, которые необходимо просмотреть для выделения минимального, непомерно огромно. Однако существуют алгоритмы поиска субоптимального решения [1]. Субоптимальное решение необязательно даст цикл минимального общего веса, но найденный цикл будет, как правило, значительно меньшего веса, чем большинство произвольных гамильтоновых циклов! Один из таких алгоритмов – алгоритм ближайшего соседа.

Этот алгоритм выдает субоптимальное решение задачи коммивояжера, генерируя гамильтоновы циклы в нагруженном графе с множеством вершин V. Цикл, полученный в результате работы алгоритма, будет совпадать с конечным значением переменной маршрут, а его общая длина – конечное значение переменной w.

begin

Выбрать v € V;

маршрут:=v;

w:=0;

v':=v;

Отметить v';

while остаются неотмеченные вершины do begin

Выбрать неотмеченную вершину и,

ближайшую к v';

маршрут:= маршрут u;

w:= w + вес ребра v'u;

v':=u;

Отметить v';

end

маршрут:= маршрут v;

w:= w + вес ребра v'v;

end

Пример. Примените алгоритм ближайшего соседа к графу, изображенному на рисунке 3.18. За исходную вершину возьмите вершину D.

Рисунок 3.18 – Граф

Таблица 3.2 – Алгоритм ближайшего соседа

 Скачать реферат