Рефераты

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

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

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

Связный ориентированный граф G, Г) задан множеством вершин X={x1, x2, …, xn} и отображением Гxi=, 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

варианта

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, x6 }, n = 6 k = 2, l = 1 Гxi=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* 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

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

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

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

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

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

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

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

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

 =>

х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.

.

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


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

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

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

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

Решение:

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

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

Tаблица 1.

x1

x2 (1)

x3 (1)

x4 (1)

x5 (2)

x6 (3)

x7 (3)

x8 (2)

x9 (6)

x1

7

9-

4

x2

0 8 3 6

x3

0+

5

8-

4

x4

0 0 0 9 2

x5

0 2

x6

0+

5

3-

x7

0 0 0 7 6

x8

0 0 0 0 8

x9

0+

0 0

В результате получен путь l1 = (x1, х3, х6, х9). Элементы этого пути Cij помечаем знаком минус, а симметричные элементы Cji - знаком плюс.

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

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

Tаблица 2

x1

x2 (1)

x3 (1)

x4 (1)

x5 (2)

x6 (3)

x7 (3)

x8 (2)

x9 (7)

x1

7

6-

4

x2

0 8 3 6

x3

3+

5 5

4-

x4

0 0 0 9 2

x5

0 2

x6

3 5 0

x7

0+

0 0 7

6-

x8

0 0 0 0 8

x9

3

0+

0

Страницы: 1, 2


© 2010 Рефераты