Анализ структур сложных систем графовыми методами

Санкт - Петербургский государственный  технологический институт

(технический  университет)

 

Кафедра систем автоматизированного  проектирования и управления

 

 

 

Факультет: 4 
Курс: 2

Группа: 414

 

 

Учебная дисциплина: ДИСКРЕТНАЯ МАТЕМАТИКА

 

_{ЛАБОРАТОРНАЯ  РАБОТА}

 

АНАЛИЗ СТРУКТУР СЛОЖНЫХ СИСТЕМ

ГРАФОВЫМИ МЕТОДАМИ

 

 

Вариант № 6

 

 

Работа выполнена:

Голубов  Г.В.

Научный руководитель:

Халимон В. И.

 

 

 

Санкт-Петербург

2006 г.

 

Содержание

 

1. Цель работы_________________________________________________________________ 3

2. Практическая часть___________________________________________________________ 4

2.1 Задание  1____________________________________________________________ 4

2.2. Задание  2____________________________________________________________ 5

2.3. Задание  3____________________________________________________________ 7

2.4. Задание  4____________________________________________________________ 9

2.5. Задание  5____________________________________________________________ 9

2.6. Задание  6____________________________________________________________ 10

2.7. Задание  7____________________________________________________________ 11

2.8. Задание  8____________________________________________________________ 12

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Цель работы

 

 

Изучение  основ теории графов, базовых понятий  и определений; ознакомление с задачами, возникающими в теории графов и методами их решения; освоение компьютерных способов представления графов и алгоритмов машинной обработки графов.

Освоение  компьютерных технологий обработки  графов; изучение специализированных программных продуктов для ввода, редактирования и анализа графов на ЭВМ.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Практическая часть

 

Практическая  часть работы была реализована с  помощью программы GRAPH TOOLBOX 1.3 (build 3010.20.02) с использованием материалов методического  пособия «Анализ структур сложных  систем графовыми методами».

 

2.1. Задание 1

 

Построить граф, состоящий из 3 изолированных компонентов мощностью 5, 6, 7 и 3 изолированные вершины. Во всём графе должно быть 2 истока, 2 стока, 2 висячие вершины, 3 регулярных вершин, три из которых имеют степени 2, 3, 4. Максимальная степень кратности дуг графа должна быть 5. В графе должно быть не меньше, чем 3 пар противоположных дуг.

 

Вершины изолированных компонент:

1, 2, 3, 4, 5 (мощность 5);

6, 7, 8, 9, 10, 11 (мощность 6);

12, 13, 14, 15, 16, 17, 18 (мощность 6).

Изолированные вершины:

19, 20, 21

Вершины-истоки:

4,    17.

Вершины-стоки:

9,    11.

Висячие вершины:

4, 11.

 

Регулярные вершины:

2 (степень 2), 8 (степень 3), 12 (степень 4).

Пары противоположных дуг:

1-8,   7-4,   11-13,   18-19,   15-17,  23-29,  28-22,  21-25, 24-33

 

Полустепени исхода и захода вершин:

 

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
P+	2	2	2	0	2	2	1	3	2	2	1	4	2	1	3	2	1	2	0	0	0
P-	1	2	1	1	3	3	2	3	0	3	0	4	1	2	1	1	2	1	0	0	0

 

2.2. Задание 2

 

Построить ориентированный  граф из 7 вершин и 14 дуг, содержащий один исток, один сток, одну изолированную  вершину, одну регулярную вершину, одну петлю, пару одинаково направленных дуг, пару противоположно направленных дуг. С истоком и со стоком должно быть связано более двух дуг.

Построить и  проанализировать следующие способы  представления графов: матрица смежности, матрица инцидентности, матрицы  окрестностей вершин по входам и по выходам, список дуг. В отчете представить  построенный граф и матричные  представления графа с описанием. (1 граф и 5 матриц)

 

Матрица смежности:             Матрица инцидентности:

 

 

 

Список дуг:

 

 

Матрица окрестностей вершин по выходам:

 

 

 

Матрица окрестностей вершин по входам:

 

 

 

 

