Типовой расчет графов

Типовой расчет графов Данная работа является типовым расчетом N2 по курсу Дискретная математика по теме Графы, предлагаемая студентам МГТУ им. Баумана. Вариант N 17. Сразу хочу сказать для своих коллег Граждане Имейте терпение и совесть, поймите, что я это делаю для Вас с целью помочь разобраться в этой теме, а не просто свалить очередной предмет. Мне известно, как непросто сейчас с литературой, и с информацией вообще.Поиски неизвестно какой книги занимают много времени, поэтому в конце я привел небольшой список литературы, составленный мной из различных источников в дополнение к списку, написанному ранее в работе по графам о постановке лаб. работ по алгоритму Прима и Дейкстра, которая, я надеюсь, есть в сети. Содержание работы Типовой расчет состоит из 11-ти задач 1, 2 и 3 задачи относятся к способам задания графов и опредению их характеристик, таких как диаметр, радиус и т.д. 4 и 5 задачи соответственно на алгоритм Прима и Дейкстра.

Здесь я снова отсылаю Вас к более ранней работе см. выше. 6-я задача о поиске максим ального потока в сети метод Форда-Фалкерсона. 7-я задача - Эйлерова цепь задача о почтальоне. 8-я задача - Гамильтонова цепь. 9-я задача - метод ветвей и границ применительно к задаче о коммивояжере. 10-я задача - задача о назначениях венгерский алгоритм. 11-я задача - тоже методом ветвей и границ.

GорV,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 533345x68622 Таблица Е x1x2x3x4x5x6x1150172x280141x3600700x4180 15x50100001003x664000022 Дробим по переходу x2-x3 Таблица 14014 x1x2x4x5x6x11017x36706x4101x50101100x664 0000 Таблица 14115 x1x2x3x4x5x6x115017x273031x3600700x41801 x5010005100x6640000 Продолжаем по . Дробим по переходу x3-x6 Таблица 14014 x1x2x4x5x1101x4101x501011x660000Таблица 14620 x1x2x4x5x6x11017x30116x4101x50001107x664 0000Продолжаем по . Дробим по переходу 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 y1y2y3y4y5x120000x207986x301322x408764x5 07683 Первый этап - получение нулей не нужен, т. к. нули уже есть во всех строк и столбцах.

Второй этап - нахождение полного паросочетания. y1y2y3y4y5x120000x207986x301322x408764x5 07683 Третий этап - нахождение максимального паросочетания. y1y2y3y4y5x120000Xx207986Xx301322x408764 x507683XX Четвертый этап - нахождение минимальной опоры. y1y2y3y4y5x120000x2079865x3013221x408764 2x50768334 Пятый этап - возможная перестановка некоторых нулей. y1y2y3y4y5x130000x2068755x3002111x407653 2x50657234 Решение с ненулевым значением.

Переход ко второму этапу.

Полное паросочетание y1y2y3y4y5x130000x206875x300211x407653x5 06572 Максимальное паросочетание y1y2y3y4y5x130000Xx206875Xx300211x407653 x506572XX Минимальная опора y1y2y3y4y5x1300006x2068757x3002111x40765 32x506572345 Перестановка нулей y1y2y3y4y5x1300006x2068757x3002111x40765 32x506572345 Полное паросочетание y1y2y3y4y5x1300006x2068757x3002111x40765 32x506572345 Максимальное паросочетание 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. Это не увеличит оценку.

В итоге имеем совершенное паросочетание с минимальным весом Прадерево разбиений Литература 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 с.