Типовой расчет графов
Данная работа является типовым расчетом N2 по курсу "Дискретная математика" по теме "Графы", предлагаемая студентам МГТУ им. Баумана. (Вариант N 17). Сразу хочу сказать для своих коллег: Граждане! Имейте терпение и совесть, поймите, что я это делаю для Вас с целью помочь разобраться в этой теме, а не просто свалить очередной предмет. Мне известно, как непросто сейчас с литературой, и с информацией вообще. Поиски неизвестно какой книги занимают много времени, поэтому в конце я привел небольшой список литературы, составленный мной из различных источников в дополнение к списку, написанному ранее в работе по графам (о постановке лаб. работ по алгоритму Прима и Дейкстра), которая, я надеюсь, есть в сети. Содержание работы: Типовой расчет состоит из 11-ти задач:
1, 2 и 3 задачи относятся к способам задания графов и опредению их характеристик, таких как диаметр, радиус и т. д.
4 и 5 задачи соответственно на алгоритм Прима и Дейкстра. Здесь я снова отсылаю Вас к более ранней работе (см. выше).
6-я задача о поиске максим ального потока в сети (метод Форда-Фалкерсона). 7-я задача - Эйлерова цепь (задача о почтальоне). 8-я задача - Гамильтонова цепь.
9-я задача - метод ветвей и границ применительно к задаче о коммивояжере. 10-я задача - задача о назначениях; венгерский алгоритм. 11-я задача - тоже методом ветвей и границ. Gор(V, X) Рис. 1
Задача1 Для неориентированного графа G, ассоциированного с графом Gор выписать (перенумеровав вершины) : а) множество вершин V и множество ребер X, G(V, X); б) списки смежности; в) матрицу инцидентности; г) матрицу весов. д) Для графа Gор выписать матрицу смежности. Нумерация вершин - см. Рис 1 а) V={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
X={{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 4}, {1, 5}, {1, 6}, {1, 7}, {2, 3}, {2, 5}, {3, 8}, {3, 9}, {4, 5}, {4, 6}, {5, 3}, {5, 6}, {5, 8}, {6, 9}, {7, 8}, {7, 9}, {8, 9}} В дальнейшем ребра будут обозначаться номерами в указанном порядке начиная с нуля. б) Г0={1, 2, 3}; Г1={0, 2, 4, 5, 6, 7}; Г2={0, 1, 3, 5}; Г3={0, 2, 5, 8, 9}; Г4={1, 5, 6}; Г5={1, 2, 3, 4, 6, 8}; Г6={1, 4, 5, 9}; Г7={1, 8, 9}; Г8={1, 3, 5, 7, 9}; Г9={3, 6, 7, 8}; в) Нумерация вершин и ребер соответственно п. а) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 3 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 4 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 5 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 6 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 7 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 9 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1
г) Показана верхняя половина матрицы, т. к. матрица весов неориентированного графа симметрична относительно главной диагонали. 0 1 2 3 4 5 6 7 8 9 0 Ґ 8 3 5 Ґ Ґ Ґ Ґ Ґ Ґ 1 Ґ 1 Ґ 2 2 4 5 Ґ Ґ 2 Ґ 2 Ґ 5 Ґ Ґ Ґ Ґ 3 Ґ Ґ 1 Ґ Ґ 1 6 4 Ґ 4 2 Ґ Ґ Ґ 5 Ґ 2 Ґ 1 Ґ 6 Ґ Ґ Ґ 2 7 Ґ 1 1 8 Ґ 6 9 Ґ д) Матрица смежности для графа Gор. 0 1 2 3 4 5 6 7 8 9 0 Ґ 1 1 1 Ґ Ґ Ґ Ґ Ґ Ґ 1 -1 Ґ 1 Ґ 1 1 1 1 Ґ Ґ 2 -1 -1 Ґ 1 Ґ 1 Ґ Ґ Ґ Ґ 3 -1 Ґ -1 Ґ Ґ -1 Ґ Ґ 1 1 4 Ґ -1 Ґ Ґ Ґ 1 1 Ґ Ґ Ґ 5 Ґ -1 -1 1 -1 Ґ 1 Ґ 1 Ґ 6 Ґ -1 Ґ Ґ -1 -1 Ґ Ґ Ґ 1 7 Ґ -1 Ґ Ґ Ґ Ґ Ґ Ґ 1 1 8 Ґ Ґ Ґ -1 Ґ -1 Ґ -1 Ґ 1 9 Ґ Ґ Ґ -1 Ґ Ґ -1 -1 -1 Ґ
Задача 2 Найти диаметр D(G), радиус R(G), количество центров Z(G) для графа G ; указать вершины, являющиеся центрами графа G. D(G)=2 R(G)=2 Z(G)=10 Все вершины графа G(V, X) являются центрами.
Задача 3 Перенумеровать вершины графа G, используя алгоритмы: а) "поиска в глубину"; б) "поиска в ширину". Исходная вершина - a. а) б)
Задача 4 Используя алгоритм Прима найти остов минимального веса графа G. выписать код укладки на плоскости найденного дерева, приняв за корневую вершинуa. Вес найденного дерева - 14. Код укладки дерева: 000011000001111111.
Задача 5 Используя алгоритм Дейкстра найти дерво кратчайших путей из вершины a графа G. Вес найденного пути - 8.
Задача 6 Используя алгоритм Форда - Фалкерсона, найти максимальный поток во взвешенной двуполюсной ориентированной сети {Gор , a , w}. Указать разрез минимального веса.
Последовательность насыщения сети (насыщенные ребра отмечены кружечками): 1-й шаг 2-й шаг 3-й шаг 4-й шаг 5-й шаг 6-й шаг 7-й шаг Окончательно имеем:
Как видно из рисунка, ребра {6, 9}, {7, 9}, {3, 9}, питающие вершину w, насыщенны, а оставшееся ребро {8, 9}, питающееся от вершины 8, не может получить большее значение весовой функции, так как насыщенны все ребра, питающие вершину 8. Другими словами - если отбросить все насыщенные ребра, то вершинаw недостижима, что является признаком максимального потока в сети. Максимальный поток в сети равен 12.
Минимальный разрез сети по числу ребер: {{0, 1}, {0, 2}, {0, 3}}. Его пропускная способность равна 16
Минимальный разрез сети по пропускной способности: {{6, 9}, {7, 9}, {3, 9}, {3, 8}, {5, 8}, {7, 8}}. Его пропускная способность равна 12.
Задача 7 (Задача о почтальоне) Выписать степенную последовательность вершин графа G. а) Указать в графе G Эйлерову цепь. Если таковой цепи не существует, то в графе G добавить наименьшее число ребер таким образом, чтобы в новом графе можно было указать Эйлерову цепь.
б) Указать в графе G Эйлеров цикл. Если такого цикла не существует, то в графе G добавить наименьшее число ребер таким образом, чтобы в новом графе можно было указать Эйлеров цикл. Степенная последовательность вершин графа G: (3, 6, 4, 5, 3, 6, 4, 3, 4, 4)
а) Для существования Эйлеровой цепи допустимо только две вершины с нечетными степенями, поэтому необходимо добавить одно ребро, скажем между вершинами 4 и 7.
Полученная Эйлерова цепь: 0, 3, 2, 0, 1, 2, 5, 1, 4, 5, 6, 1, 7, 4, 6, 9, 7, 8, 9, 3, 8, 5, 3. Схема Эйлеровой цепи (добавленное ребро показано пунктиром):
б) Аналогично пункту а) добавляем ребро {3, 0}, замыкая Эйлерову цепь (при этом выполняя условие существования Эйлерова цикла - четность степеней всех вершин). Ребро {3, 0} кратное, что не противоречит заданию, но при необходимости можно ввести ребра {0, 7} и {4, 3} вместо ранее введенных.
Полученный Эйлеров цикл: 0, 3, 2, 0, 1, 2, 5, 1, 4, 5, 6, 1, 7, 4, 6, 9, 7, 8, 9, 3, 8, 5, 3, 0. Схема Эйлерова цикла (добавленные ребра показаны пунктиром): Задача 8
а) Указать в графе Gор Гамильтонов путь. Если такой путь не существует, то в графе Gоризменить ориентацию наименьшего числа ребер таким образом, чтобы в новом графе Гамильтонов путь можно было указать.
б) Указать в графе Gор Гамильтонов цикл. Если такой цикл не существует, то в графе Gоризменить ориентацию наименьшего числа ребер таким образом, чтобы в новом графе Гамильтонов цикл можно было указать.
а) Гамильтонов путь (ребра с измененной ориентацией показаны пунктиром):
б) Гамильтонов цикл (ребра с измененной ориентацией показаны пунктиром):
Задача 9 (Задача о коммивояжере) Дан полный ориентированный симметрический граф с вершинами x1, x2, ....xn. Вес дуги xixj задан элементами Vijматрицы весов. Используя алгоритм метода ветвей и границ, найти Гамильтонов контур минимального (максимального) веса. Задачу на максимальное значение Гамильтонова контура свести к задаче на минимальное значение, рассмотрев матрицу с элементами, где . Выполнить рисунок. Исходная таблица. x1 x2 x3 x4 x5 x6 x1 Ґ 3 7 2 Ґ 11 x2 8 Ґ 06 Ґ 4 3 x3 6 05 Ґ 7 Ґ 2 x4 6 Ґ 13 Ґ 5 Ґ x5 3 3 3 4 Ґ 5 x6 8 6 Ґ 2 2 Ґ Таблица Е 14 x1 x2 x3 x4 x5 x6 x1 Ґ 1 5 01 Ґ 7 2 x2 8 Ґ 01 Ґ 4 1 x3 6 00 Ґ 7 Ґ 00 x4 1 Ґ 8 Ґ 01 Ґ 5 x5 01 00 00 1 Ґ 00 3 x6 6 4 Ґ 00 00 Ґ 2 2 Дробим по переходу x2-x3: Таблица 23 е=14+0=14 x1 x2 x4 x5 x6 x1 Ґ 1 01 Ґ 7 x3 6 Ґ 7 Ґ 06 x4 1 Ґ Ґ 01 Ґ x5 01 01 1 Ґ 00 x6 6 4 00 00 Ґ Таблица 23 е=14+1=15 x1 x2 x3 x4 x5 x6 x1 Ґ 1 5 01 Ґ 7 x2 7 Ґ Ґ Ґ 3 03 1 x3 6 00 Ґ 7 Ґ 00 x4 1 Ґ 8 Ґ 01 Ґ x5 01 00 05 1 Ґ 00 x6 6 4 Ґ 00 00 Ґ Продолжаем по 23. Дробим по переходу x3-x6: Таблица 23E36 е=14+0=14 x1 x2 x4 x5 x1 Ґ 1 01 Ґ x4 1 Ґ Ґ 01 x5 01 01 1 Ґ x6 6 Ґ 00 00 Таблица 2336 е=14+6=20 x1 x2 x4 x5 x6 x1 Ґ 1 01 Ґ 7 x3 01 Ґ 1 Ґ Ґ 6 x4 1 Ґ Ґ 01 Ґ x5 00 01 1 Ґ 07 x6 6 4 00 00 Ґ Продолжаем по 2336. Дробим по переходу x4-x5: Таблица 23E3645 е=14+0=14 x1 x2 x4 x1 Ґ 1 01 x5 01 01 1 x6 6 Ґ 00 Таблица 233645 е=14+1=15 x1 x2 x4 x5 x1 Ґ 1 01 Ґ x4 00 Ґ Ґ Ґ 1 x5 01 01 1 Ґ x6 6 Ґ 00 00 Продолжаем по 233645. Дробим по переходу x5-x1: Таблица 23364551 е=14+1=15 x2 x4 x1 1 Ґ 1 x6 Ґ 00 Таблица 23364551 е=14+6=20 x1 x2 x4 x1 Ґ 1 01 x5 Ґ 01 Ґ x6 0 Ґ 00 6 Окончательно имеем Гамильтонов контур: 2, 3, 6, 4, 5, 1, 2. Прадерево разбиений:
Задача 10 (Задача о назначениях) Дан полный двудольный граф Knn с вершинами первой доли x1, x2, ....xn. и вершинами другой доли y1, y2, ....yn...Вес ребра {xi, yj} задается элементами vijматрицы весов. Используя венгерский алгоритм, найти совершенное паросочетание минимального (максимального веса). Выполнить рисунок. Матрица весов двудольного графа K55 : y1 y2 y3 y4 y5 x1 2 0 0 0 0 x2 0 7 9 8 6 x3 0 1 3 2 2 x4 0 8 7 6 4 x5 0 7 6 8 3
Первый этап - получение нулей не нужен, т. к. нули уже есть во всех строк и столбцах. Второй этап - нахождение полного паросочетания. y1 y2 y3 y4 y5 x1 2 0 0 0 0 x2 0 7 9 8 6 x3 0 1 3 2 2 x4 0 8 7 6 4 x5 0 7 6 8 3 Третий этап - нахождение максимального паросочетания. y1 y2 y3 y4 y5 x1 2 0 0 0 0 X x2 0 7 9 8 6 X x3 0 1 3 2 2 x4 0 8 7 6 4 x5 0 7 6 8 3 X X Четвертый этап - нахождение минимальной опоры. y1 y2 y3 y4 y5 x1 2 0 0 0 0 x2 0 7 9 8 6 5 x3 0 1 3 2 2 1 x4 0 8 7 6 4 2 x5 0 7 6 8 3 3 4 Пятый этап - возможная перестановка некоторых нулей. y1 y2 y3 y4 y5 x1 3 0 0 0 0 x2 0 6 8 7 5 5 x3 0 0 2 1 1 1 x4 0 7 6 5 3 2 x5 0 6 5 7 2 3 4 Решение с ненулевым значением. Переход ко второму этапу. Полное паросочетание: y1 y2 y3 y4 y5 x1 3 0 0 0 0 x2 0 6 8 7 5 x3 0 0 2 1 1 x4 0 7 6 5 3 x5 0 6 5 7 2 Максимальное паросочетание: y1 y2 y3 y4 y5 x1 3 0 0 0 0 X x2 0 6 8 7 5 X x3 0 0 2 1 1 x4 0 7 6 5 3 x5 0 6 5 7 2 X X Минимальная опора: y1 y2 y3 y4 y5 x1 3 0 0 0 0 6 x2 0 6 8 7 5 7 x3 0 0 2 1 1 1 x4 0 7 6 5 3 2 x5 0 6 5 7 2 3 4 5 Перестановка нулей: y1 y2 y3 y4 y5 x1 3 0 0 0 0 6 x2 0 6 8 7 5 7 x3 0 0 2 1 1 1 x4 0 7 6 5 3 2 x5 0 6 5 7 2 3 4 5 Полное паросочетание: y1 y2 y3 y4 y5 x1 3 0 0 0 0 6 x2 0 6 8 7 5 7 x3 0 0 2 1 1 1 x4 0 7 6 5 3 2 x5 0 6 5 7 2 3 4 5 Максимальное паросочетание: y1 y2 y3 y4 y5 x1 3 0 0 0 0 X x2 0 6 8 7 5 x3 0 0 2 1 1 X x4 0 7 6 5 3 X x5 0 6 5 7 2 X X X Минимальная опора: y1 y2 y3 y4 y5 x1 3 0 0 0 0 x2 0 6 8 7 5 1 x3 0 0 2 1 1 x4 0 7 6 5 3 x5 0 6 5 7 2 2 3 Перестановка нулей: y1 y2 y3 y4 y5 x1 5 0 0 0 0 x2 0 4 6 5 3 1 x3 2 0 2 1 1 x4 2 7 6 5 3 x5 0 4 3 5 0 2 3 Полное паросочетание: y1 y2 y3 y4 y5 x1 5 0 0 0 0 x2 0 4 6 5 3 x3 2 0 2 1 1 x4 2 7 6 5 3 x5 0 4 3 5 0 Максимальное паросочетание: y1 y2 y3 y4 y5 x1 5 0 0 0 0 X x2 0 4 6 5 3 X x3 2 0 2 1 1 X x4 2 7 6 5 3 x5 0 4 3 5 0 X X X X X Минимальная опора: y1 y2 y3 y4 y5 x1 5 0 0 0 0 x2 0 4 6 5 3 x3 2 0 2 1 1 x4 2 7 6 5 3 1 x5 0 4 3 5 0 Перестановка нулей: y1 y2 y3 y4 y5 x1 5 0 0 0 0 x2 0 4 6 5 3 x3 2 0 2 1 1 x4 0 5 4 3 1 1 x5 0 4 3 5 0 Полное паросочетание: y1 y2 y3 y4 y5 x1 5 0 0 0 0 x2 0 4 6 5 3 x3 2 0 2 1 1 x4 0 5 4 3 1 1 x5 0 4 3 5 0 Максимальное паросочетание: y1 y2 y3 y4 y5 x1 5 0 0 0 0 X x2 0 4 6 5 3 X x3 2 0 2 1 1 X x4 0 5 4 3 1 x5 0 4 3 5 0 X X X X X Минимальная опора: y1 y2 y3 y4 y5 x1 5 0 0 0 0 x2 0 4 6 5 3 3 x3 2 0 2 1 1 x4 0 5 4 3 1 1 x5 0 4 3 5 0 2 Перестановка нулей: y1 y2 y3 y4 y5 x1 6 0 0 0 0 x2 0 3 5 4 2 3 x3 3 0 2 1 1 x4 0 4 3 2 0 1 x5 1 4 3 5 0 2 Полное паросочетание: y1 y2 y3 y4 y5 x1 6 0 0 0 0 x2 0 3 5 4 2 3 x3 3 0 2 1 1 x4 0 4 3 2 0 1 x5 1 4 3 5 0 2 Максимальное паросочетание: y1 y2 y3 y4 y5 x1 6 0 0 0 0 X x2 0 3 5 4 2 X x3 3 0 2 1 1 X x4 0 4 3 2 0 x5 1 4 3 5 0 X X X X X Минимальная опора: y1 y2 y3 y4 y5 x1 6 0 0 0 0 x2 0 3 5 4 2 4 x3 3 0 2 1 1 x4 0 4 3 2 0 1 x5 1 4 3 5 0 5 2 3 В результате имеем: y1 y2 y3 y4 y5 x1 6 0 0 0 0 x2 0 1 3 2 2 4 x3 3 0 2 1 1 x4 0 2 1 0 0 1 x5 1 4 3 5 0 5 2 3 Исходный граф Полученный граф: Вес найденного совершенного паросочетания = 12.
Задача 11 Решить задачу 10, используя алгоритм ветвей и границ (отождествив вершины xi и yj). Таблица Е (исходная). Строки - xi , столбцы - yj. е=0 1 2 3 4 5 1 2 01 03 02 02 2 06 7 9 8 6 3 01 1 3 2 2 4 04 8 7 6 4 5 03 7 6 8 3 Дробим по переходу x2 - y1: Таблица Е21 е=0+8=8 2 3 4 5 1 00 02 01 00 3 01 2 1 1 1 4 4 3 2 02 4 5 4 3 5 03 3 Таблица 21 е=0+6=6 1 2 3 4 5 1 2 01 03 02 00 2 Ґ 1 3 2 01 6 3 01 1 3 2 2 4 04 8 7 6 4 5 03 7 6 8 3 Продолжаем по 21: Дробим по переходу x4 - y1: Таблица 21Е41 е=6+4=10 2 3 4 5 1 00 02 01 00 2 1 3 2 01 3 01 2 1 1 1 5 4 3 5 03 3 Таблица 2141 е=6+4=10 1 2 3 4 5 1 2 01 03 02 00 2 Ґ 1 3 2 01 3 01 1 3 2 2 4 Ґ 4 3 2 02 4 5 03 7 6 8 3 Продолжаем по Е21: Дробим по переходу x5 - y5: Таблица Е21Е55 е=8+2=10 2 3 4 1 00 01 00 3 01 2 1 4 2 1 01 2 Таблица Е2155 е=8+3=11 2 3 4 5 1 00 02 01 00 3 01 2 1 1 4 4 3 2 02 5 1 01 2 Ґ 3 Продолжаем по Е21Е55: Дробим по переходу x3 - y2: Таблица Е21Е55Е32 е=10+0=10 3 4 1 01 00 4 1 01
Далее решение очевидно: x1 - y3 и x4 - y4. Это не увеличит оценку. В итоге имеем совершенное паросочетание с минимальным весом: Прадерево разбиений: Литература
1. Грешилов А. А. Как принять наилучшее решение в реальных условиях: -М. :Радио и связь, 1991. -320с. :ил.
2. Беллман Р. Динамическое программирование: Пер. с англ. /Под ред. Н. Н. Воробьева. -М. : ИЛ, 1960. -400 с.
3. Беллман Р. , Дрейфус С. Прикладные задачи динамического программирования: Пер с англ. /Под ред. А. А. Первозванского. -М. : Наука, 1965. -458 с. 4. Вентцель Е. С. Исследование операций. -М. : Сов. радио, 1972. -551 с. 5. Вильямс Н. Н. Параметрическое программирование в экономике (методы оптимальных решений): -М. :Статистика, 1976. -96с.
6. Гольштейн Е. Г. , Юдин Д. Б. Новые направления в линейном программировании: -М. : Сов радио, 1966. - 524 с.
7. Зангвилл У. И. Нелинейное программирование: Пер. с англ. /Под ред. Е. Г. Гольштейна. -М. : Сов радио, 1973. - 312 с.
8. Зуховицкий С. И. , Авдеева Л. И. Линейное и выпуклое программирование (справочное руководство). -М. : Наука, 1964. -348 с.
9. Исследование операций. Методологические основы и математические методы: Пер. с англ. / Под ред. И. М. Макарова, И. М. Бескровного. -М. : Мир, 1981. - Т. 1. -712 с. 10. Исследование операций. Модели и применение: Пер. с англ. / Под ред. И. М. Макарова, И. М. Бескровного. -М. : Мир, 1981. - Т. 1. -712 с.
11. Лазарев В. Г. , Лазарев Ю. В. Динамическое управление потоками информации в сетях связи. -М. : Радио и связь, 1983. - 216 с.
12. Мартин Дж. Системный анализ передачи данных. : Пер с англ. / Под ред. В. С. Лапина. -М. : Мир, 1975. - М. 2. - 431 с.
13. Монаков В. М. , Беляева Э. С. , Краснер Н. Я. Методы оптимизации. Пособие для учителя. -М. : Просвещение, 1978. - 175с.
14. Муртаф Б. Современное линейное программирование: Теория и практика. Пер. с англ. /Под ред. И. А. Станевичуса. - М. : Мир, 1984. - 224 с.
15. Рокафеллор Р. Выпуклый анализ: Пер. с англ. /Под ред. А. Д. Иоффе, В. М. Тихомирова. -М. : Мир, 1973. - 469 с.
16. Сухарев А. Г. , Тимохов А. В. , Федоров В. В. Курс методов оптимизации. - М. : Наука, Физматгиз, 1986. - 326 с.
17. Ху Т. Целочисленное программирование и потоки в сетях: Пер. с англ. /Под ред. А. А. Фридмана. - М. : Мир, 1974. -419 с.
18. Фиакко А. , Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации: Пер. с англ. /Под ред. Е. Г. Гольштейна. -М. :- Мир, 1972. - 240 с.
19. Филлипс Д. , Гарсиа-Диас А. Методы анализа сетей: Пер. с англ. / Под ред. Б. Г. Сушкова. - М. : Мир, 1984. - 496 с.
20. Юдин Д. Б. , Гольштейн Е. Г. Линейное программирование. Теория и конечные методы, - М. :- Физматгиз, 1963. - 775 с.