Задача 1. Элементы теории графов
Связный ориентированный граф G
(Х
, Г)
задан множеством вершин X
={
x
1
, x
2
,…,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
= {
x
a
,x
b
,x
g
,…}
. Если значения индексов a
, b
,g
… переменной x
не соответствуют ни одному из номеров вершин графа, то эта переменная не учитывается во множестве Г
xi
.
Выполнить следующие действия:
а) определить исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами;
б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов;
в) выделить в ориентированном графе два подграфа. Найти объединение, пересечение и разность подграфов;
г) описать систему уравнений, соответствующую сигнальному графу, считая, что передача между вершинами xi
и xj
i*j
при i
³
j
;
Kij
=
1/ (
p
+1)
при i
<
j
.
Найти передачу между вершинами x
1
и 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
= {
x
1
, x
2
,x
3
, x
4
, x
5
, x
6
},
n
= 6
k
= 2,
l
= 1 Г
xi
={
x
|
I
±
k
|
,x
|
I
±
l
|
}.
а) определим исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами:
Определим граф аналитическим способом:
Г
x
1
= {
x
1
,
x
3
,
x
2
};
Г
x
2
= {
x
4
,
x
1
,
x
3
};
Г
x
3
= {
x
1
,
x
5
,
x
2
,
x
4
};
Г
x
4
= {
x
2
,
x
6
,
x
3
,
x
5
};
Г
x
5
= {
x3
,
x
4
,
x
6
};
Г
x
6
= {
x4
,x
5
}.
Ориентированный граф графическим способом:
Неориентированный граф графическим способом:
Ориентированный граф матричным способом:
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.
в) выделим в ориентированном графе два подграфа и найдем объединение, пересечение и разность подграфов.
Выделяем два подграфа: G
1
и G
2
X
1
- {
x
1
,
x
2
}, Г1х1
= {
x
1
,
x
2
}, Г1х2
= {
x
1
},
X
2
- {
x
1
,
x
2
,
x
3
}, Г2х1
= {
x
2
}, Г2х2
= {
x
3
}, Г2х3
= {
x
2
}
.
Объединение
,
,
,
, .
G
Пересечение
,
,
, .
G
Разность
,
,
,
.
G
г) Считая, что передача между вершинами xi
и xj
i*j
при i
³
j
;
Kij
=
1/ (
p
+1)
при i
<
j
.
Сигнальный граф имеет вид
Система уравнений, соответствующая сигнальному графу имеет вид
x
1
=
x
1
+2
x
2
+3
x
3
x
2
=
x
1
+6
x
3
+8
x
4
x
3
=
x
1
+
x
2
+12
x
4
+15
x
5
x
4
=
x
2
+
x
3
+20
x
5
+24
x
6
x
5
=
x
3
+
x
4
+30
x
6
x
6
=
x
4
+
x
5
Определить передачу k
16
по правилу Мезона. Формула Мезона имеет вид
PS
-
передача пути,
DS
-
алгебраическое дополнение,
D
- определитель.
Пути из х1
в х6
и передаточные функции для каждого из них имеют вид:
Контура:
;
;
;
;
;
;
;
;
;
;
;
;
;
.
;
.
Пары несоприкасающихся контуров
L
1
L
3
, L
1
L
4
, L
1
L
5
, L
1
L
6
, L
1
L
8
, L
1
L
9
, L
1
L
10
, L
1
L
13
, L
1
L
14
, L
1
L
15
, L
1
L
16
, L
1
L
17
, L
1
L
18
;
L
2
L
4
, L
2
L
5
, L
2
L
6
, L
2
L
8
, L
2
L
9
, L
2
L
10
, L
2
L
15
, L
2
L
16
, L
2
L
17
, L
2
L
18
;
L
3
L
5
, L
3
L
6
, L
3
L
10
, L
3
L
17
, L
3
L
18
;
L
4
L
6
, L
5
L
7
; L
5
L
11
, L
5
L
12
, L
6
L
7
, L
6
L
8
, L
6
L
11
, L
6
L
12
, L
6
L
13
, L
6
L
14
;
L
7
L
8
, L
7
L
10
, L
7
L
17
, L
7
L
18
;
L
8
L
9
, L
9
L
10
, L
10
L
11
, L
10
L
12
, L
11
L
17
, L
11
L
18
, L
12
L
17
, L
12
L
18
.
Независимые тройки
L
1
L
3
L
5
,L
1
L
3
L
6
,L
1
L
3
L
10
,L
1
L
3
L
17
,L
1
L
3
L
18
,L
1
L
4
L
6
,L
1
L
6
L
8
,L
1
L
6
L
13
,L
1
L
6
L
14
,L
1
L
8
L
9,
L
1
L9
L10
,L2
L
4
L6
,L2
L9
L10
,L6
L7
L
8
.
Отсюда
D
= 1 - (
L
1
+L
2
+L
3
+L
4
+L
5
+ L
6
+L
7
+L
8
+L
9
+L
10
+L
11
+L
12
+
+
L
13
+L
14
+
L
15
+L
16
+
L
17
+L
18
)+ (
L
1
L
3
+L
1
L
4
+L
1
L
5
+L
1
L
6
+L
1
L
8
+L
1
L
9
+L
1
L
10
+L
1
L
13
+L
1
L
14
+L
1
L
15
+L
1
L
16
+L
1
L
17
+L
1
L
18
+L
2
L
4
+L
2
L
5
+L
2
L
6
+L
2
L
8
+L
2
L
9
+L
2
L
10
+L
2
L
15
+L
2
L
16
+L
2
L
17
+L
2
L
18
+
L
3
L
5
+L
3
L
6
+L
3
L
10
+L
3
L
17
+L
3
L
18
L
4
L
6
+L
5
L
7
+L
5
L
11
+L
5
L
12
+L
6
L
7
+L
6
L
8
+L
6
L
11
+L
6
L
12
+L
6
L
13
+L
6
L
14
+L
7
L
8
+L
7
L
10
+L
7
L
17
+L
7
L
18
+L
8
L
9
+L
9
L
10
+L
10
L
11
+L
10
L
12
+L
11
L
17
+L
11
L
18
+L
12
L
17
+L
12
L
18
) -
(
L
1
L
3
L
5
+L
1
L
3
L
6
+L
1
L
3
L
10
+L
1
L
3
L
17
+L
1
L
3
L
18
+L
1
L
4
L
6
+L
1
L
6
L
8
+L
1
L
6
L
13
+L
1
L
6
L
14
+L
1
L
8
L
9
+L
1
L
9
L
10
+L
2
L
4
L
6
+L
2
L
9
L
10
+L
6
L
7
L
8
)
.
D
1
= 1-
L
8
;
D
2
= 1;
D
3
= 1;
D
4
= 1 -
L
9
;
D
5
= 1;
D
6
= 1.
.
Структура кинематической системы представлена на рисунке:
Задача 2. Задача о максимальном потоке и потоке минимальной стоимости
Транспортная сеть задана в виде ориентированного графа, приведенного на рисунке.
На каждом из ребер проставлены значения пропускной способности С
(n
) ребра n
.
Для заданной сети определить максимальный поток j
max
транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком.
Решение:
Максимальный поток j
max
транспортировки груза между указанной парой вершин, считая одну из них источником, а другую — стоком:
Первый шаг.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
|
|