Из  матрицы смежности:

Единица в  третьей строке на главной диагонали  говорит о том, что третьей  вершина имеет дугу-петлю. Вершины 4 и 2 имеют противоположно направленные дуги, т. к. соответствующие элементы матрицы, симметричные главной диагонали, заполнены. Т.к. число во второй строке третьего столбца - 2, то в графе имеются  две кратные дуги, направленные от 3-ей к 4-ой вершине. Строки   матрицы   соответствуют   выходным   окрестностям   вершин,   а  столбцы  -   входным окрестностям. Сумма элементов по строке равна  полустепени исхода соответствующей  вершины, а сумма элементов по столбцу - полустепени захода. Вершине-истоку 1 соответствует нулевой столбец 1 и ненулевая строка 1, а вершине-стоку 5 соответствует нулевая строка 5 и ненулевой столбец 5. Изолированной  вершине 6 соответствует нулевая  строка 6 и нулевой столбец 6.

Из  матрицы инцидентности:

Дуге-петле 3 в матрице инцидентности соответствует  единственная единица в 11-ом столбце, расположенная в строке с номером  вершины, которой она принадлежит. Столбцы 6 и 7 одинаковы, следовательно, соответствующие дуги являются кратными. Столбцы 13 и 10 станут одинаковыми, если в них поменять местами -1 и 1, следовательно, соответствующие им дуги противоположно направлены. Количество -1 в любой  строке равно полустепени исхода соответствующей вершины, а количество 1 равно полустепени захода. Изолированной  вершине 6 соответствует нулевая -6ая строка. Вершине-истоку 1 соответствует 1-ая строка, в которой имеются -1 и  нет 1. Вершине-стоку 5 соответствует 5-ая строка, в которой имеются 1 но нет -1.

Из  списка дуг:

Дуге-петле 3 графа соответствует столбец  матрицы списка дуг, в котором  элементы равны между собой и  равны номеру вершины, которой эта  дуга принадлежит. Т.к. дуги 6 и 7 кратны, им соответствуют одинаковые столбцы 6 и 7 матрицы. Противоположно направленным дугам 10 и 13 соответствуют 10 и 13 столбцы  матрицы, которые оказываются одинаковыми, если в одном из них переставить  местами элементы. Полустепень исхода любой вершины - количество повторений ее номера в первой строке матрицы, а полустепень захода - количество повторений ее номера во второй строке матрицы. Изолированная вершина 6 имеет  номер, который не встречается ни в первой, ни во второй строке. Вершина-исток 1 имеет номер, который встречается в первой и не встречается во второй строке, а вершина-сток 5 имеет номер, который встречается во второй и не встречается в первой строке.

Из  матриц окрестностей вершин:

Если   в   графе   имеются   кратные  дуги,   то   в   i-ой  окрестности   массива   FO  (FI)   имеются повторяющиеся номера вершин. Противоположные дуги между вершинами iи jнаходятся как номер jвстречается в окрестности i-ой вершины и одновременно номер iесть в окрестности j-ой вершины.

 

2.3. Задание 3

 

Построить связанный  граф из 18 вершин, содержащий 4 точек сочленения, и не содержащий висячих и изолированных вершин. Рассчитать ранги вершин этого графа.

В отчете представить  построенный граф с выделенными  точками сочленения и подписанными рангами каждой вершины. (1 картинка).

 

Матрица достижимости графа А и ранги вершин графа:

Ранги элементов  вычисляются по следующей формуле: R= А + АА , где А - матрица достижимости графа.

 

 

 

 

 

 

 

 

 

 

 

 

Т.к. ранг вершины  графа равен отношению суммы  элементов соответствующей строки к сумме элементов всей матрицы, то ранги вершин графа будут равны:

 

 

 

