Изучение теории графов

Размещено на http://www.allbest.ru/

Изучение теории графов

Задание 1

граф компьютерный алгоритм решение

Построить граф, состоящий из Z изолированных компонент мощностью N₁, N₂,…, N_Z и T изолированных вершин. Во всём графе должно быть I истоков, S стоков, V висячих вершин, R регулярных вершин, три из которых имеют степени r₁, r₂, r₃. Максимальная степень кратности дуг графа должна быть K. В графе должно быть не меньше, чем M пар противоположных дуг. В отчете представить построенный граф с выделением всех построенных элементов. Надписать полустепени исхода и захода для каждой вершины.

Данные: T=1, Z=3, N1=6, N2=8, N3=9, I=2, S=3, V=2, R=4: r1=2, r2=3, r4=4, K=4, M>2.

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

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

8,9,10,11,12,13,14,15,16 (мощность 9);

17,18,19,20,21,22,23,24 (мощность 8);

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

Вершины-истоки: 9, 24.

Вершины-стоки: 3, 14, 19.

Висячие вершины: 15, 18.

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

11 (степень 4), 23 (степень 3), 13 (степень 2), 16 (степень2).

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

5-6, 10-11, 12-13, 22-23.

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

Задание 2

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

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

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

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

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

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

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

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

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

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

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

Задание 3

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

Данные: N=17 и T=4.

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

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

Rang:=A+AA

i=1…17

Матрица результата:

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

Вершины 7 и 16 не имеют путей к остальным вершинам графа и они являются выходами системы. У данных элементов отсутствует влияние на остальные элементы, поэтому ранги равны нулю. Элементы 5, 6, 14, 17 и 8,15 имеют одинаковые ранги, что свидетельствует о их одинаковой значимости в системе.

Выход из строя любого из элементов 5, 6, 14, 17 и 8,15 будет иметь примерноодинаковые последствия - система лишится одной из своих функций, но будет продолжать функционировать.

Задание 4

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

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

Сильные компоненты

Задание 5

Построить связанный ориентированный ациклический непоследовательный граф, состоящий из L порядковых уровней мощностьюN1, N2, N3, N4, N5. Граф содержит 2 истоков и 2 стока. Свернуть граф по найденным уровням. В отчете представить граф, упорядоченный по уровням слева направо и граф свертку.

N1=2, N2=3, N3=4, N4=3, N5=2.

Уровни от входов к выходам

Задание 6

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

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

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

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

Выводы

В данной лабораторной работе были изучены различные способы представления графов и методы исследования топологических структур с использованием основных положений теории графов.

Размещено на Allbest.ru