Дискретная математика (Обход графа, Алгоритм Форда – Фалкерсона и т.д. и т.п), страница 7
Описание файла
Файл "Дискретная математика" внутри архива находится в папке "Обход графа, Алгоритм Форда - Фалкерсона и т.д. и т.п". Документ из архива "Обход графа, Алгоритм Форда – Фалкерсона и т.д. и т.п", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 3 семестр, которые можно найти в файловом архиве МАИ. Не смотря на прямую связь этого архива с МАИ, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "дискретная математика" в общих файлах.
Онлайн просмотр документа "Дискретная математика"
Текст 7 страницы из документа "Дискретная математика"
Перестроим поток следующим образом: (е+) заменим на (е+) + K, а (е –) на (е –) – K. Условия 1 и 2 останутся выполненными, а величина потока при этом увеличится на K. Повторяем процедуру до тех пор, пока t перестанет быть достижимой. Пусть S - множество всех вершин, достижимых из s, а Т = V \ S содержит t. Следовательно, это разрез, при этом дуги, входящие в Р +, насыщены, а дуги из Р – имеют нулевой поток (иначе S можно было бы расширить).
Таким образом, W ( ) = Ф (Р +) – Ф (Р – ) = С (Р +) – 0 = С (Р +), то есть поток максимальный, а Р + - минимальный орразрез.
Пример
Найти максимальный поток для сети Т (рис. 24).
Рис. 24
Решение:
1) Перенумеруем поток произвольным образом. Вершина-исток должна иметь номер 1, а вершина-сток – максимальное значение среди всех вершин сети. Зададим начальный поток в сети = 0 и присвоим вершине-истоку нулевую метку (рис. 25).
Рис. 25
2) Пометим вершины и дуги сети (рис. 26), пользуясь следующим правилом: пусть v – помеченная вершина, w – непомеченная, тогда:
- если w = Г +(v), т.е. дуга направлена от вершины v к вершине w, и выполняется неравенство , вершине w присваивается метка, равная номеру вершины v, а дуге – значение «+»;
- если w = Г – (v), т.е. дуга направлена от вершины w к вершине v, и выполняется неравенство , вершине w присваивается потенциал, равный номеру вершины v, а дуге – значение «–».
Рис. 26
Вершина-сток получила метку, поэтому продолжаем решение.
3) Рассмотрим подграф исходного графа (рис. 27), такой, что метка вершины w соответствует номеру вершины v, где v – вершина-начало дуги (v, w).
Рис. 27
4) Перестроим поток в сети по правилу:
-
если некоторая дуга е не принадлежит рассматриваемому подграфу, то величина нового потока составит * (е) = (е);
-
если некоторая дуга е принадлежит рассматриваемому подграфу и имеет знак «+», то * (е) = (е) + K1, где K1 = min [с (е) – (е)];
-
если некоторая дуга е принадлежит рассматриваемому подграфу и имеет знак «–», то * (е) = (е) – K2, где K2 = min [ (е)].
В рассматриваемом случае (рис. 28) * = 0 + min [1, 2, 2] = 1.
Рис. 28
Далее осуществляем переход к п. 2, по результатам выполнения которого представляется граф с заново размеченными вершинами (рис. 29):
Рис. 29
Вершина-сток получила метку, поэтому продолжаем решение. Зададим новый поток при рассмотрении подграфа, отраженного на рис. 26.
K1 = min [4, 3, 1] = 1;
* (1,4) = 0 + K1 = 1; * (4,3) = 0 + K1 = 1; * (3,6) = 1+ K1 = 2;
* = min [* (1,4), * (4,3), * (3,6)] = 1.
5) Увеличим поток в сети на величину * (рис. 30) и осуществим переход к п. 2, результат выполнения которого отражен на рис. 31.
Рис. 30
Рис. 31
Вершине-стоку присвоен потенциал, поэтому продолжаем решение. Перестроим поток в сети:
K1 = min [3, 2, 1, 3, 1] = 1;
* (1,4) = 1 + K1 = 2; * (4,3) = 1 + K1 = 2; * (3,2) = 1+ K1 = 2;
* (2,5) = 0 + K1 = 1; (5,6) = 0+ K1 = 1;
*= min [* (1,4), * (4,3), * (3,2), * (2,5), * (5,6)] = 1.
6) Увеличиваем поток в сети на величину * (рис. 32) и осуществляем переход к п. 2 (рис. 33).
Рис. 32
Рис. 33
Вершина-сток не получила метку, что свидетельствует о том, что максимальный поток в рассматриваемой сети найден (рис. 34).
Рис. 34
Таким образом, по результатам выполнения алгоритма получили, что множество достижимых из вершины-истока вершин S = {1, 3, 4}; множество недостижимых из вершины-истока вершин Т = {2, 5, 6}. Минимальным орразрезом является Р +: (3;6).
Максимальный поток в сети равен 2.
Задания
Определить минимальный орразрез и найти максимальный поток.
1Ответы
1. Обходы графов в ширину и глубину
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
1 | 2, 3 | 4, 5 | ||||||
2 | 2, 3 | 4, 5 | 6, 7 | |||||
3 | 2, 3 | 4 | 5, 6 | |||||
4 | 2, 3 | 4 | 5, 6 | 7 | ||||
5 | 2, 3 | 4, 5 | ||||||
6 | 2, 3 | 4, 5 | 6, 7 | |||||
7 | 2 | 1, 4, 5 | ||||||
8 | 2 | 4, 5 | 1, 6, 7 | |||||
9 | 2 | 4 | 1, 5, 6 | |||||
10 | 2 | 4 | 1, 5, 6 | 7 | ||||
11 | 2 | 4, 5 | 1 | |||||
12 | 2 | 4, 5 | 1 | 6, 7 | ||||
13 | 3 | 1 | 4, 5 | |||||
14 | 3 | 1, 4, 5 | 6, 7 | |||||
15 | 3 | 1, 4 | 5, 6 | 7 | ||||
16 | 3 | 1, 4, 5 | 6, 7 | |||||
17 | 3 | 1, 4 | 5, 6 | |||||
18 | 3 | 1, 4, 5 | ||||||
19 | 2 | 1, 5 | 3 | |||||
20 | 3 | 1, 5 | 6, 7 | 2 | ||||
21 | 3 | 1 | 5, 6 | 2 | ||||
22 | 3 | 1 | 5, 6 | 2 | 7 | |||
23 | 3 | 1, 5 | 2 | |||||
24 | 3 | 1, 5 | 2 | 6, 7 | ||||
25 | 2, 3 | 4, 5 | 6, 7, 8 | |||||
26 | 2, 3 | 4, 5, 6 | ||||||
27 | 2, 3 | 4, 5, 6 | 7 | |||||
28 | 2, 3, 7 | 4, 5, 6 | ||||||
29 | 2, 7, 3 | 4, 5, 6 | 8 | |||||
30 | 2, 3 | 4, 5, 6 | 7, 8 |
2. Алгоритм Тэрри
-
3 – 2 – 4 – 1 – 5
-
1 – 2 – 3 – 5 – 4
-
5 – 2 – 4 – 1 – 3
-
1 – 2 – 5 – 4 – 3
-
2 – 5 – 4 – 3 – 1
-
2 – 1 – 3 – 4 – 5
-
4 – 3 – 2 – 5 – 1
-
1 – 2 – 3 – 5 – 4
-
3 – 5 – 4 – 2 – 1
-
5 – 3 – 4 – 2 – 1
-
1 – 3 – 2 – 4 – 5 – 6
-
4 – 3 – 5 – 6 – 1 – 2
-
5 – 4 – 3 – 6 – 1 – 2
-
2 – 3 – 4 – 6 – 5 – 1
-
6 – 4 – 5 – 3 – 2 – 1
-
2 – 1 – 3 – 4 – 5 – 6
-
6 – 5 – 2 – 1 – 3 – 4
-
3 – 2 – 5 – 6 – 4 – 1
-
5 – 6 – 2 – 4 – 3 – 1
-
1 – 2 – 5 – 6 – 4 – 3
-
1 – 2 – 3 – 4 – 5 – 6
-
3 – 1 – 2 – 4 – 5 – 6
-
4 – 3 – 5 – 1 – 2 – 6
-
6 – 5 – 4 – 3 – 2 – 1
-
2 – 3 – 5 – 6 – 4 – 1
-
2 – 1 – 3 – 4 – 5
-
5 – 3 – 4 – 1 – 2
-
1 – 3 – 5 – 4 – 2
-
3 – 5 – 4 – 2 – 1
-
4 – 5 – 3 – 1 – 2
3. Матроиды. Жадные алгоритмы. Алгоритм Краскала
-
(2,5); (1,4); (3,4); (4,5).
-
(3,4); (4,5); (7,8); (4,7); (5,6);
(2,3); (1,6). -
(2,6); (4,5); (4,6); (3,4); (1,3).
-
(1,2); (3,6); (2,6); (4,5); (3,4).
-
(1,2); (6,8); (7,8); (1,8); (2,3);
(5,6); (3,4). -
(2,3); (1,4); (2,4); (1,5).
-
(1,6); (3,4); (4,5); (4,7); (5,6);
(1,2); (7,8). -
(1,2); (2,6); (4,5); (3,4); (5,6).
-
(2,6); (4,5); (4,6); (3,4); (1,3).
-
(1,8); (2,3); (3,4); (2,8); (6,8);
(7,8); (4,5). -
(2,4); (1,5); (2,3); (2,5).
-
(3,4); (7,8); (1,6); (3,8); (5,6);
(2,3); (6,7). -
(2,6); (4,6); (1,2); (1,3); (5,6).
-
(1,3); (3,6); (5,6); (2,6); (4,6).
-
(2,4); (5,6); (6,8); (1,8); (3,4);
(1,2); (7,8). -
(1,4); (1,5); (1,2); (2,3).
-
(4,5); (5,6); (7,8); (1,2); (4,7);
(1,6); (2,3). -
(3,4); (4,5); (4,6); (2,3); (1,2).
-
(2,6); (4,6); (1,2); (1,3); (5,6).
-
(1,8); (3,4); (1,2); (2,4); (5,6);
(6,8) (7,8). -
(1,3); (4,5); (2,4); (1,4).
-
(2,3); (3,8); (3,4); (4,7); (1,6);
(4,5); (1,8). -
(1,3); (5,6); (2,6); (4,6); (1,2).
-
(2,3); (1,2); (5,6); (2,6); (4,5).
-
(6,7); (1,2); (5,6); (1,8); (2,3);
(4,5); (6,8). -
(1,2); (2,5); (1,3); (2,4).
-
(1,2); (4,7); (1,6); (2,3); (3,4);
(4,5); (1,8). -
(2,3); (1,2); (5,6); (2,6); (4,5).
-
(1,3); (5,6); (2,6); (4,6); (1,2).
-
(2,4); (5,6); (1,8); (3,4); (1,2);
(4,5); (7,8).
4. Нахождение кратчайшего пути в сети без контуров
-
Правильная нумерация: 0-0, 2-1, 3-2, 4-3, 1-4.
Потенциалы: 0-0, 1-1, 2-5, 3-6, 4-8. Кратчайший путь: 0 1 4. -
Правильная нумерация: 0-0, 1-1, 2-2, 3-3, 4-4.
Потенциалы: 0-0, 1-1, 2-9, 3-5, 4-11. Кратчайший путь: 0 1 3 4. -
Правильная нумерация: 1-0, 2-1, 3-2, 1-3, 4-4.
Потенциалы: 0-0, 1-8, 2-4, 3-13, 4-7. Кратчайший путь: 0 2 4. -
Правильная нумерация: 0-0, 2-1, 3-2, 1-3, 4-4.
Потенциалы: 0-0, 1-8, 2-14, 3-10, 4-3. Кратчайший путь: 0 4. -
Правильная нумерация: 2-0, 0-1, 1-2, 3-3, 4-4.
Потенциалы: 0-0, 1-4, 2-1, 3-8, 4-6. Кратчайший путь: 0 2 4. -
Правильная нумерация: 3-0, 0-1, 1-2, 2-3, 4-4.
Потенциалы: 0-0, 1-6, 2-9, 3-4, 4-6. Кратчайший путь: 0 3 4. -
Правильная нумерация: 2-0, 1-1, 3-2, 4-3, 0-4.
Потенциалы: 0-0, 1-4, 2-12, 3-2, 4-8. Кратчайший путь: 0 3 4. -
Правильная нумерация: 2-0, 0-1, 1-2, 3-3, 4-4.
Потенциалы: 0-0, 1-9, 2-7, 3-16, 4-10. Кратчайший путь: 0 2 4. -
Правильная нумерация: 1-0, 3-1, 0-2, 4-3, 2-4.
Потенциалы: 0-0, 1-7, 2-13, 3-3, 4-5. Кратчайший путь: 0 3 4. -
Правильная нумерация: 1-0, 0-1, 3-2, 2-3, 4-4.
Потенциалы: 0-0, 1-2, 2-4, 3-5, 4-5. Кратчайший путь: 0 4. -
Правильная нумерация: 1-0, 0-1, 3-2, 4-3, 2-4.
Потенциалы: 0-0, 1-6, 2-1, 3-3, 4-3. Кратчайший путь: 0 2 4. -
Правильная нумерация: 2-0, 3-1, 4-2, 0-3, 1-4 .
Потенциалы: 0-0, 1-7, 2-1, 3-2, 4-5. Кратчайший путь: 0 2 4. -
Правильная нумерация: 1-0, 0-1, 3-2, 4-3, 2-4.
Потенциалы: 0-0, 1-4, 2-1, 3-2, 4-7. Кратчайший путь: 0 1 4. -
Правильная нумерация: 1-0, 3-1, 0-2, 2-3, 4-4.
Потенциалы: 0-0, 1-4, 2-2, 3-5, 4-8. Кратчайший путь: 0 2 4. -
Правильная нумерация: 4-0, 0-1, 1-2, 2-3, 3-4.
Потенциалы: 0-0, 1-3, 2-10, 3-7, 4-9. Кратчайший путь: 0 1 3 4. -
Правильная нумерация: 2-0, 0-1, 5-2, 6-3, 1-4, 3-5, 4-6.
Потенциалы: 0-0, 1-6, 2-9, 3-7, 4-8, 5-15, 6-5. Кратчайший путь: 0 6. -
Правильная нумерация: 4-0, 1-1, 2-2, 3-3, 5-4, 0-5, 6-6.
Потенциалы: 0-0, 1-4, 2-6, 3-8, 4-11, 5-8, 6-13. Кратчайший путь: 0 1 6. -
Правильная нумерация: 4-0, 0-1, 2-2, 5-3, 3-4, 1-5, 6-6.
Потенциалы: 0-0, 1-9, 2-2, 3-16, 4-19, 5-7, 6-27.
Кратчайший путь: 0 1 3 4 6. -
Правильная нумерация: 0-0, 1-1, 2-2, 3-3, 4-4, 5-5, 6-6.
Потенциалы: 0-0, 1-1, 2-2, 3-6, 4-9, 5-6, 6-9. Кратчайший путь: 0 6. -
Правильная нумерация: 3-0, 0-1, 1-2, 2-3, 4-4, 6-5, 5-6.
Потенциалы: 0-0, 1-4, 2-5, 3-5, 4-1, 5-3, 6-8. Кратчайший путь: 0 2 4 6. -
Правильная нумерация: 1-0, 0-1, 2-2, 3-3, 4-4, 5-5, 6-6.
Потенциалы: 0-0, 1-6, 2-4, 3-11, 4-7, 5-2, 6-14. Кратчайший путь: 0 1 6. -
Правильная нумерация: 3-0, 0-1, 1-2, 5-3, 2-4, 4-5, 6-6.
Потенциалы: 0-0, 1-4, 2-8, 3-9, 4-10, 5-5, 6-7. Кратчайший путь: 0 1 6. -
Правильная нумерация: 0-0, 1-1, 3-2, 4-3, 5-4, 2-5, 6-6.
Потенциалы: 0-0, 1-3, 2-7, 3-1, 4-8, 5-6, 6-6. Кратчайший путь: 0 6. -
Правильная нумерация: 3-0, 0-1, 1-2, 2-3, 4-4, 6-5, 5-6.
Потенциалы: 0-0, 1-6, 2-4, 3-7, 4-6, 5-3, 6-8. Кратчайший путь: 0 5 6. -
Правильная нумерация: 6-0, 0-1, 3-2, 1-3, 4-4, 2-5, 5-6.
Потенциалы: 0-0, 1-1, 2-9, 3-4, 4-5, 5-6, 6-8. Кратчайший путь: 0 1 6. -
Правильная нумерация: 4-0, 0-1, 1-2, 2-3, 3-4, 6-5, 5-6.
Потенциалы: 0-0, 1-2, 2-8, 3-4, 4-5, 5-9, 6-12. Кратчайший путь: 0 1 5 6. -
Правильная нумерация: 5-0, 0-1, 1-2, 2-3, 3-4, 4-5, 6-6.
Потенциалы: 0-0, 1-2, 2-4, 3-1, 4-7, 5-5, 6-12. Кратчайший путь: 0 2 6. -
Правильная нумерация: 0-0, 1-1, 2-2, 3-3, 4-4, 5-5, 6-6.
Потенциалы: 0-0, 1-1, 2-4, 3-5, 4-6, 5-11, 6-4. Кратчайший путь: 0 1 6. -
Правильная нумерация: 1-0, 0-1, 2-2, 3-3, 4-4, 5-5, 6-6.
Потенциалы: 0-0, 1-1, 2-6, 3-9, 4-5, 5-7, 6-5. Кратчайший путь: 0 1 6. -
Правильная нумерация: 1-0, 0-1, 2-2, 3-3, 5-4, 6-5, 4-6.
Потенциалы: 0-0, 1-5, 2-2, 3-8, 4-14, 5-1, 6-9. Кратчайший путь: 0 5 6.
5. Алгоритм Беллмана - Форда
-
0 – 1 – 2 – 3 – 5
-
0 – 2 – 3 – 5
-
0 – 1 – 3 – 2 – 4 – 5
-
0 – 2 – 1 – 3 – 5
-
0 – 2 – 4 – 5
-
0 – 2 – 5 – 3 – 6
-
0 – 2 – 1 – 5 – 3 – 4 – 6
-
0 – 1 – 5 – 3 – 6
-
0 – 2 – 5 – 3 – 4 – 6
-
0 – 2 – 1 – 5 – 4 – 6
-
0 – 2 – 1 – 3 – 4 – 6 – 5 – 7
-
0 – 1 – 3 – 4 – 6 – 7
-
0 – 1 – 3 – 5 – 7
-
0 – 2 – 4 – 6 – 5 – 7
-
0 – 2 – 1 – 3 – 5 – 7
-
0 – 3 – 6
-
0 – 1 – 3 – 4 – 6
-
0 – 3 – 4 – 6
-
0 – 2 – 5 – 6
-
0 – 2 – 3 – 4 – 6
-
0 – 1 – 2 – 3 – 4 – 5 – 6
-
0 – 2 – 3 – 4 – 6
-
0 – 1 – 2 – 4 – 5 – 6
-
0 – 2 – 4 – 6
-
0 – 1 – 2 – 3 – 4 – 6
-
0 – 2 – 3 – 1 – 4 – 6
-
0 – 1 – 4 – 3 – 5 – 6
-
0 – 2 – 3 – 5 – 6
-
0 – 1 – 4 – 6
-
0 – 2 – 5 – 6
1.16. Алгоритм Дейкстра
-
1 4 5.
Длина пути: 7. -
1 2 4 3 5.
Длина пути: 12. -
1 2 3 5.
Длина пути: 7. -
1 4 3 5.
Длина пути: 6. -
1 3 5.
Длина пути: 5. -
1 2 5.
Длина пути: 7. -
1 4 5.
Длина пути: 5. -
1 3 5.
Длина пути: 3. -
1 2 5.
Длина пути: 4. -
1 2 4 5.
Длина пути: 7. -
1 4 5.
Длина пути: 5. -
1 2 3 5.
Длина пути: 4. -
1 4 3 5.
Длина пути: 6. -
1 2 5.
Длина пути: 2. -
1 4 3 5.
Длина пути: 7. -
1 2 3 5.
Длина пути: 11. -
1 2 4 5.
Длина пути: 5. -
1 5.
Длина пути: 1. -
1 2 4 5.
Длина пути: 5. -
1 2 5.
Длина пути: 2. -
1 3 4 5.
Длина пути: 10. -
1 5.
Длина пути: 3. -
1 3 5.
Длина пути: 5. -
1 4 5.
Длина пути: 4. -
1 2 5.
Длина пути: 6. -
1 2 3 4 5.
Длина пути: 11. -
1 4 2 5.
Длина пути: 8. -
1 3 5.
Длина пути: 2. -
1 4 5.
Длина пути: 3. -
1 5.
Длина пути: 1.