Задача 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 ₂ }.

 

Объединение ,

 

, , , .

 

G

 

Пересечение

 

, , , .

 

G

 

Разность

 

,

, , .

 

G

 

г) Считая, что передача между вершинами x_i и x_j

 

i*j при i ³ j;

Kij =

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

 

Сигнальный граф имеет вид

 

 

Система уравнений, соответствующая сигнальному графу имеет вид

 

x ₁ = x ₁ +2 x ₂ +3 x ₃

x ₂ =  x ₁ +6 x ₃ +8 x ₄

x ₃ = x ₁ + x ₂ +12 x ₄ +15 x ₅

x ₄ = x ₂ + x ₃ +20 x ₅ +24 x ₆

x ₅ = x ₃ + x ₄ +30 x ₆

x ₆ =  x ₄ + x ₅

 

Определить передачу k ₁₆ по правилу Мезона. Формула Мезона имеет вид

P_S - передача пути,

D_S - алгебраическое дополнение,

D - определитель.

 

 

Пути из х₁ в х₆ и передаточные функции для каждого из них имеют вид:

 

 

Контура:

 

;

; ;

; ;

; ;

; ;

; ;

;

; .

; .

 

Пары несоприкасающихся контуров

 

L ₁ L ₃, L ₁ L ₄, L ₁ L ₅, L ₁ L ₆, L ₁ L ₈, L ₁ L ₉, L ₁ L ₁₀, L ₁ L ₁₃, L ₁ L ₁₄, L ₁ L ₁₅, L ₁ L ₁₆, L ₁ L ₁₇, L ₁ L ₁₈;

L ₂ L ₄, L ₂ L ₅, L ₂ L ₆, L ₂ L ₈, L ₂ L ₉, L ₂ L ₁₀, L ₂ L ₁₅, L ₂ L ₁₆, L ₂ L ₁₇, L ₂ L ₁₈;

L ₃ L ₅, L ₃ L ₆, L ₃ L ₁₀, L ₃ L ₁₇, L ₃ L ₁₈;

L ₄ L ₆, L ₅ L ₇; L ₅ L ₁₁, L ₅ L ₁₂, L ₆ L ₇, L ₆ L ₈, L ₆ L ₁₁, L ₆ L ₁₂, L ₆ L ₁₃, L ₆ L ₁₄;

L ₇ L ₈, L ₇ L ₁₀, L ₇ L ₁₇, L ₇ L ₁₈;

L ₈ L ₉, L ₉ L ₁₀, L ₁₀ L ₁₁, L ₁₀ L ₁₂, L ₁₁ L ₁₇, L ₁₁ L ₁₈, L ₁₂ L ₁₇, L ₁₂ L ₁₈.

 

Независимые тройки

 

L ₁ L ₃ L ₅, L ₁ L ₃ L ₆, L ₁ L ₃ L ₁₀, L ₁ L ₃ L ₁₇, L ₁ L ₃ L ₁₈, L ₁ L ₄ L ₆, L ₁ L ₆ L ₈, L ₁ L ₆ L ₁₃, L ₁ L ₆ L ₁₄, L ₁ L ₈ L _9, L ₁ L₉L₁₀, L₂L ₄ L₆, L₂L₉L₁₀, L₆L₇L _{8 .}

 

Отсюда

 

D = 1 - ( L ₁ +L ₂ +L ₃ +L ₄ +L ₅ + L ₆ +L ₇ + L ₈ +L ₉ +L ₁₀ +L ₁₁ +L ₁₂ +

+ L ₁₃ +L ₁₄ + L ₁₅ +L ₁₆ + L ₁₇ +L ₁₈ )+ ( L ₁ L ₃+L ₁ L ₄+L ₁ L ₅+L ₁ L ₆+L ₁ L ₈+L ₁ L ₉+L ₁ L ₁₀+L ₁ L ₁₃+L ₁ L ₁₄+L ₁ L ₁₅+L ₁ L ₁₆+L ₁ L ₁₇+L ₁ L ₁₈+L ₂ L ₄+L ₂ L ₅+L ₂ L ₆+L ₂ L ₈+L ₂ L ₉+L ₂ L ₁₀+L ₂ L ₁₅+L ₂ L ₁₆+L ₂ L ₁₇+L ₂ L ₁₈ + L ₃ L ₅+L ₃ L ₆+L ₃ L ₁₀+L ₃ L ₁₇+L ₃ L ₁₈ L ₄ L ₆+L ₅ L ₇+L ₅ L ₁₁+L ₅ L ₁₂+L ₆ L ₇+L ₆ L ₈+L ₆ L ₁₁+L ₆ L ₁₂+L ₆ L ₁₃+L ₆ L ₁₄+L ₇ L ₈+L ₇ L ₁₀+L ₇ L ₁₇+L ₇ L ₁₈+L ₈ L ₉+L ₉ L ₁₀+L ₁₀ L ₁₁+L ₁₀ L ₁₂+L ₁₁ L ₁₇+L ₁₁ L ₁₈+L ₁₂ L ₁₇+L ₁₂ L ₁₈ ) -

( L ₁ L ₃ L ₅+L ₁ L ₃ L ₆+L ₁ L ₃ L ₁₀+L ₁ L ₃ L ₁₇+L ₁ L ₃ L ₁₈+L ₁ L ₄ L ₆+L ₁ L ₆ L ₈+L ₁ L ₆ L ₁₃+L ₁ L ₆ L ₁₄+L ₁ L ₈ L ₉+L ₁ L ₉ L ₁₀+L ₂ L ₄ L ₆+L ₂ L ₉ L ₁₀+L ₆ L ₇ L ₈ ).

D ₁ = 1- L ₈ ;

D ₂ = 1;

D ₃ = 1;

D ₄ = 1 - L ₉ ;

D ₅ = 1;

D ₆ = 1.

.

 

Структура кинематической системы представлена на рисунке: