ВУЗ:
Составители:
60
2.5. Типы графов, их типовые характеристики и операции
Многообразие графов, в первую очередь, зависит от мощности
множества вершин. Но даже при фиксированном n=/X/ число раз-
личных графов велико. Для ориентировки в данном многообразии
рассмотрим ряд классов графов.
1. Подграфом G
A
графа G=<X,> называется граф, в который
входит лишь часть вершин графа G, образующих множество A вме-
сте с дугами, соединяющими эти
вершины. Формально подграф
определяется так:
G
A
=<,
>, A
⊆
X,
A
(x)=(x)
∩
A.
Пусть, например, задан
граф G=<X,> (рис. 2.24) и
пусть ={x
2
,x
3
,x
4
}. Тогда для G
A
=<,
> получим
(
2
)=()
∩
A={
3
,
4
}
∩
A={
3
,
4
},
(
3
)=(
3
)
∩
A=
4
∩
A=
4
,
(
4
)=(
4
)
∩
A=Ø
∩
A=Ø.
2. Частичным графом (также встречается термин “остовый под-
граф”) G
по отношению к графу G=<X,> называется граф, содер-
жащий только часть дуг графа G. Частичный граф формально опре-
деляем следующим условием
G
=<X,>, (x)
⊆
().
Другими словами, если в за-
данном графе убрать любую часть
дуг, то получим частичный граф.
На рис. 2.25 для исходного графа G
приведены подграф G
A
и частичный граф G
. Пусть, например, G
есть карта шоссейных дорог России. Тогда карта дорог Хабаровского
G
A
G
Рис. 2.25
G
G
x
1
x
3
x
2
x
4
Рис. 2.24
G
A
x
4
x
2
x
3
Страницы
- « первая
- ‹ предыдущая
- …
- 62
- 63
- 64
- 65
- 66
- …
- следующая ›
- последняя »
