Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Задание 3. Построить связанный граф из 20 вершин, содержащий 5 точек сочленения

Дискретная математика | ГРАФОВЫЕ МОДЕЛИ, МЕТОДЫ ПРЕДСТАВЛЕНИЯ ГРАФОВ | Выявление ошибок в структуре системы | Анализ быстродействия системы | Анализ надежности структуры | Задание 1 | Задание 8 | КОНТРОЛЬНАЯ РАБОТА № 2 | Суперпозиция логических функций. Формулы. | Булева алгебра и минимизация булевых функций |


Читайте также:
  1. AlllЗадание 3 семестр.
  2. II. Индивидуальное задание студента на практику
  3. III. ГЕОЛОГИЧЕСКОЕ ЗАДАНИЕ
  4. III. Задание на дом.
  5. VI. Диктант с заданием.
  6. VI. Задание по производственной (преддипломной) практике
  7. VI. Задание по учебной (производственно-технологической) практике

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

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

Рисунок 13

 

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

 

Очевидно, в матрице достижимости графа все элементы - единицы, следовательно матрица достижимости - единичная матрица 20x20. Следовательно, все элементы матрицы R = A + AA будут равны 21.

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

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

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

Рисунок 14

 

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

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

Рисунок 15

 

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

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

 

 


Дата добавления: 2015-07-20; просмотров: 125 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Задание 2| Задание 7

mybiblioteka.su - 2015-2024 год. (0.006 сек.)