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

Г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, используя алгоритмы:

а) "поиска в глубину";

б) "поиска в ширину".

Исходная вершина - a.

а)

б)

Задача 4 Используя алгоритм Прима найти остов минимального веса графа G. выписать код укладки на плоскости найденного дерева, приняв за корневую вершину a.

Вес найденного дерева - 14.

Код укладки дерева: 000011000001111111.

Задача 5 Используя алгоритм Дейкстра найти дерво кратчайших путей из вершины a графа G.

Вес найденного пути - 8.

Задача 6 Используя алгоритм Форда - Фалкерсона, найти максимальный поток во взвешенной двуполюсной ориентированной сети {Gор , a , w}. Указать разрез минимального веса.

Последовательность насыщения сети (насыщенные ребра отмечены кружечками):