GV,X Рис. 1 Задача1 Для неориентированного графа G, ассоциированного с графом G выписать перенумеровав вершины а множество вершин V и множество ребер X, GV,X б списки смежности в матрицу инцидентности г матрицу весов. д Для графа G выписать матрицу смежности. Нумерация вершин – см. Рис 1 а V0,1,2,3,4,5,6,7,8,9 X0,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 В дальнейшем ребра будут обозначаться номерами в указанном порядке начиная с нуля. б Г01,2,3 Г10,2,4,5,6,7 Г20,1,3,5 Г30,2,5,8,9 Г41,5,6 Г51,2,3,4,6,8 Г61,4,5,9 Г71,8,9 Г81,3,5,7,9 Г93,6,7,8 в Нумерация вершин и ребер соответственно п. а г Показана верхняя половина матрицы, т.к. матрица весов неориентированного графа симметрична относительно главной диагонали. д
Матрица смежности для графа G. 012345678901111-12-1-1113-1-1-1114-1115- 1-11-1116-1-1-117-1118-1-1-119-1-1-1-1 Задача 2 Найти диаметр DG, радиус RG, количество центров ZG для графа G указать вершины, являющиеся центрами графа G. DG2 RG2 ZG10 Все вершины графа GV,X являются центрами. Задача 3 Перенумеровать вершины графа G, используя алгоритмы а поиска в глубину б поиска в ширину.
Исходная вершина а б Задача 4 Используя алгоритм Прима найти остов минимального веса графа G. выписать код укладки на плоскости найденного дерева, приняв за корневую вершину . Вес найденного дерева – 14. Код укладки дерева 00001101. Задача 5 Используя алгоритм Дейкстра найти дерво кратчайших путей из вершины графа G. Вес найденного пути – 8. Задача 6 Используя алгоритм
Форда – Фалкерсона, найти максимальный поток во взвешенной двуполюсной ориентированной сети G w. Указать разрез минимального веса. Последовательность насыщения сети насыщенные ребра отмечены кружечками 1-й шаг 2-й шаг 3-й шаг 4-й шаг 5-й шаг 6-й шаг 7-й шаг Окончательно имеем Как видно из рисунка, ребра 6,9,7,9,3,9, питающие вершину , насыщенны, а оставшееся ребро 8,9, питающееся от вершины 8, не может получить большее значение весовой функции, так как насыщенны
все ребра, питающие вершину 8. Другими словами – если отбросить все насыщенные ребра, то вершина недостижима, что является признаком максимального потока в сети. Максимальный поток в сети равен 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 матрицы весов. Используя алгоритм метода ветвей и границ, найти Гамильтонов контур минимального максимального веса.
Задачу на максимальное значение Гамильтонова контура свести к задаче на минимальное значение, рассмотрев матрицу с элементами ,где . Выполнить рисунок. Исходная таблица. x1x2x3x4x5x6x137211x280643x360572x46135x 533345×68622 Таблица Е x1x2x3x4x5x6x1150172x280141x3600700x4180 15x50100001003x664000022 Дробим по переходу x2-x3 Таблица 14014 x1x2x4x5x6x11017x36706x4101x50101100x0000 Таблица 14115 x1x2x3x4x5x6x115017x273031x3600700x41801 x5010005100x6640000
Продолжаем по . Дробим по переходу x3-x6 Таблица 14014 x1x2x4x5x1101x4101x501011x660000Таблица 14620 x1x2x4x5x6x11017x30116x4101x50001107x0000 Продолжаем по . Дробим по переходу x4-x5 Таблица 14014 x1x2x4x1101x501011x6600 Таблица 14115 x1x2x4x5x1101x4001x501011x660000 Продолжаем по . Дробим по переходу x5-x1 Таблица 14115 x2x4x111x600
Таблица 14620 x1x2x4x1101x501x60006 Окончательно имеем Гамильтонов контур 2,3,6,4,5,1,2. Прадерево разбиений Задача 10 Задача о назначениях Дан полный двудольный граф Knn с вершинами первой доли x1, x2 xn.и вершинами другой доли y1, y2 yn Вес ребра xi,yj задается элементами vij матрицы весов.
Используя венгерский алгоритм, найти совершенное паросочетание минимального максимального веса. Выполнить рисунок. Матрица весов двудольного графа K55 y1y2y3y4y5x120000x207986x301322x408764x07683 Первый этап – получение нулей не нужен, т. к. нули уже есть во всех строк и столбцах. Второй этап – нахождение полного паросочетания. y1y2y3y4y5x120000x207986x301322x408764x5 07683
Третий этап – нахождение максимального паросочетания. y1y2y3y4y5x120000Xx207986Xx301322x408764 x507683XX Четвертый этап – нахождение минимальной опоры. y1y2y3y4y5x120000x2079865x3013221x408764 2×50768334 Пятый этап – возможная перестановка некоторых нулей. y1y2y3y4y5x130000x2068755x3002111x407653 2×50657234 Решение с ненулевым значением. Переход ко второму этапу. Полное паросочетание y1y2y3y4y5x130000x206875x300211x407653x5 06572
Максимальное паросочетание y1y2y3y4y5x130000Xx206875Xx300211x407653 x506572XX Минимальная опора y1y2y3y4y5x1300006x2068757x3002111x40765 32×506572345 Перестановка нулей y1y2y3y4y5x1300006x2068757x3002111x40765 32×506572345 Полное паросочетание y1y2y3y4y5x1300006x2068757x3002111x40765 32×506572345 Максимальное паросочетание y1y2y3y4y5x130000Xx206875x300211Xx407653
Xx506572XXX Минимальная опора y1y2y3y4y5x130000x2068751x300211x407653x 50657223 Перестановка нулей y1y2y3y4y5x150000x2046531x320211x427653x 50435023 Полное паросочетание y1y2y3y4y5x150000x204653x320211x427653x5 04350 Максимальное паросочетание y1y2y3y4y5x150000Xx204653Xx320211Xx42765 3x504350X Минимальная опора y1y2y3y4y5x150000x204653x320211x4276531x 504350
Перестановка нулей y1y2y3y4y5x150000x204653x320211x4054311x 504350 Полное паросочетание y1y2y3y4y5x150000x204653x320211x4054311x 504350 Максимальное паросочетание y1y2y3y4y5x150000Xx204653Xx320211Xx40543 1x504350X Минимальная опора y1y2y3y4y5x150000x2046533x320211x4054311 x5043502 Перестановка нулей y1y2y3y4y5x160000x2035423x330211x4043201 x5143502
Полное паросочетание y1y2y3y4y5x160000x2035423x330211x4043201 x5143502 Максимальное паросочетание y1y2y3y4y5x160000Xx203542Xx330211Xx40432 0x514350X Минимальная опора y1y2y3y4y5x160000x2035424x330211x4043201 x514350523 В результате имеем y1y2y3y4y5x160000x2013224x330211x4021001 x514350523Исходный граф Полученный граф Вес найденного совершенного паросочетания 12.
Задача 11 Решить задачу 10, используя алгоритм ветвей и границ отождествив вершины xi и yj. Таблица Е исходная. Строки – xi , столбцы – yj. 0 Дробим по переходу x2 – y1 Таблица Е21 088 Таблица 066 Продолжаем по Дробим по переходу x4 – y1 Таблица Е41 6410 Таблица 6410 Продолжаем по Е21 Дробим по переходу x5 – y5
Таблица Е21Е55 8210 234100010030121421012Таблица Е 8311 Продолжаем по Е21Е55 Дробим по переходу x3 – y2 Таблица Е21Е55Е32 10010 34101004101 Далее решение очевидно x1 – y3 и x4 – y4. Это не увеличит оценку. В итоге имеем совершенное паросочетание с минимальным весом Прадерево разбиений