МОТС 30 вариант Первая часть

^1. Элементы теории графов

Связный ориентированный граф задан множеством и отображением

K=3 L=5 N=7

Аналитический способ

Графический способ задания графа:

- ориентированный граф:

-неориентированный граф:

Матричный способ задания

- ориентированный граф:

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

			0	1	0	1	0	1	0
			1	0	1	0	0	0	1
			0	1	0	0	0	0	0
			1	0	0	0	0	0	0
			0	1	0	0	0	0	0
			1	0	1	0	0	0	0
			0	1	0	1	0	0	0

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

			1	1	1	-1	0	0	0	-1	0	0	-1	0	0
			-1	0	0	1	1	1	-1	0	-1	0	0	0	-1
			0	0	0	0	0	-1	1	0	0	-1	0	0	0
			0	0	-1	0	0	0	0	1	0	0	0	-1	0
			0	0	0	0	0	0	0	0	1	0	0	0	0
			0	-1	0	0	0	0	0	0	0	1	1	0	0
			0	0	0	0	-1	0	0	0	0	0	0	1	1

- неориентированный граф:

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

			0	2	0	2	0	2	0
			2	0	2	0	1	0	2
			0	2	0	0	0	1	0
			2	0	0	0	0	0	1
			0	1	0	0	0	0	0
			2	0	1	0	0	0	0
			0	2	0	1	0	0	0

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

			1	1	1	1	0	0	0	1	0	0	1	0	0
			1	0	0	1	1	1	1	0	1	0	0	0	1
			0	0	0	0	0	1	1	0	0	1	0	0	0
			0	0	1	0	0	0	0	1	0	0	0	1	0
			0	0	0	0	0	0	0	0	1	0	0	0	0
			0	1	0	0	0	0	0	0	0	1	1	0	0
			0	0	0	0	1	0	0	0	0	0	0	1	1

Установить центры и периферийные вершины графов, найти радиусы и диаметры графов.

-Для ориентированного графа:

матрица отклонений:

			0	1	2	1	-	1	2
			1	0	1	2	-	2	1
			2	1	0	3	-	3	2
			1	2	3	0	-	2	3
			2	1	2	3	0	3	2
			1	2	1	2	-	0	3
			2	1	2	1	-	3	0

вектор удаленностей:

В данном графе вершины x_1, x₂ являются центрами графа, вершины x₃ x₄ x₅ x₆ x₇ являются периферийными вершинами, соответственно радиус графа ρ(G) = 2; диаметр графа D(G) = 3

Для неориентированного графа:

матрица отклонений:

			0	1	2	1	2	1	2
			1	0	1	2	1	2	1
			2	1	0	3	2	1	2
			1	2	3	0	3	2	1
			2	1	2	3	0	3	2
			1	2	1	2	3	0	3
			2	1	2	1	2	3	0

вектор удаленностей:

В данном графе вершины x_1, x₂ являются центрами графа, вершины x₃ x₄ x₅ x₆ x₇ являются периферийными вершинами, соответственно радиус графа ρ(G) = 2; диаметр графа D(G) = 3