Математические основы теории систем - контрольная работа

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

Решение:

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

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 - матрица смежности

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

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

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

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

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

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

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

=>

х₂ , х₃ , х₄ , х₅ - центры графа с наименьшей удаленностью. Радиус ρ (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.

.

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

Задача 2. Задача о максимальном потоке и потоке минимальной стоимости

Транспортная сеть задана в виде ориентированного графа, приведенного на рисунке.

На каждом из ребер проставлены значения пропускной способности С (n ) ребра n .

Для заданной сети определить максимальный поток j _max транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком.

Решение:

Максимальный поток j _max транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком:

Первый шаг.1. Находим какой-либо путь из х ₁ в х ₉ с положительной пропускной способностью.

Tаблица 1.

В результате получен путь l₁ = (x₁ , х₃ , х₆ , х₉ ). Элементы этого пути C_ij помечаем знаком минус, а симметричные элементы C_ji - знаком плюс.

Определяем пропускную способность найденного пути, которая равна наименьшей из пропускных способностей дуг:

Определяем остаточные пропускные способности дуг найденного пути и симметричных ему дуг. Для этого из элементов табл.1 вычитаем C₁ , а к элементам прибавляем C₁ . В результате получим новую табл.2 с измененными пропускными способностями.

Tаблица 2