Kursovaja_po_MOTS_19
.docxЗАДАНИЕ 1. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Связный ориентированный граф задан множеством и отображением Гxi={x|Ik|, xI+l},
где i – текущий номер вершины,
n-количество вершин графа.
K=1; L=5; N=6;
Аналитический способ задания графа:
Графический способ задания графа:
- ориентированный граф:
-неориентированный граф:
Матричный способ задания графа:
- ориентированный граф:
Матрица смежности:
|
|
|
|
||||||
|
|
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
1 |
0 |
1 |
0 |
0 |
0 |
|
|
|
0 |
1 |
0 |
1 |
0 |
0 |
|
||
|
|
0 |
0 |
1 |
0 |
1 |
0 |
|
|
|
|
0 |
0 |
0 |
1 |
0 |
1 |
|
|
|
|
0 |
0 |
0 |
0 |
1 |
0 |
|
Матрица инцидентности:
|
|
|
|
|||||||||||
|
|
1 |
1 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
-1 |
0 |
1 |
1 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
|
|
|
0 |
0 |
-1 |
0 |
1 |
1 |
0 |
-1 |
0 |
0 |
0 |
|
||
|
|
0 |
0 |
0 |
0 |
-1 |
0 |
1 |
1 |
0 |
-1 |
0 |
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
1 |
1 |
-1 |
|
|
|
|
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
1 |
|
- неориентированный граф:
Матрица смежности:
|
|
|
|
||||||
|
|
0 |
2 |
0 |
0 |
0 |
1 |
|
|
|
|
2 |
0 |
2 |
0 |
0 |
0 |
|
|
|
0 |
2 |
0 |
2 |
0 |
0 |
|
||
|
|
0 |
0 |
2 |
0 |
2 |
0 |
|
|
|
|
0 |
0 |
0 |
2 |
0 |
2 |
|
|
|
|
1 |
0 |
0 |
0 |
2 |
0 |
|
Матрица инцидентности:
|
|
|
|
|||||||||||
|
|
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
|
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
|
||
|
|
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
|
|
|
|
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
|
Установим центры и периферийные вершины графов, найдем радиусы и диаметры графов.
Для ориентированного графа:
-матрица отклонений:
|
|
|
|
||||||
|
|
0 |
1 |
2 |
3 |
2 |
1 |
|
|
|
|
1 |
0 |
1 |
2 |
3 |
2 |
|
|
|
2 |
1 |
0 |
1 |
2 |
3 |
|
||
|
|
3 |
2 |
1 |
0 |
1 |
2 |
|
|
|
|
4 |
3 |
2 |
1 |
0 |
1 |
|
|
|
|
5 |
4 |
3 |
2 |
1 |
0 |
|
-вектор удаленностей:
В данном графе вершины x1, x2, x3, x4 являются центрами графа, вершины x6 являются периферийными вершинами, соответственно радиус графа ρ(G) = 3; диаметр графа D(G) = 5
Для неориентированного графа:
-матрица отклонений:
|
|
|
|
||||||
|
|
0 |
1 |
2 |
3 |
2 |
1 |
|
|
|
|
1 |
0 |
1 |
2 |
3 |
2 |
|
|
|
2 |
1 |
0 |
1 |
2 |
3 |
|
||
|
|
3 |
2 |
1 |
0 |
1 |
2 |
|
|
|
|
2 |
3 |
2 |
1 |
0 |
1 |
|
|
|
|
1 |
2 |
3 |
2 |
1 |
0 |
|
-вектор удаленностей:
В данном графе все вершины являются центрами графа и периферийными вершинами, соответственно радиус графа ρ(G) = 3; диаметр графа D(G) = 3
Опишем систему уравнений, соответствующую сигнальному графу, считая, что передача между вершинами xi и xj:
Сигнальный граф в соответствии с приведенной системой:
Найдем передачу между x1 и x6 по правилу Мезона.
где: Рs – передача S-го элементарного пути;
D – определитель графа, который зависит только от передач контуров;
Ds – алгебраическое дополнение для S-ro пути;
S – число элементарных путей.
Элементарные пути из x1 в x6:
Контуры:
Пары несоприкасающихся контуров:
Тройки несоприкасающихся контуров:
D = 1–(L1+L2+L3+L4+L5+L6)+L1L4+L1L5+L1L6+L3L5+L4L6+L3L6-L1L4L6
Приведем структурную схему системы, определяемой топологией графа
ЗАДАНИЕ 2. ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ И ПОТОКЕ МИНИМАЛЬНОЙ СТОИМОСТИ
Транспортная сеть задана графом:
4
8
2/2
3/3
9/8
5/3
1/7
I
1
9/8
4/6
7