Типовой расчет графов
Информация - Математика и статистика
Другие материалы по предмету Математика и статистика
?лерова цепь: 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 матрицы весов. Используя алгоритм метода ветвей и границ, найти Гамильтонов контур минимального (максимального) веса. Задачу на максимальное значение Гамильтонова контура свести к задаче на минимальное значение, рассмотрев матрицу с элементами ,где . Выполнить рисунок.
Исходная таблица.
x1x2x3x4x5x6x137211x280643x360572x46135x533345x68622
Таблица Е14
x1x2x3x4x5x6x1150172x280141x3600700x418015x50100001003x664000022
Дробим по переходу x2-x3:
Таблица 23=14+0=14
x1x2x4x5x6x11017x36706x4101x50101100x6640000
Таблица 23=14+1=15
x1x2x3x4x5x6x115017x273031x3600700x41801x5010005100x6640000
Продолжаем по 23. Дробим по переходу x3-x6:
Таблица 23E36=14+0=14
x1x2x4x5x1101x4101x501011x660000Таблица 2336=14+6=20
x1x2x4x5x6x11017x30116x4101x50001107x6640000Продолжаем по 2336. Дробим по переходу x4-x5:
Таблица 23E3645=14+0=14
x1x2x4x1101x501011x6600
Таблица 233645=14+1=15
x1x2x4x5x1101x4001x501011x660000
Продолжаем по 233645. Дробим по переходу x5-x1:
Таблица 23364551=14+1=15
x2x4x111x600
Таблица 23364551=14+6=20
x1x2x4x1101x501x60006
Окончательно имеем Гамильтонов контур: 2,3,6,4,5,1,2.
Прадерево разбиений:
Задача 10(Задача о назначениях) Дан полный двудольный граф Knn с вершинами первой доли x1, x2,...xn.и вершинами другой доли y1, y2,...yn..Вес ребра {xi,yj} задается элементами vij матрицы весов. Используя венгерский алгоритм, найти совершенное паросочетание минимального (максимального веса). Выполнить рисунок.
Матрица весов двудольного графа K55 :
y1y2y3y4y5x120000x207986x301322x408764x507683
Первый этап - получение нулей не нужен, т. к. нули уже есть во всех строк и столбцах.
Второй этап - нахождение полного паросочетания.
y1y2y3y4y5x120000x207986x301322x408764x507683
Третий этап - нахождение максимального паросочетания.
y1y2y3y4y5x120000Xx207986Xx301322x408764x507683XX
Четвертый этап - нахождение минимальной опоры.
y1y2y3y4y5x120000x2079865x3013221x4087642x50768334
Пятый этап - возможная перестановка некоторых нулей.
y1y2y3y4y5x130000x2068755x3002111x4076532x50657234Решение с ненулевым значением. Переход ко второму этапу.
Полное паросочетание:
y1y2y3y4y5x130000x206875x300211x407653x506572Максимальное паросочетание:
y1y2y3y4y5x130000Xx206875Xx300211x407653x506572XX
Минимальная опора:
y1y2y3y4y5x1300006x2068757x3002111x4076532x506572345
Перестановка нулей:
y1y2y3y4y5x1300006x2068757x3002111x4076532x506572345
Полное паросочетание:
y1y2y3y4y5x1300006x2068757x3002111x4076532x506572345
Максимальное паросочетание:
y1y2y3y4y5x130000Xx206875x300211Xx407653Xx506572XXX
Минимальная опора:
y1y2y3y4y5x130000x2068751x300211x407653x50657223
Перестановка нулей:
y1y2y3y4y5x150000x2046531x320211x427653x50435023
Полное паросочетание:
y1y2y3y4y5x150000x204653x320211x427653x504350Максимальное паросочетание:
y1y2y3y4y5x150000Xx204653Xx320211Xx427653x504350XXXXX
Минимальная опора:
y1y2y3y4y5x150000x204653x320211x4276531x504350
Перестановка нулей:
y1y2y3y4y5x150000x204653x320211x4054311x504350
Полное паросочетание:
y1y2y3y4y5x150000x204653x320211x4054311x504350
Максимальное паросочетание:
y1y2y3y4y5x150000Xx204653Xx320211Xx405431x504350XXXXX
Минимальная опора:
y1y2y3y4y5x150000x2046533x320211x4054311x5043502
Перестановка нулей:
y1y2y3y4y5x160000x2035423x330211x4043201x5143502
Полное паросочетание:
y1y2y3y4y5x160000x2035423x330211x4043201x5143502
Максимальное паросочетание:
y1y2y3y4y5x160000Xx203542Xx330211Xx404320x514350XXXXX
Минимальная опора:
y1y2y3y4y5x160000x2035424x330211x4043201x514350523
В результате имеем:
y1y2y3y4y5x160000x2013224x330211x4021001x514350523Исходный граф
Полученный граф:
Вес найденного совершенного паросочетания = 12.
Задача 11Решить задачу 10, используя алгоритм ветвей и границ (отождествив вершины xi и yj).