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

UptoLike

ВУЗ: 

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

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

Рубрика: 

70
Геометрический способ задания графов
При геометрическом способе задания графа множеству X ставится
в соответствие множество точек некоторого подпространства (чаще
плоскости). Эти точки являются вершинами графа. Каждую верши-
ну
i
x
X
∈
соединяют линиями со
стрелками на конце с вершина-
ми
j
xX
∈
, которые являются
образами вершины x
i
, т. е. для
которых выполнено условие
()
ji
xx
∈Γ
. Стрелки на концах
линий направляют от вершины x
i
к вершинам
()
ji
xx
∈Γ
. В ре-
зультате получают геометричес-
кое представление графа, назы-
ваемое диаграммой графа.
Диаграмма графа, приведен-
ного в примерах 2.1.1 и 2.1.2,
представлена на рис. 2.1.1.
Матричный способ задания графов
Рассмотрим конечный граф G = < X, U >, число вершин которого
равно n, а число дуг – m.
Определение 2.1.8. Квадратная матрица
n
ij
n
r
=
R
размерности n × n,
каждой строке и каждому столбцу которой сопоставлены вершины x
i
,
i = 1(1)n графа G, а элементы r
ij
которой равны 1, если граф имеет дугу,
исходящую из вершины x
i
и заходящую в вершину x
j
, и 0, если такой
дуги в графе нет, т. е.
1, если , ;
0, если , ,
ij
ij
ij
xx U
r
∈
=
∉
называется матрицей смежности вершин этого графа.
x
1
x
5
x
2
x
4
x
3
Рис. 2.1.1. Диаграмма графа, приведенного в
примерах 2.1.1 и 2.1.2

Страницы