Типовой расчет графов - (реферат)
Типовой расчет графов - (реферат)
Дата добавления: март 2006г.
Типовой расчет графов
Данная работа является типовым расчетом 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
