Контрольная работа вариант № 8 Задача 1. Элементы теории графов
Связный ориентированный граф G(Х, Г) задан множеством вершин X={x1, x2, …, xn} и отображением Гxi={x|Ik|, x|Il|}, i =1, 2,…, n. Здесь i – текущий номер вершины, n- количество вершин графа. Значение индексов n, k и l взять из табл. 1 в соответствии с номером варианта. Индексы k и l формируют значения индексов , , … переменной x в отображении Гxi = {x , x , x,…}. Если значения индексов , , … переменной x не соответствуют ни одному из номеров вершин графа, то эта переменная не учитывается во множестве Гxi.
Выполнить следующие действия:
а) определить исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами;
б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов;
в) выделить в ориентированном графе два подграфа. Найти объединение, пересечение и разность подграфов;
г) описать систему уравнений, соответствующую сигнальному графу, считая, что передача между вершинами xi и xj
i*j
при
i
j;
Kij =
1/(p+1) при i<j .
Найти передачу между вершинами x1 и xn, используя правило Мезона. Построить структуру кибернетической системы, определяемой топологией графа.
Таблица 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 = {x1, x2, x3, x4, x5}, n = 5, k = 5, l = 1. Гxi={x|Ik|, x|Il|}.
а) определим исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами:
Определим граф аналитическим способом:
Гx1 = { x4, x2 };
Гx2 = { x3, x1 };
Гx3 = { x2, x4 };
Гx4 = { x1, x5, x3};
Гx5 = {x4}.
Ориентированный граф графическим способом:
Неориентированный граф графическим способом:
Ориентированный граф матричным способом:
RG
– матрица смежности 
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
|
x1 |
0 |
1 |
0 |
1 |
0 |
|
x2 |
1 |
0 |
1 |
0 |
0 |
|
x3 |
0 |
1 |
0 |
1 |
0 |
|
x4 |
1 |
0 |
1 |
0 |
1 |
|
x5 |
0 |
0 |
0 |
1 |
0 |
AG
– матрица инцидентности
|
|
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
v7 |
v8 |
v9 |
v10 |
|
x1 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 |
|
x2 |
-1 |
1 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
x3 |
0 |
0 |
-1 |
1 |
1 |
-1 |
0 |
0 |
0 |
0 |
|
x4 |
0 |
0 |
0 |
0 |
-1 |
1 |
1 |
-1 |
-1 |
1 |
|
x5 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
0 |
0 |
Неориентированный граф матричным способом:
RD – матрица смежности
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
|
x1 |
0 |
2 |
0 |
2 |
0 |
|
x2 |
2 |
0 |
2 |
0 |
0 |
|
x3 |
0 |
2 |
0 |
2 |
0 |
|
x4 |
2 |
0 |
2 |
0 |
2 |
|
x5 |
0 |
0 |
0 |
2 |
0 |
AD – матрица инцидентности
|
|
v1 |
v2 |
v3 |
v4 |
v5 |
v6 |
v7 |
v8 |
v9 |
v10 |
|
x1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
|
x2 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
x3 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
|
x4 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
x5 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов:
–матрица
отклонений; 
– вектор отклонения.
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
|
x1 |
0 |
1 |
2 |
1 |
2 |
|
x2 |
1 |
0 |
1 |
2 |
3 |
|
x3 |
2 |
1 |
0 |
1 |
2 |
|
x4 |
1 |
2 |
1 |
0 |
1 |
|
x5 |
2 |
3 |
2 |
1 |
0 |
=>
Центры графа – это вершины с наименьшей удаленностью. Периферийные вершины - вершины с наибольшей удаленностью. В данном случае периферийными вершинами являются две вершины x2, x4, а центрами графа являются три вершины x1, x3, x5. Тогда радиус ρ(G) =2, а диаметр графа D(G) = 3.
в) выделим в ориентированном графе два подграфа и найдем объединение, пересечение и разность подграфов:
Выделяем два подграфа: G1 и G2
X1 – {x1, x2}, Г1х1 = { x2 }, Г1х2 = {x1},
X2 – {x1, x2, x3}, Г2х1 = {x2}, Г2х2 = {x3}, Г2х3 = {x2}.
Объединение
графов:
,
,
,
,
.
G
Пересечение
,
,
,
.
G
Разностью
графов G1(X1, Г1)
и G2(X2, Г2)
называется граф
,
где
– дополнение по отображению графа G2
до насыщенного.
,
где
.
Он имеет вид
;
,
.
Граф имеет вид:
G
г
)
i*j
при
i
j;
Kij = 1/(p+1) при i<j .
Сигнальный граф имеет вид
Система уравнений, соответствующая сигнальному графу имеет вид
x1 = 2 x2 + 4x4
x2
=
x1
+6x3
x3
=
x2
+12 x4
x4
=
x1
+
x3
+20x5
x5
=
x4.
Определить
передачу k15
по правилу
Мезона. Формула Мезона имеет вид
PS – передача пути,
DS – алгебраическое дополнение,
D – определитель.
Пути из х1 в х5:
.
Контура:
; 
; 
;
; 
.
;
Пары несоприкасающихся контуров L1L3, L1L4, L2L4, L2L5.
Отсюда
(L1L3+
L1L4+
L2L4+
L2L5).
D1 = 1- L2
D2 = 1.
.
Структура кинематической системы представлена на рисунке
