Практикум по дискретной математике в среде виртуальной лаборатории системы ДО ИТМО (стр. 2 )

Для изучения и получения зачета по каждой теме практических занятий занятий студент должен выполнить следующие действия:

1.  Зайти на сервер центра дистанционного обучения ГУИТМО (de. *****), и в левой части окна страницы в меню выбрать пункт «Обучение и аттестация».

2.  В открывшемся списке предметов выберите учебный план «Дискретная математика».

3.  В появившемся окне выберите ссылку теоретического курса и выберите из предложенного списка изучаемую тему.

4.  Ознакомтесь с предлагаемым теоретическим материалом и рассмотрите пример решения типовой задачи с применением изучаемого метода.

5.  Вернитесь назад и выберите страницу практикума. Получите у преподавателя номер своего варианта и перейдите на страницу выбора практического задания.

6.  С помощью выпадающего списка в верхней части страницы выберите вариант задачи согласно номеру, полученному Вами у преподавателя.

7.  Решите полученный вариант используя изучаемый метод.

8.  Запустите систему проверки результатов и укажите в ней:

·  Свою фамилию, номер группы;

·  Название изучаемой темы;

·  Номер решенного варианта;

·  Полученный в результате вычислений результат.

9.  При отрицательном ответе системы повторно ознакомтесь с теорией по изучаемому методу и проверьте свое решение. Повторите ввод результата в систему проверки. Обратите внимание, на то, как и какие данные Вы вводите!

10.  При возникновении вопросов, оформите отчет о проделанной работе и обратитесь к преподавателю за консультацией.

11.  Информация в электронный журнал по дисциплине «Дискретная математика» добавляется только в случае положительного(!) результата проверки решения.

2.  МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ТЕМАМ ПРАКТИЧЕСКИХ ЗАНЯТИЙ

2.1.  Тема №1 «Связность в графе». Волновой метод поиска минимального маршрута в связном графе.

Орграф – граф, состоящий из вершин и дуг (направленных ребер).

Маршрут. Для графа G(V, X) (для орграфа - путь) последовательность (где ), в которой чередуются вершины и ребра (дуги) и для каждого j=1, …, k, ребро xj имеет вид , называется маршрутом, соединяющим вершины (путем из v1 в vk+1). При этом v1 называется начальной, vk+1­ – конечной вершинами маршрута (пути), а остальные вершины внутренними.

Длина маршрута – число ребер (дуг) в маршруте (пути).

Маршрут минимальной длины – маршрут с минимальным количеством ребер (дуг) между заданными начальной и конечной вершинами.

Взвешенный граф – граф, в котором ребрам (дугам) присвоены некоторые веса.

Минимальный маршрут – маршрут, соединяющий начальную и конечную вершину во взвешенном графе и имеющий минимальный суммарный вес ребер (дуг) маршрута.

Волновой метод

Пусть D=(V,X) – орграф с вершинами и v,w – заданные вершины из V, где. Опишем алгоритм поиска минимального пути из v в w в орграфе D (алгоритм фронта волны).

1.  Помечаем вершину v индексом 0. Затем помечаем вершины, принадлежащие образу вершины v, индексом 1. Множество вершин с индексом 1 обозначаем FW1(v).

2.  Если или выполняется , то вершина w недостижима из v, и работа алгоритма на этом заканчивается. В противном случае переходим к шагу 3.

3.  Если , то переходим к шагу 4. В противном случае существует путь из v в w длины k, и этот путь является минимальным. Последовательность вершин

, где

(*)

и есть искомый минимальный путь из v в w. На этом работа алгоритма заканчивается.

4.  Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин с индексом k. Множество вершин с индексом k обозначаем FWk+1(v).Присваиваем k=k+1 и переходим к шагу 2.

Замечание 1. Множество FWk(v) в алгоритме называют фронтом волны k-го уровня.

Замечание 2. Вершины w1,…,wk-1 из (*) могут быть выделены неоднозначно. Эта неоднозначность соответствует случаям, когда существует несколько различных минимальных путей из v в w.

Пример:

Используя алгоритм[10], определим минимальный путь из v1 в v6 в орграфе D, заданном матрицей смежности:

	V1	V2	V3	V4	V5	V6
V1	0	0	0	1	1	0
V2	1	0	0	1	1	1
V3	1	1	0	1	1	1
V4	0	1	1	0	1	0
V5	1	1	1	1	0	0
V6	1	1	1	1	1	0

Действуя согласно алгоритму определим :

Таким образом , а значит (см. шаг 3), существует путь из v1 в v6 длины 3, и этот путь является минимальным. Найдем теперь минимальный путь из v1 в v6. Определим множество:

.

Выберем любую вершину из найденного множества, например v3. Определим далее множество:

.

Выберем любую вершину из найденного множества, например v5. Тогда v1v5v3v6 – искомый минимальный путь из v1 в v6 (длины 3) в орграфе D.

2.2.  Тема № 2 «Циклы в графе». Циклы Гамильтона и задача коммивояжера.

Простой цикл, содержащий все вершины графа, называют циклом Гамильтона [9].

Рассмотрим две задачи, связанные с понятием цикла Гамильтона.

Задача 1. Дан ориентированный граф G, требуется найти в нем циклы Гамильтона, если они существуют.

Задача 2. Дан полный граф G, ребрам которого приписаны произвольные веса сij. Требуется найти такой цикл Гамильтона, который имеет наименьший суммарный вес ребер.

Замечание. Если граф G - неполный, то его можно рассматривать как полный, приписывая недостающим дугам (ребрам) бесконечный вес.

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