Вершины 7 и 11 не имеют путей к остальным вершинам графа и они являются выходами системы. У данных элементов отсутствует влияние на остальные элементы, поэтому ранги равны нулю. Элементы 1, 2, 3, 4, 16,17и 18;5 и 9;6,8,10,12,13 и 15 имеют одинаковые ранги, что свидетельствует о их одинаковой значимости в системе. Выход из строя любого из элементов 1, 2, 3, 4, 16,17и 18;5 и 9;6,8,10,12,13 и 15 будет иметь примерно одинаковые последствия - система лишится одной из своих функций, но будет продолжать функционировать.

 

 

2.4. Задание 4

 

Построить связанный  ориентированный граф, содержащий 5 сильных компонент связанности  мощностью 4,5,6,7,1. Свернуть граф по найденным компонентам.

В отчете представить  граф, раскрашенный по компонентам  и граф-свертку. (2 картинки).

 

 

 

 

 

 

 

2.5. Задание 5

 

Построить связанный  ориентированный ациклический непоследовательный граф, состоящий из 5 порядковых уровней  мощностью 3, 4, 5, 3, 2. Граф содержит 3 истоков и 2 стока. Свернуть граф по найденным уровням. В отчете представить граф, упорядоченный по уровням слева направо и граф-свертку. (2 картинки)

 

 

 

 

2.6. Задание 6

 

Построить связанный  граф из 5 вершин и 7 дуг. Используя метод, описанный в учебном пособии, перечислить все маршруты этого графа длиной 1, 2, 3. В отчете привести граф и выкладки по вычислению матриц. (1 граф и 3 матрицы)

Матрица маршрутов длины 1

	V1	V2	V3	V4	V5
V1		v1u1v2		v1u2v4
V2					v2u3v5
V3	v3u4v1	v3u5v2
V4			v4u7v3		v4u6v5
V5

 

Матрица маршрутов длины 2

 

	V1	V2	V3	V4	V5
V1			v1u2v4u7v3		v1u1v2u3v5 v1u2v4u6v5
V2
V3		v3u4v1u1v2		v3u4v1u2v4	v3u5v2u3v5
V4	v4u7v3u4v1	v4u7v3u5v2
V5

 

Матрица маршрутов длины 3

 

	V1	V2	V3	V4	V5
V1	v1u2v4u7v3u4v1	v1u2v4u7v3u5v2
V2
V3			v3u4v1u2v4u7v3		v3u4v1u1v2u3v5 v3u4v1u2v4u6v5
V4		v4u7v3u4v1u1v2		v4u7v3u4v1u2v4	v4u7v3u5v2u3v5
V5

 

2.7. Задание 7

 

 

Построить связанный  ориентированный граф из 25 вершин, содержащий один исток и один сток, не содержащий петель. Задать веса на дугах графа и пронумеровать все вершины. Между истоком и стоком построить Р>5 путей через остальные вершины, длиной больше 5 дуг.

Изменяя веса на дугах модифицировать граф так, чтобы  кратчайшие пути по сумме весов и  по количеству дуг между истоком  и стоком не имели ни одной общей  дуги (не совпадали). В отчете представить  граф с выделенными путями, указать  длину путей по весам и по количеству дуг. (1 картинка)

На этом же графе построить исходящее дерево кратчайших путей с корнем в истоке и заходящее дерево кратчайших путей  с корнем в стоке. (2 картинки)

 

 

 

Вершина-исток - 1, вершина сток - 25. Между истоком и стоком существует более

5-ти путей, длиной более 5-и дуг. Кратчайший путь по количеству дуг (5 дуг, вес 21) и кратчайший путь по весам дуг (6 дуг, вес 14) не имеют ни одной общей дуги.

 

Исходящее дерево кратчайших путей  в корнем в вершине-истоке (1):

 

по количеству дуг:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

по весам дуг:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заходящее дерево кратчайших путей  в корнем в вершине-стоке (22):

 

по количеству дуг:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

по весам дуг:

 

 

2.8. Задание 8

 

 

Построить связанный  ориентированный граф, имеющий как  минимум две центральные вершины, как минимум две периферийные вершины, как минимум две обычные вершины так, чтобы его радиус был не равен нулю и не равен диаметру. Начать построение с 6 вершин, добиться результата добавлением и удалением дуг и вершин. Построить максимальное покрывающее дерево кратчайших путей.