Типовий розрахунок графів
Дана праця є типовим розрахунком N2 з курсу "Дискретна математика "за темою" Графи ", пропонована студентам МГТУ ім. Баумана. (Варіант N 17). p> Відразу хочу сказати для своїх колег: Громадяни! Майте терпіння і совість, зрозумійте, що я це роблю для Вас з метою допомогти розібратися в цій темі, а не просто звалити черговий предмет. Мені відомо, як непросто зараз з літературою, і з інформацією взагалі. Пошуки невідомо якої книги займають багато часу, тому наприкінці я привів невеликий список літератури, складений мною з різних джерел на додаток до списку, написаному раніше в роботі по графах (про постановку лаб. робіт з алгоритмом Прима і Дейкстра), яка, я сподіваюся, є в мережі.
Зміст роботи:
Типовий розрахунок складається з 11-ти завдань:
1, 2 і 3 завдання ставляться до способів завдання графів і опреденію їх характеристик, таких як діаметр, радіус і т.д.
4 та 5 завдання відповідно на алгоритм Прима і Дейкстра. Тут я знову відсилаю Вас до більш ранній роботі (див. вище). p> 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}
У Надалі ребра будуть позначатися номерами в зазначеному порядку починаючи з нуля.
б) Г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
<...