Метод Робертса и Флореса

Для исходного орграфа G строим матрицу М = [mij], где элемент mij есть i-я вершина (скажем, xg), для которой в графе G существует дуга (хj, хg). Вершины хg во множестве Г (хj) можно упорядочить произвольно, образовав элементы j-го столбца матрицы М. Заметим, что для проверки правильности построения матрицы следует помнить, что число строк матрицы М будет равно наибольшей полустепени исхода вершины.

Метод Робертса и Флореса основан на переборе возможных решений, позволяет найти все варианты циклов Гамильтона в орграфе, и состоит в следующем. Некоторая вершина, например, х1 выбирается в качестве начальной вершины множества S. Это множество S будет служить для хранения вершин строящейся цепи Гамильтона путем включения на каждом следующем шаге возможной вершины: под возможной вершиной мы будем понимать вершину, ранее не вошедшую в S. Итак, в S добавляется из столбца х1 очередная возможная вершина, например, «а». Затем к множеству S добавляется очередная возможная вершина из столбца «а», например, «b». Затем к S добавляется очередная возможная вершина из столбца «b», например, «с» и т. д.

Существуют две причины, препятствующие включению некоторой вершины на шаге r во множество S, где S = {х1 ,а, b,с,..., хr-1, хr}:

Случай 1. В столбце хr нет возможной вершины.

Случай 2. Множество S содержит (n-1) вершин. Это означает, что мы нашли цепь Гамильтона. Для того, чтобы достроить ее до цикла Гамильтона, надо рассмотреть дугу (хr, х1):

a)  если в графе существует дуга (хr, х1), то найден цикл Гамильтона;

b)  если дуга (хr, х1) отсутствует, то в данном графе не существует цикла Гамильтона на основе найденной цепи.

В случаях 1 и 2(б) следует возврат к варианту без вершины хr. После исключения данной вершины остается множество S ={ х1 ,а, b,с,..., хr-1 }. Теперь в S добавляется очередная возможная вершина, следующая за хr-1 в столбце хr матрицы М. Далее процедура поиска повторяется: осуществляется включение возможных вершин до тех пор, пока не будет найдена цепь Гамильтона или пока не потребуется очередной возврат.

Пример.

Пусть дан следующий орграф[14] на 6-ти вершинах:

Матрица М для данного графа выглядит следующим образом:

	a	b	c	d	e	f
1	b	c	a	c	c	a
2	-	e	d	f	d	b
3	-	-	-	-	-	с

Поиск циклов Гамильтона методом Робертса и Флореса состоит в последовательности следующих шагов:

№ шага	Действие	Множество S
1.	В качестве начальной вершины выбираем вершину «а».	а
2.	Добавляем очередную возможную вершину из столбца «а»: вершину «b».	а, b
3.	Добавляем очередную возможную вершину из столбца «b»: вершину «с».	a, b, c
4.	Рассмотрим столбец «с»: вершина «а» не является возможной (уже есть в S), добавляем вершину «d».	a, b, c, d
5.	Рассмотрим столбец «d»: вершина «с» не является возможной (уже есть в S), добавляем вершину «f».	a, b, c, d, f
6.	Столбец «f» не содержит возможных вершин. Исключаем вершину «f».	a, b, c, d
7.	Столбец «d» не содержит возможных вершин. Исключаем вершину «d».	a, b, c
8.	Столбец «c» не содержит возможных вершин. Исключаем вершину «c».	а, b
9.	Добавляем очередную возможную вершину из столбца «b»: вершину «e».	a, b, e
10.	Добавляем очередную возможную вершину из столбца «e»: вершину «c».	a, b, e, c
11.	Добавляем очередную возможную вершину из столбца «c»: вершину «d».	a, b, e, c, d
12.	Добавляем очередную возможную вершину из столбца «d»: вершину «f».	a, b, e, c, d, f
13.	Количество вершин в S равно 5, т. е. (n-1). Проверяем наличие дуги (f,a). Так как она существует, то найден первый вариант цикла Гамильтона (a, b, e, c, d, f , а). Удаляем вершину «f» и продолжим поиск других вариантов цикла Гамильтона.	a, b, e, c, d
14.	Столбец «d» не содержит отличных от «f» возможных вершин. Исключаем вершину «d».	a, b, e, c
15.	Столбец «с» не содержит отличных от «d» возможных вершин. Исключаем вершину «с».	a, b, e
16.	Добавляем очередную возможную отличную от «с» вершину из столбца «e»: вершину «d».	a, b, e, d
17.	Добавляем очередную возможную вершину из столбца «d»: вершину «f».	a, b, e, d, f
18.	Добавляем очередную возможную вершину из столбца «f»: вершину «с».	a, b, e, d, f, c
19.	Количество вершин в S равно 5, т. е. (n-1). Проверяем наличие дуги (f,с). Так как она существует, то найден второй вариант цикла Гамильтона (a, b, e, d, f, c). Удаляем вершину «с» и продолжим поиск других вариантов цикла Гамильтона.	a, b, e, d, f
20.	Столбец «f» не содержит других возможных вершин. Исключаем вершину «f».	а, b, e, d
21.	Столбец «d» не содержит других возможных вершин. Исключаем вершину «d».	а, b, e
22.	Столбец «е» не содержит других возможных вершин. Исключаем вершину «e».	а, b
23.	Столбец «b» не содержит других возможных вершин. Исключаем вершину «b».	a
24.	Столбец «a» не содержит других возможных вершин. Поиск закончен.