Задание 2
Матрица длин дуг
|
v0 |
v1 |
v2 |
v3 |
v4 |
v5 |
v0 |
∞ |
3 |
5 |
∞ |
8 |
3 |
v1 |
3 |
∞ |
2 |
6 |
7 |
∞ |
v2 |
5 |
2 |
∞ |
∞ |
4 |
∞ |
v3 |
∞ |
6 |
∞ |
∞ |
5 |
∞ |
v4 |
8 |
7 |
4 |
5 |
∞ |
∞ |
v5 |
3 |
∞ |
∞ |
∞ |
∞ |
∞ |
Неориентированный граф G=(V,X). V={v0,v1,v2,v3,v4,v5}, X={x0,x1,x2,x3,x4,x5,x6,x7,x8}. x0={v0,v1}, x1={v0,v5}, x2={v1,v2}, x3={v1,v4}, x4={v1,v3}, x5={v0,v2}, x6={v0,v4}, x7={v2,v4}, x8={v3,v4}.
v5 – висячая вершина.
(v0)=4, (v1)=4, (v2)=3, (v3)=2, (v4)=4, (v5)=1.
Матрица смежности
|
v0 |
v1 |
v2 |
v3 |
v4 |
v5 |
v0 |
0 |
1 |
1 |
0 |
1 |
1 |
v1 |
1 |
0 |
1 |
1 |
1 |
0 |
v2 |
1 |
1 |
0 |
0 |
1 |
0 |
v3 |
0 |
1 |
0 |
0 |
1 |
0 |
v4 |
1 |
1 |
1 |
1 |
0 |
0 |
v5 |
1 |
0 |
0 |
0 |
0 |
0 |
Матрица инцидентности
|
x0 |
x1 |
x2 |
x3 |
х4 |
х5 |
х6 |
х7 |
x8 |
v0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
v1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
v2 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
v3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
v4 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
v5 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Матрица связности:
|
v0 |
v1 |
v2 |
v3 |
v4 |
v5 |
v0 |
1 |
1 |
1 |
1 |
1 |
1 |
v1 |
1 |
1 |
1 |
1 |
1 |
1 |
v2 |
1 |
1 |
1 |
1 |
1 |
1 |
v3 |
1 |
1 |
1 |
1 |
1 |
1 |
v4 |
1 |
1 |
1 |
1 |
1 |
1 |
v5 |
1 |
1 |
1 |
1 |
1 |
1 |
Матрица достижимости:
|
v0 |
v1 |
v2 |
v3 |
v4 |
v5 |
v0 |
1 |
1 |
1 |
1 |
1 |
1 |
v1 |
1 |
1 |
1 |
1 |
1 |
1 |
v2 |
1 |
1 |
1 |
1 |
1 |
1 |
v3 |
1 |
1 |
1 |
1 |
1 |
1 |
v4 |
1 |
1 |
1 |
1 |
1 |
1 |
v5 |
1 |
1 |
1 |
1 |
1 |
1 |
Простой цикл: v0х0v1х2v2х5v0
Цикл: v4x6v0x5v2x7v4x3v1x4v3х8v4
Простая цепь: v2х5v0х1v5
Цепь: v0х0v1х2v2х7v4х3v1х4v3
Рассчитаем остовное дерево графа:
Рассчитаем минимальное остовное дерево графа:
