ДЗ

Дан ориентированный граф $N=9$

1.1 Описание графа

Множества вершин и рёбер

• $G=(V,E)$
• $V=\{1,2,3,4,5\}$
• $E=\{(1,1),(2,1),(5,1),(3,3),(4,4),(4,2),(3,5)\}$

1.2 Степени вершин

Таблица степеней

$v$	${\mathrm{deg}}^{-}(v)$	${\mathrm{deg}}^{+}(v)$	$\mathrm{deg}(v)$
1	3	1	4
2	1	1	2
3	1	2	3
4	1	2	3
5	1	1	2

1.3 Матрицы орграфа

Матрица смежности

из \ в	1	2	3	4	5
1	1	0	0	0	0
2	1	0	0	0	0
3	0	0	1	0	1
4	0	1	0	1	0
5	1	0	0	0	0

Матрица инцидентности

v \ e	11	21	35	33	42	44	51
1	0	-1	0	0	0	0	-1
2	0	1	0	0	-1	0	0
3	0	0	1	0	0	0	0
4	0	0	0	0	1	0	0
5	0	0	-1	0	0	0	1

1.4 Список смежности

• 1: $\{1\}$
• 2: $\{1\}$
• 3: $\{3,5\}$
• 4: $\{2,4\}$
• 5: $\{1\}$

1.5 Ассоциированный неориентированный граф

Матрица смежности

	1	2	3	4	5
1	1	1	0	0	1
2	1	0	0	1	0
3	0	0	1	0	1
4	0	1	0	1	0
5	1	0	1	0	0

Матрица инцидентности

v \ e	11	12	15	33	35	24	44
1	2	1	1	0	0	0	0
2	0	1	0	0	0	1	0
3	0	0	0	2	1	0	0
4	0	0	0	0	0	1	2
5	0	0	1	0	1	0	0

1.6 Матрица достижимости и компоненты

Матрица достижимости

из \ в	1	2	3	4	5
1	1	0	0	0	0
2	1	1	0	0	0
3	1	0	1	0	1
4	1	1	0	1	0
5	1	0	0	0	1