Графы и системный анализ: лабораторные работы по моделированию

1. Системный анализ

Лабораторные работы

2. Лабораторная работа №1. Формализация структурной модели системы на основе теории графов

Задание. Преобразовать исходное описание
структурной модели системы в заданное.
№ варианта
Матрица
смежности А
1
2
3
4
5
6
7
8
9
10
11
12
Задано
Матрица
Множество
Множество
инциденций В правых
левых
инциденций G+ инциденций G-
А
+
+
+
В
+
+
+
+
+
Получить
G+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
G-
+
+
+
+
+
+
+
+
+
+
+
+

3. Содержание отчета

1.
2.
3.
Задание кафедры
Алгоритм работы программы
Тестовый пример (в виде скриншота)

4. Лабораторная работа №2. Алгоритма введения порядковой функции на графе для выделения иерархических уровней в структуре

Задание. Запрограммировать алгоритм на основе заданного
описания структурной модели системы. После изменения
нумерации вершин указать новый и старый номер вершины
и представить новый граф в заданном описании
№ варианта
Матрица
смежности
А
1
2
3
4
5
6
7
8
9
10
11
12
Задано
Матрица
Множество
инциденций правых
В
инциденций
G+
Множество
левых
инциденций
G-
А
+
+
+
Получить
В
G+
G-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+

5.

6.

7. Лабораторная работа №3. Алгоритм топологической декомпозиции структуры системы

Задание. Запрограммировать алгоритм на основе заданного описания
структурной модели системы. После выделения подсистем указать
список номеров вершин, входящих в каждую подсистему и представить
новый граф из подсистем (вершина – это подсистема) в заданном
описании.
№ варианта
Матрица
смежности
А
1
2
3
4
5
6
7
8
9
10
11
12
Задано
Матрица
Множество
инциденций правых
В
инциденций
G+
Множество
левых
инциденций
G-
А
+
+
+
Получить
В
G+
G-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+

8.

1. Указать также дуги, входящие в каждый связанный
подграф (подсистему)
2. Представить граф из подсистем в заданном виде

9.

1. Представить граф из подсистем в заданном виде

10. Лабораторная работа №4 Алгоритмы поиска кратчайших путей на графе

Задание. Запрограммировать заданный алгоритм поиска кратчайших
путей на графе. Использовать заданное описание расстояний
между смежными вершинами графа. Кратчайшие пути
представить в виде матрицы кратчайших путей U размером nxn.
№
варианта
1
2
3
4
Задано
Матрица
Матрица
Множество
смежности инциденций правых
А
В
инциденций G+
+
Множество левых
инциденций
G-
Матрица расстояний
между смежными
вершинами D
Алгоритм поиска кратчайших путей
Алгоритм, когда длина каждой дуги 1 (МУ п.2.2.1)
+
Алгоритм, когда длина каждой дуги 1 (МУ п.2.2.1)
+
Алгоритм, когда длина каждой дуги 1 (МУ п.2.2.1)
+
Алгоритм, когда длина каждой дуги 1 (МУ п.2.2.1)
5
+
Алгоритм для графа без контуров (МУ п.2.2.2)
6
+
Метод линейного программирова-ния (МУ п.2.3.3)
7
+
Метод решения транспортной задачи (МУ п.2.3.4)
8
+
Метод Дейкстры (МУ п.2.3.1)
9
+
10
+
Метод Прима (через минимальное остовное дерево)
https://evileg.com/ru/post/524/
Метод Флойда –Уоршелла (МУ п.2.3.2)
11
+
Алгоритм Данцига
12
+
Метод Беллмана-Форда
https://ru.wikipedia.org/wiki/Алгоритм_Беллмана_—_Форда
13
+
Волновой алгоритм https://ru.wikipedia.org/wiki/Алгоритм_Ли
14
+
Алгоритм Джонсона
https://ru.wikipedia.org/wiki/Алгоритм_Джонсона
15
+
Алгоритм Левита

11.

12.

13. Литература к лабораторной работе №4

1.
Новиков Ф. А. Дискретная математика: Учебник для вузов. Стандарт третьего
поколения [Текст] / Ф. А. Новиков – СПб.: Питер, 2011. – 384 с. – (Серия
«Учебник для вузов»)
2. Новиков Ф. А. Дискретная математика для программистов: Учебник для
вузов [Текст] / Ф. А. Новиков – СПб.: Питер, 2009. – 384 с.– (Серия «Учебник
для вузов»).
3. Романовский И.В. Дискретный анализ: Учебное пособие для студентов,
специализирующихся на прикладной математике и информатике.. — 3-е
изд. — СПб.: Невский Диалект, 2003 г.
4. Макоха, А. Н. Дискретная математика: учебное пособие [Текст] / А.Н.
Макоха, П.А. Стаднюк, Н.И. Червяков – М.: ФИЗМАТЛИТ, 2005. –368 с.
5. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977.
6. Кофман А. , Анри-Лабодер А. Методы и модели исследования операций.
Целочисленное программирование. – М.: Мир,1977
7. Саати Т. Целочисленное программирование. – М.: Мир,1973
8. Ху Т. Целочисленное программирование и потоки в сетях. – М.: Мир, 1974. –
520 с.
9. Майника Э. Алгоритмы оптимизации на сетях и графах. – М.: Мир, 1981.
10. Пападимитриу Х. , Стайглиц К. Комбинаторная оптимизация. Алгоритмы и
сложность. – М.: Мир, 1985.
11. Хилари Ф. Теория графов. - М.: Мир, 1973.
12. Басакер Р., Саати Т. Конечные графы и сети – М.: Наука, 1974

14. Лабораторная работа №5 Анализ качества структуры на основе структурных характеристик системы

Задание. Запрограммировать методику расчета группы показателей качества
структуры системы. Использовать заданное исходное описание графа. В
случае невозможности рассчитать показатель для ориентированного графапреобразовать граф в неориентированный
№
варианта
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Матрица
смежност
иА
Задано
Матрица Множество
Множество Связинциден- правых инлевых инци- ности AΣ,
ций В
циденций, G+ денций,GС
+
+
+
+
Рассчитать показатели
ИзбыточКомпакт- Централи2
ности k, ε
ности, Q, зации, Z, δQотн, d
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+