- •Федеральное агентство по образованию
- •1 Цели и задачи практических занятий по дискретной математике
- •2 Содержание занятий
- •2.1 Практические занятия № 1 – 2. Множества. Операции над множествами. Свойства операций над множествами
- •2.1.1 Теоретические сведения и методические рекомендации по решению задач
- •1) , То есть;
- •2) , То есть.
- •2.1.2 Примеры решения задач
- •2.1.3 Задачи для самостоятельного решения
- •2.2.1 Теоретические сведения и методические рекомендации по решению задач
- •2.2.2 Примеры решения задач
- •2.2.3 Задачи для самостоятельного решения
- •2.3 Практическое занятие № 8. Соответствия и их свойства
- •2.3.1 Теоретические сведения и методические рекомендации по решению задач
- •2.3.2 Примеры решения задач
- •2.3.3 Задачи для самостоятельного решения
- •G1 g2
- •2.4 Практическое занятие № 9. Операции и их свойства
- •2.4.1 Теоретические сведения и методические рекомендации по решению задач
- •2.4.2 Примеры решения задач
- •2.4.3 Задачи для самостоятельного решения
- •2.5 Практическое занятие № 10. Гомоморфизмы
- •2.5.1 Теоретические сведения и методические рекомендации по решению задач
- •2.5.2 Примеры решения задач
- •2.5.3 Задачи для самостоятельного решения
- •2.6 Практическое занятие № 1112. Алгебры с одной бинарной операцией. Полугруппы. Моноиды. Группы. Подгруппы. Циклические группы. Группа подстановок
- •2.6.1 Теоретические сведения и методические рекомендации по решению задач
- •2.6.2 Примеры решения задач
- •2.7 Практические занятия № 13 – 15. Алгебры с двумя бинарными операциями. Кольца. Поля. Решетки. Булевы алгебры
- •2.7.1 Теоретические сведения и методические рекомендации по решению задач
- •2.7.2 Примеры решения задач
- •2.7.3 Задачи для самостоятельного решения
- •2.8 Практические занятия № 16 – 19. Комбинаторика
- •2.8.1 Теоретические сведения и методические рекомендации по решению задач
- •2.8.2 Примеры решения задач
- •2.8.3 Задачи для самостоятельного решения
- •2.9 Практическое занятие № 20. Контрольная работа
- •2.10 Практические занятия № 21 – 22. Орграфы и бинарные отношения. Связность. Компоненты связности
- •2.10.1 Теоретические сведения и методические рекомендации по решению задач
- •2.10.2Примеры решения задач
- •2.10.3 Задачи для самостоятельного решения
- •2.11 Практические занятия № 23 – 25. Поиск путей в графах орграфах. Минимальные пути в нагруженных орграфах. Эйлеровы цепи и циклы. Сети и потоки
- •2.11.1 Теоретические сведения и методические рекомендации по решению задач
- •2.11.2 Примеры решения задач
- •2.11.3 Задачи для самостоятельного решения
- •3 Технические и инструментальные средства
- •4 Порядок проведения занятий
- •Содержание
2.11.2 Примеры решения задач
Задача 1.Найти минимальный путь из вершиныv1вv6 во взвешенном орграфеG, заданном матрицей весов:
-
v1
v2
v3
v4
v5
v6
v1
∞
∞
5
5
2
12
v2
∞
∞
∞
∞
∞
2
v3
∞
2
∞
∞
∞
∞
v4
∞
2
∞
∞
∞
∞
v5
∞
∞
1
2
∞
∞
v6
∞
∞
∞
∞
∞
∞
Решение. Справа от матрицыC(D) припишем шесть столбцов
|
|
|
|
|
|
Здесь k=0, 1, 2, 3, 4, 5, которые будем определять, используя формулы (1), (2), (3) п. 2.11.1. Величина= 7 выражает длину минимального пути из источникаv1в стокv6 в нагруженном орграфеG.
|
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
|
|
|
|
|
|
v1 |
∞ |
∞ |
5 |
5 |
2 |
12 |
0 |
0 |
0 |
0 |
0 |
0 |
v2 |
∞ |
∞ |
∞ |
∞ |
∞ |
2 |
∞ |
∞ |
7 |
5 |
5 |
5 |
v3 |
∞ |
2 |
∞ |
∞ |
∞ |
∞ |
∞ |
5 |
3 |
3 |
3 |
3 |
v4 |
∞ |
2 |
∞ |
∞ |
∞ |
∞ |
∞ |
5 |
4 |
4 |
4 |
4 |
v5 |
∞ |
∞ |
1 |
2 |
∞ |
∞ |
∞ |
2 |
2 |
2 |
2 |
2 |
v6 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
12 |
12 |
9 |
7 |
7 |
Найдем минимальное число k, при котором выполняется равенство=. Получим, чтоk=4. Таким образом, минимальное число дуг в пути среди всех минимальных путей изv1вv6 в нагруженном орграфеGравняется 4. Определим последовательность номеровi1,i2,i3,i4,i5, гдеi1=6. Из таблицы видно, что в качестве такой последовательности нужно взять номера 6, 2, 3, 5, 1, так как выполняются равенства:
;
;
;
.
Тогда v1v5v3v2v6– искомый минимальный путь изv1вv6 в нагруженном орграфеG, причем он содержит минимальное число дуг среди всех возможных минимальных путей изv1вv6 .
Задача 2. Построить максимальный поток в сетиG, изображенной на рисунке 13 (в скобках указаны пропускные способности дуг).
v2 (6)v5
(7) (3) (2) (9)
v1 (2)v6
(7)
(8) v3v4
(2)
Рисунок 13 – К задаче 2 (2.11.2)
Решение. Источником рассматриваемой сети является вершинаv1, а стоком –v6. Сначала построим полный поток. Все потоки будем записывать в таблицу 6. Начинаем с нулевого потока: полагаем, что для любой дуги х. При нулевом потоке отсутствуют насыщенные дуги. Выделим в сетиGпростую цепьи увеличим потоки по дугам, входящим вна три до насыщения дуги. В результате получим поток1, содержащий одну насыщенную дугу. В таблице 6 потоки по насыщенным дугам отмечены жирным шрифтом. После насыщения дуг исключаем их из рассмотрения. Далее выделяем в сетиGпростую цепьи увеличиваем потоки по дугам изна два до насыщения сразу двух дуг:и. В результате этого действия получаем поток2, содержащий три насыщенные дуги. Выделим в сетиGпростую цепьи увеличим потоки по дугам изна два до насыщения дуги. Получен поток3, содержащий четыре насыщенные дуги. Следующей простой цепью, по дугам которой будем увеличивать потоки, является. Потоки по дугам этой цепи увеличим на два до насыщения дуги. Поток4 содержит уже пять насыщенных дуг. Теперь все пути, ведущие из источникаv1в стокv6, проходят, по крайней мере, через одну насыщенную дугу, значит,4– полный поток.
Таблица 6 - Потоки в сети G
х |
с(х) |
0 |
1 |
2 |
3 |
4 |
5 |
v1v2 |
7 |
0 |
3 |
5 |
5 |
7 |
7 |
v1v3 |
8 |
0 |
0 |
0 |
2 |
2 |
4 |
v2v3 |
2 |
0 |
0 |
2 |
2 |
2 |
0 |
v2v4 |
3 |
0 |
3 |
3 |
3 |
3 |
3 |
v2v5 |
6 |
0 |
0 |
0 |
0 |
2 |
4 |
v3v4 |
2 |
0 |
0 |
2 |
2 |
2 |
2 |
v3v5 |
2 |
0 |
0 |
0 |
2 |
2 |
2 |
v4v6 |
7 |
0 |
3 |
5 |
5 |
5 |
5 |
v5v6 |
9 |
0 |
0 |
0 |
2 |
4 |
6 |
Величина потока |
0 |
3 |
5 |
7 |
9 |
11 |
Строим орграф приращений I(G, 4). Длины дуг орграфа записаны в таблице 7.
Таблица 7 – Длины дуг в орграфе приращений I(G, 4)
х |
l(x) |
х' |
l(x’) |
v1v2 |
|
v2 v1 |
0 |
v1v3 |
0 |
v3 v1 |
0 |
v2v3 |
|
v3 v2 |
0 |
v2v4 |
|
v4 v2 |
0 |
v2v5 |
0 |
v5 v2 |
0 |
v3v4 |
|
v4 v3 |
0 |
v3v5 |
|
v5 v3 |
0 |
v4v6 |
0 |
v6 v4 |
0 |
v5v6 |
0 |
v6 v5 |
0 |
В нагруженном орграфе I(G, 5) имеется простая цепь, длина которой равна нулю. Увеличиваем потоки по цепина максимально допустимую величину два до обнуления потока по дуге(прибавляя к уже имеющимся потокам по дугам прямого направления и вычитая из потока по дуге противоположного направления). В результате получаем поток5.
Строим орграф приращений I(G, 5). Длины дуг орграфа приведены в таблице 8.
Таблица 8 – Длины дуг в орграфе приращений I(G, 5)
х |
l(x) |
х' |
l(x’) |
v1v2 |
|
v2 v1 |
0 |
v1v3 |
0 |
v3 v1 |
0 |
v2v3 |
0 |
v3 v2 |
|
v2v4 |
|
v4 v2 |
0 |
v2v5 |
0 |
v5 v2 |
0 |
v3v4 |
|
v4 v3 |
0 |
v3v5 |
|
v5 v3 |
0 |
v4v6 |
0 |
v6 v4 |
0 |
v5v6 |
0 |
v6 v5 |
0 |
В нагруженном орграфе I(G, 5)длина любого пути изv1вv6равна, следовательно, поток5является максимальным, его величина равна 11.