Связный ориентированный граф G (Х, Г) задан множеством вершин X={x1, x2,…, xn} и отображением Гxi={x|I±k|, x|I±l|}, i =1, 2, …, n. Здесь i - текущий номер вершины, n- количество вершин графа. Значение индексов n, k и l возьмем из табл.1 в соответствии с номером варианта. Индексы k и l формируют значения индексов a, b, g … переменной x в отображении Гxi = {xa, xb, xg,… }. Если значения индексов a, b, g … переменной x не соответствуют ни одному из номеров вершин графа, то эта переменная не учитывается во множестве Гxi.
Выполнить следующие действия:
а) определить исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами;
б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов;
в) выделить в ориентированном графе два подграфа. Найти объединение, пересечение и разность подграфов;
г) описать систему уравнений, соответствующую сигнальному графу, считая, что передача между вершинами xi и xj
i*j при i ³ j;
Kij =
1/ (p+1) при i<j.
Найти передачу между вершинами x1 и xn, используя правило Мезона. Построить структуру кибернетической системы, определяемой топологией графа;
Таблица 1
№ варианта | |||||||||||||||
N | |||||||||||||||
K | |||||||||||||||
L | |||||||||||||||
№ варианта | |||||||||||||||
N | |||||||||||||||
K | |||||||||||||||
L |
Решение:
Множество вершин
X = {x1, x2, x3, x4, x5, x6 }, n = 6 k = 2, l = 1 Гxi={x|I±k|, x|I±l|}.
а) определим исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами:
Определим граф аналитическим способом:
Гx1 = { x1, x3, x2 };
Гx2 = { x4, x1, x3 };
Гx3 = { x1, x5, x2, x4 };
Гx4 = { x2, x6, x3, x5 };
Гx5 = { x3, x4, x6 };
Гx6 = {x4, x5 }.
Ориентированный граф графическим способом:
Неориентированный граф графическим способом:
Ориентированный граф матричным способом:
RG - матрица смежности
x1 | x2 | x3 | x4 | x5 | x6 | |
x1 | 1* | |||||
x2 | ||||||
x3 | ||||||
x4 | ||||||
x5 | ||||||
x6 |
AG - матрица инцидентности
v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 | v9 | v10 | v11 | v12 | v13 | v14 | v15 | v16 | v17 | v18 | v19 | |
x1 | 1* | -1 | -1 | ||||||||||||||||
x2 | -1 | -1 | -1 | ||||||||||||||||
x3 | -1 | -1 | -1 | -1 | |||||||||||||||
x4 | -1 | -1 | -1 | -1 | |||||||||||||||
x5 | -1 | -1 | -1 | ||||||||||||||||
x6 | -1 | -1 |
Неориентированный граф матричным способом:
RD - матрица смежности
x1 | x2 | x3 | x4 | x5 | x6 | |
x1 | 1* | |||||
x2 | ||||||
x3 | ||||||
x4 | ||||||
x5 | ||||||
x6 |
AD - матрица инцидентности
v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 | v9 | v10 | v11 | v12 | v13 | v14 | v15 | v16 | v17 | v18 | v19 | |
x1 | 1* | ||||||||||||||||||
x2 | |||||||||||||||||||
x3 | |||||||||||||||||||
x4 | |||||||||||||||||||
x5 | |||||||||||||||||||
x6 |
б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов:
- матрица отклонений имеет вид:
x1 | x2 | x3 | x4 | x5 | x6 | |
x1 | ||||||
x2 | ||||||
x3 | ||||||
x4 | ||||||
x5 | ||||||
x6 |
- вектор отклонения
=>
х2, х3, х 4, х5 - центры графа с наименьшей удаленностью. Радиус ρ (G) = 2.
Периферийными вершинами являются вершины х1, х6 с наибольшей удаленностью. Диаметр графа D (G) = 3.
в) выделим в ориентированном графе два подграфа и найдем объединение, пересечение и разность подграфов.
Выделяем два подграфа: G1 и G2
X1 - {x1, x2}, Г1х1 = {x1, x2}, Г1х2 = {x1},
X2 - {x1, x2, x3}, Г2х1 = {x2}, Г2х2 = {x3}, Г2х3 = {x2}.
Объединение ,
,
,
,
.
G
Пересечение
,
,
,
.
G
Разность
,
,
,
.
G
г) Считая, что передача между вершинами xi и xj
i*j при i ³ j;
Kij =
1/ (p+1) при i<j.
Сигнальный граф имеет вид
Система уравнений, соответствующая сигнальному графу имеет вид
x1 = x1 +2x2 +3x3
x2 = x1 +6 x3 +8 x4
x3 = x1 +
x2+12x4 +15x5
x4 = x2 +
x3 +20 x5 +24x6
x5 = x3 +
x4 +30x6
x6 = x4 +
x5
Определить передачу k16 по правилу Мезона. Формула Мезона имеет вид
PS - передача пути,
DS - алгебраическое дополнение,
D - определитель.
Пути из х1 в х6 и передаточные функции для каждого из них имеют вид:
Контура:
;
;
;
;
;
;
;
;
;
;
;
;
;
.
;
.
Пары несоприкасающихся контуров
L1L3, L1L4, L1L5, L1L6, L1L8, L1L9, L1L10, L1L13, L1L14, L1L15, L1L16, L1L17, L1L18;
L2L4, L2L5, L2L6, L2L8, L2L9, L2L10, L2L15, L2L16, L2L17, L2L18;
L3L5, L3L6, L3L10, L3L17, L3L18;
L4L6, L5L7; L5L11, L5L12, L6L7, L6L8, L6L11, L6L12, L6L13, L6L14;
L7L8, L7L10, L7L17, L7L18;
L8L9, L9L10, L10L11, L10L12, L11L17, L11L18, L12L17, L12L18.
Независимые тройки
L1L3L5, L1L3L6, L1L3L10, L1L3L17, L1L3L18, L1L4L6, L1L6L8, L1L6L13, L1L6L14, L1L8L9,L1L9L10, L2L4L6, L2L9L10, L6L7L8.
Отсюда
D = 1 - (L1 + L2 + L3 + L4 + L5 + L6 + L7 + L8 + L9 + L10 + L11 + L12 +
+L13 + L14+L15 + L16+L17 + L18)+ (L1L3 + L1L4 + L1L5 + L1L6 + L1L8 + L1L9 + L1L10 + L1L13 + L1L14 + L1L15 + L1L16 + L1L17 + L1L18 + L2L4 + L2L5 + L2L6 + L2L8 + L2L9 + L2L10 + L2L15 + L2L16 + L2L17 + L2L18 +L3L5 + L3L6 + L3L10 + L3L17 + L3L18 L4L6 + L5L7 + L5L11 + L5L12 + L6L7 + L6L8 + L6L11 + L6L12 + L6L13 + L6L14 + L7L8 + L7L10 + L7L17 + L7L18 + L8L9 + L9L10 + L10L11 + L10L12 + L11L17 + L11L18 + L12L17 + L12L18) -
(L1L3L5 + L1L3L6 + L1L3L10 + L1L3L17 + L1L3L18 + L1L4L6 + L1L6L8 + L1L6L13 + L1L6L14 + L1L8L9 + L1L9L10 + L2L4L6 + L2L9L10 + L6L7L8).
D1 = 1- L8;
D2 = 1;
D3 = 1;
D4 = 1 - L9;
D5 = 1;
D6 = 1.
.
Структура кинематической системы представлена на рисунке: