Дискретная математика: "Графы" - (курсовая)
Дискретная математика: "Графы" - (курсовая)
Дата добавления: март 2006г.
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
Ґ
