Математические модели в управлении. Заболотский В.П - 99 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

99
Определение 2.3.1. Вершина графа называется изолированной, если
в графе не существует дуг, инцидентных этой вершине.
Определение 2.3.2. Вершина графа называется висячей, если для
всех дуг графа, инцидентных данной вершине, она является начальной.
Определение 2.3.3. Вершина графа называется тупиковой, если для
всех дуг графа, инцидентных данной вершине, она является конечной.
Введенные понятия иллюстрирует
рис. 2.3.1. Граф, диаграмма которого
представлена на рисунке, имеет изо-
лированную вершину 7, висячую вер-
шину 1 и тупиковую вершину 6.
Наличие в графе изолированных
вершин чаще всего свидетельствует
об ошибках, допущенных при описании
структуры системы или построении
графа структуры. Такое заключение
следует из определения системы как
целого, состоящего из взаимосвязан-
ных элементов.
Висячие вершины соответствуют входам системы, а тупиковые –
ее выходам. Наличие лишних висячих или тупиковых вершин, как и
их недостаток, по сравнению с количеством входов и выходов систе-
мы также говорит об ошибках в описании или моделировании струк-
туры.
Выявить все изолированные, висячие и тупиковые вершины дос-
таточно просто по матрице смежности вершин графа.
Пусть R
[n]
– матрица смежности вершин графа. Суммируя эле-
менты r
ij
матрицы по строкам, получают величины
()
()
1
,11.
n
j
ij
i
rrjn
=
==
∑
(2.3.1)
После суммирования элементов r
ij
матрицы по столбцам получа-
ют величины
2
1
4
6
3
5
7
Рис. 2.3.1. Типы вершин графа

Страницы