Математические основы теории систем (стр. 1 из 5)

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

Связный ориентированный граф G (Х, Г) задан множеством вершин X={x₁, x₂,…,x_n} и отображением Гx_i={x_|I±k|,x_|I±l|},i =1, 2,…,n. Здесь i- текущий номер вершины, n- количество вершин графа. Значение индексов n, k и l возьмем из табл.1 в соответствии с номером варианта. Индексы k и l формируют значения индексов a,b, g… переменной x в отображении Гx_i = {x_a,x_b,x_g,…}. Если значения индексов a, b,g… переменной x не соответствуют ни одному из номеров вершин графа, то эта переменная не учитывается во множестве Гx_i.

Выполнить следующие действия:

а) определить исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами;

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

в) выделить в ориентированном графе два подграфа. Найти объединение, пересечение и разность подграфов;

г) описать систему уравнений, соответствующую сигнальному графу, считая, что передача между вершинами x_i и x_j

i*jпри i ³ j;

Kij =

1/ (p+1) при i<j .

Найти передачу между вершинами x₁и x_n, используя правило Мезона. Построить структуру кибернетической системы, определяемой топологией графа;

Таблица 1

№ варианта	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
N	5	5	5	5	5	5	5	5	5	6	6	6	6	6	6
K	2	3	4	1	1	1	3	5	2	4	2	3	4	5	6
L	1	1	1	2	3	4	2	1	3	3	1	1	1	1	1
№ варианта	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30
N	6	6	6	6	6	6	6	6	6	7	7	7	7	7	7
K	1	1	1	1	3	2	5	5	2	3	4	5	6	5	3
L	2	3	4	5	2	3	2	3	3	2	3	2	1	3	5

Решение:

Множество вершин

X = {x₁, x₂,x₃, x₄, x₅, x₆}, n = 6 k = 2, l = 1 Гx_i={x_|I±k|,x_|I±l|}.

а) определим исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами:

Определим граф аналитическим способом:

Гx₁ = { x₁, x₃, x₂ };

Гx₂ = { x₄, x₁,x₃ };

Гx₃ = { x₁, x₅, x₂, x₄ };

Гx₄ = { x₂, x₆,x₃, x₅ };

Гx₅ = { x₃, x₄, x₆ };

Гx₆ = {x₄,x₅ }.

Ориентированный граф графическим способом:

Неориентированный граф графическим способом:

Ориентированный граф матричным способом:

R_G- матрица смежности

x1	x2	x3	x4	x5	x6
x1	1*	1	1	0	0	0
x2	1	0	1	1	0	0
x3	1	1	0	1	1	0
x4	0	1	1	0	1	1
x5	0	0	1	1	0	1
x6	0	0	0	1	1	0

A_G- матрица инцидентности

v1	v2	v3	v4	v5	v6	v7	v8	v9	v10	v11	v12	v13	v14	v15	v16	v17	v18	v19
x1	1*	1	-1	0	0	0	0	0	0	0	0	1	-1	0	0	0	0	0	0
x2	0	-1	1	1	-1	0	0	0	0	0	0	0	0	1	-1	0	0	0	0
x3	0	0	0	-1	1	1	-1	0	0	0	0	-1	1	0	0	1	-1	0	0
x4	0	0	0	0	0	-1	1	1	-1	0	0	0	0	-1	1	0	0	1	-1
x5	0	0	0	0	0	0	0	-1	1	1	-1	0	0	0	0	-1	1	0	0
x6	0	0	0	0	0	0	0	0	0	-1	1	0	0	0	0	0	0	-1	1

Неориентированный граф матричным способом:

R_D- матрица смежности

x1	x2	x3	x4	x5	x6
x1	1*	2	2	0	0	0
x2	2	0	2	2	0	0
x3	2	2	0	2	2	0
x4	0	2	2	0	2	2
x5	0	0	2	2	0	2
x6	0	0	0	2	2	0

A_D- матрица инцидентности

v1	v2	v3	v4	v5	v6	v7	v8	v9	v10	v11	v12	v13	v14	v15	v16	v17	v18	v19
x1	1*	1	1	0	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0
x2	0	1	1	1	1	0	0	0	0	0	0	0	0	1	1	0	0	0	0
x3	0	0	0	1	1	1	1	0	0	0	0	1	1	0	0	1	1	0	0
x4	0	0	0	0	0	1	1	1	1	0	0	0	0	1	1	0	0	1	1
x5	0	0	0	0	0	0	0	1	1	1	1	0	0	0	0	1	1	0	0
x6	0	0	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0	1	1

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

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

x1	x2	x3	x4	x5	x6
x1	1	1	1	2	2	3
x2	1	0	1	1	2	2
x3	1	1	0	1	1	2
x4	2	1	1	0	1	1
x5	2	2	1	1	0	1
x6	3	2	2	1	1	0

- вектор отклонения

=>

х₂, х₃, х₄, х₅ - центры графа с наименьшей удаленностью. Радиус ρ (G) = 2.

Периферийными вершинами являются вершины х₁, х₆с наибольшей удаленностью. Диаметр графа D (G) = 3.

в) выделим в ориентированном графе два подграфа и найдем объединение, пересечение и разность подграфов.

Выделяем два подграфа: G₁ и G₂

X₁ - {x₁, x₂}, Г_1х1 = {x₁, x₂}, Г_1х2 = {x₁},

X₂ - {x₁, x₂,x₃}, Г_2х1 = {x₂}, Г_2х2 = {x₃}, Г_2х3 = {x₂}.

Объединение

,