ВУЗ:
Составители:
61
края представляет собой подграф G
A
, а карта дорог федерального
значения – частичный граф G
∆
.
3. Граф G=<X,U> называется полным, если для любой пары
вершин x
i
и x
j
из X в G существует ребро (x
i
,x
j
), т.е. для каждой пары
вершин графа G должна существовать по крайней мере одна дуга,
соединяющая их.
4. Граф G=<X,U> на-
зывается симметрическим,
если во множестве дуг U
для любой дуги (x
i
,x
j
) су-
ществует также противоположно ориентированная дуга (x
j
,x
i
). В
противном случае – граф антисимметрический. На рис. 2.26 приве-
дена иллюстрация полного и симметрического графов.
5. Неориентированный граф⎯G=<X,U> называется двудольным,
если множество его вершин Х может быть разбито на два подмноже-
ства Х
1
и Х
2
так, что каждое ребро начинается в Х
1
, а заканчивается в
Х
2
. Ориентированный граф G=<X,U> называется двудольным, если
его неориентированный двойник ⎯G
− двудольный граф. Двудольный
граф G=<X
1
∪
Х
2
,U> называют пол-
ным, если для любых двух вершин
х
i
∈
X
1
и х
j
∈
X
2
существует ребро
(x
i
,x
j
) в G. На рис. 2.27 приведены примеры полных двудольных гра-
фов.
6. Граф G=<X,U> называется планарным, если он может быть
нарисован на плоскости (сфере) таким образом, что произвольные
две дуги графа не пересекаются друг с другом. Например, полный
двудольный граф К
3,3
не планарный, а также является не планарным
полный граф К
5
(рис. 2.28).
K
2,2
K
1,2
K
1,1
Рис. 2.27
Рис. 2.26
в
б
а
Страницы
- « первая
- ‹ предыдущая
- …
- 63
- 64
- 65
- 66
- 67
- …
- следующая ›
- последняя »
