Курсовая: Дискретная математика: "Графы" - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

Дискретная математика: "Графы"

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Архив Zip, 274 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

Узнайте стоимость написания уникальной работы

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, используя алгоритмы : а ) "поиска в глубину "; б ) "поиска в ширину ". Исходная вершина - . а ) б ) Задача 4 Используя алгоритм Прима найти остов минимального веса графа G. выписать код укладки на плоскости найденного дерева , приняв за корневую вершину . Вес найденного дерева - 14. Код укладки дерева : 000011000001111111. Задача 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 (Задача о коммивояжере ) Дан полный ориентированный симметрический граф с вершинами x 1 , x 2 ,...x n .Вес дуги x i x j задан элементами V ij матрицы весов . Используя алгоритм метода ветвей и границ , найти Гамильтонов контур минимального (максимального ) веса . Задачу на максимальное значение Гамильтонова контура свести к задаче на минимальное значение , рассмотрев матрицу с эл ементами ,где . Выполнить рисунок. Исходная таблица. x 1 x 2 x 3 x 4 x 5 x 6 x 1 3 7 2 11 x 2 8 0 6 4 3 x 3 6 0 5 7 2 x 4 6 13 5 x 5 3 3 3 4 5 x 6 8 6 2 2 Таблица Е 14 x 1 x 2 x 3 x 4 x 5 x 6 x 1 1 5 0 1 7 2 x 2 8 0 1 4 1 x 3 6 0 0 7 0 0 x 4 1 8 0 1 5 x 5 0 1 0 0 0 0 1 0 0 3 x 6 6 4 0 0 0 0 2 2 Дробим по переходу x 2 -x 3 : Таблица 23 =14+0=14 x 1 x 2 x 4 x 5 x 6 x 1 1 0 1 7 x 3 6 7 0 6 x 4 1 0 1 x 5 0 1 0 1 1 0 0 x 6 6 4 0 0 0 0 Таблица 23 =14+1=15 x 1 x 2 x 3 x 4 x 5 x 6 x 1 1 5 0 1 7 x 2 7 3 0 3 1 x 3 6 0 0 7 0 0 x 4 1 8 0 1 x 5 0 1 0 0 0 5 1 0 0 x 6 6 4 0 0 0 0 Продолжаем по 23. Дробим по переходу x 3 -x 6 : Таблица 23E36 =14+0=14 x 1 x 2 x 4 x 5 x 1 1 0 1 x 4 1 0 1 x 5 0 1 0 1 1 x 6 6 0 0 0 0 Таблица 23 36 =14+6=20 x 1 x 2 x 4 x 5 x 6 x 1 1 0 1 7 x 3 0 1 1 6 x 4 1 0 1 x 5 0 0 0 1 1 0 7 x 6 6 4 0 0 0 0 Продолжаем по 23 36. Дробим п о переходу x 4 -x 5 : Таблица 23E36 45 =14+0=14 x 1 x 2 x 4 x 1 1 0 1 x 5 0 1 0 1 1 x 6 6 0 0 Таблица 23 36 45 =14+1=15 x 1 x 2 x 4 x 5 x 1 1 0 1 x 4 0 0 1 x 5 0 1 0 1 1 x 6 6 0 0 0 0 Продолжаем по 23 36 45. Дробим по переходу x 5 -x 1 : Таблица 23 36 45 51 =14+1=15 x 2 x 4 x 1 1 1 x 6 0 0 Таблица 23 36 45 51 =14+6=20 x 1 x 2 x 4 x 1 1 0 1 x 5 0 1 x 6 0 0 0 6 Окончательно имеем Гамильтонов контур : 2,3,6,4,5,1,2. Прадерево разбиений : Задача 10 (Задача о назначениях ) Дан полный двудольный граф K nn с вершинами первой доли x 1 , x 2 ,...x n .и вершинами другой доли y 1 , y 2 ,...y n ..Вес ребра xi , y j задается элементами v ij матрицы весов . Используя венгерский алгоритм , найти совершенное паросочетание минимального (максимального веса ). Выполнить рисунок. Матрица весов двудольного графа K 55 : y 1 y 2 y 3 y 4 y 5 x 1 2 0 0 0 0 x 2 0 7 9 8 6 x 3 0 1 3 2 2 x 4 0 8 7 6 4 x 5 0 7 6 8 3 Первый этап - получение нулей не нужен , т . к . нули уже есть во всех строк и столбцах. Второй этап - нахождение полного паросочетания. y 1 y 2 y 3 y 4 y 5 x 1 2 0 0 0 0 x 2 0 7 9 8 6 x 3 0 1 3 2 2 x 4 0 8 7 6 4 x 5 0 7 6 8 3 Третий этап - нахождение максимального паросочетания. y 1 y 2 y 3 y 4 y 5 x 1 2 0 0 0 0 X x 2 0 7 9 8 6 X x 3 0 1 3 2 2 x 4 0 8 7 6 4 x 5 0 7 6 8 3 X X Четвертый этап - нахождение минимальной опоры. y 1 y 2 y 3 y 4 y 5 x 1 2 0 0 0 0 x 2 0 7 9 8 6 5 x 3 0 1 3 2 2 1 x 4 0 8 7 6 4 2 x 5 0 7 6 8 3 3 4 Пятый этап - возможная перестановка некоторых нулей. y 1 y 2 y 3 y 4 y 5 x 1 3 0 0 0 0 x 2 0 6 8 7 5 5 x 3 0 0 2 1 1 1 x 4 0 7 6 5 3 2 x 5 0 6 5 7 2 3 4 Р ешение с ненулевым значением . Переход ко второму этапу. Полное паросочетание : y 1 y 2 y 3 y 4 y 5 x 1 3 0 0 0 0 x 2 0 6 8 7 5 x 3 0 0 2 1 1 x 4 0 7 6 5 3 x 5 0 6 5 7 2 Максимальное паросочетание : y 1 y 2 y 3 y 4 y 5 x 1 3 0 0 0 0 X x 2 0 6 8 7 5 X x 3 0 0 2 1 1 x 4 0 7 6 5 3 x 5 0 6 5 7 2 X X Минимальная опора : y 1 y 2 y 3 y 4 y 5 x 1 3 0 0 0 0 6 x 2 0 6 8 7 5 7 x 3 0 0 2 1 1 1 x 4 0 7 6 5 3 2 x 5 0 6 5 7 2 3 4 5 Перестановка нулей : y 1 y 2 y 3 y 4 y 5 x 1 3 0 0 0 0 6 x 2 0 6 8 7 5 7 x 3 0 0 2 1 1 1 x 4 0 7 6 5 3 2 x 5 0 6 5 7 2 3 4 5 Полное паросочетание : y 1 y 2 y 3 y 4 y 5 x 1 3 0 0 0 0 6 x 2 0 6 8 7 5 7 x 3 0 0 2 1 1 1 x 4 0 7 6 5 3 2 x 5 0 6 5 7 2 3 4 5 Максимальное паросочетание : y 1 y 2 y 3 y 4 y 5 x 1 3 0 0 0 0 X x 2 0 6 8 7 5 x 3 0 0 2 1 1 X x 4 0 7 6 5 3 X x 5 0 6 5 7 2 X X X Минимальная опора : y 1 y 2 y 3 y 4 y 5 x 1 3 0 0 0 0 x 2 0 6 8 7 5 1 x 3 0 0 2 1 1 x 4 0 7 6 5 3 x 5 0 6 5 7 2 2 3 Перестановка нулей : y 1 y 2 y 3 y 4 y 5 x 1 5 0 0 0 0 x 2 0 4 6 5 3 1 x 3 2 0 2 1 1 x 4 2 7 6 5 3 x 5 0 4 3 5 0 2 3 Полное паросочетание : y 1 y 2 y 3 y 4 y 5 x 1 5 0 0 0 0 x 2 0 4 6 5 3 x 3 2 0 2 1 1 x 4 2 7 6 5 3 x 5 0 4 3 5 0 Максимальное паросочетание : y 1 y 2 y 3 y 4 y 5 x 1 5 0 0 0 0 X x 2 0 4 6 5 3 X x 3 2 0 2 1 1 X x 4 2 7 6 5 3 x 5 0 4 3 5 0 X X X X X Минимальная опора : y 1 y 2 y 3 y 4 y 5 x 1 5 0 0 0 0 x 2 0 4 6 5 3 x 3 2 0 2 1 1 x 4 2 7 6 5 3 1 x 5 0 4 3 5 0 Перестановка нулей : y 1 y 2 y 3 y 4 y 5 x 1 5 0 0 0 0 x 2 0 4 6 5 3 x 3 2 0 2 1 1 x 4 0 5 4 3 1 1 x 5 0 4 3 5 0 Полное паросочетание : y 1 y 2 y 3 y 4 y 5 x 1 5 0 0 0 0 x 2 0 4 6 5 3 x 3 2 0 2 1 1 x 4 0 5 4 3 1 1 x 5 0 4 3 5 0 Максимальное паросочетание : y 1 y 2 y 3 y 4 y 5 x 1 5 0 0 0 0 X x 2 0 4 6 5 3 X x 3 2 0 2 1 1 X x 4 0 5 4 3 1 x 5 0 4 3 5 0 X X X X X Минимальная опора : y 1 y 2 y 3 y 4 y 5 x 1 5 0 0 0 0 x 2 0 4 6 5 3 3 x 3 2 0 2 1 1 x 4 0 5 4 3 1 1 x 5 0 4 3 5 0 2 Перестановка нулей : y 1 y 2 y 3 y 4 y 5 x 1 6 0 0 0 0 x 2 0 3 5 4 2 3 x 3 3 0 2 1 1 x 4 0 4 3 2 0 1 x 5 1 4 3 5 0 2 Полное паросочетание : y 1 y 2 y 3 y 4 y 5 x 1 6 0 0 0 0 x 2 0 3 5 4 2 3 x 3 3 0 2 1 1 x 4 0 4 3 2 0 1 x 5 1 4 3 5 0 2 Максимальное паросочетание : y 1 y 2 y 3 y 4 y 5 x 1 6 0 0 0 0 X x 2 0 3 5 4 2 X x 3 3 0 2 1 1 X x 4 0 4 3 2 0 x 5 1 4 3 5 0 X X X X X Минимальная опора : y 1 y 2 y 3 y 4 y 5 x 1 6 0 0 0 0 x 2 0 3 5 4 2 4 x 3 3 0 2 1 1 x 4 0 4 3 2 0 1 x 5 1 4 3 5 0 5 2 3 В результате имеем : y 1 y 2 y 3 y 4 y 5 x 1 6 0 0 0 0 x 2 0 1 3 2 2 4 x 3 3 0 2 1 1 x 4 0 2 1 0 0 1 x 5 1 4 3 5 0 5 2 3 Исходный граф Полученный граф : Вес найденного совершенного паросочетания = 12. Задача 11 Решить задачу 10, используя алгоритм ветвей и границ (отождествив вершины x i и y j ). Таблица Е (исходная ). Строки - x i , столбцы - y j . =0 1 2 3 4 5 1 2 0 1 0 3 0 2 0 2 2 0 6 7 9 8 6 3 0 1 1 3 2 2 4 0 4 8 7 6 4 5 0 3 7 6 8 3 Дробим по переходу x 2 - y 1 : Таблица Е 21 =0+8=8 2 3 4 5 1 0 0 0 2 0 1 0 0 3 0 1 2 1 1 1 4 4 3 2 0 2 4 5 4 3 5 0 3 3 Таблица 21 =0+6=6 1 2 3 4 5 1 2 0 1 0 3 0 2 0 0 2 1 3 2 0 1 6 3 0 1 1 3 2 2 4 0 4 8 7 6 4 5 0 3 7 6 8 3 Продолжаем по 21: Дробим по переходу x 4 - y 1 : Таблица 21Е 41 =6+4=10 2 3 4 5 1 0 0 0 2 0 1 0 0 2 1 3 2 0 1 3 0 1 2 1 1 1 5 4 3 5 0 3 3 Таблица 21 41 =6+4=10 1 2 3 4 5 1 2 0 1 0 3 0 2 0 0 2 1 3 2 0 1 3 0 1 1 3 2 2 4 4 3 2 0 2 4 5 0 3 7 6 8 3 Продолжаем по Е 21: Дробим по переходу x 5 - y 5 : Таблица Е 21Е 55 =8+2=10 2 3 4 1 0 0 0 1 0 0 3 0 1 2 1 4 2 1 0 1 2 Таблица Е 21 55 =8+3=11 2 3 4 5 1 0 0 0 2 0 1 0 0 3 0 1 2 1 1 4 4 3 2 0 2 5 1 0 1 2 3 Про должаем по Е 21Е 55: Дробим по переходу x 3 - y 2 : Таблица Е 21Е 55Е 32 =10+0=10 3 4 1 0 1 0 0 4 1 0 1 Далее решение очевидно : x 1 - y 3 и x 4 - y 4 . Это не увеличит оценку. В итоге и меем совершенное паросочетание с минимальным весом : Прадерево разбиений :
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Самый безопасный город Украины в 2014 году - Чернобыль.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, курсовая по математике "Дискретная математика: "Графы"", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru