Составители:
Рубрика:
10
Подграфом графа G называется граф G’ = (
V
′
,
U
′
), где
V
′
⊂ V,
U
′
=
=
U
∩ (V’ & V’), т. е. подграф получается из исходного графа удалением
некоторого числа вершин вместе со всеми ребрами, инцидентными уда-
ленной вершине.
Частью (частичным графом) графа G называется граф G’ = (V’,
U
′
),
где
V
′
⊂ V,
U
′
⊂
U
, т. е. часть графа получается из исходного графа при-
менением обеих описанных операций.
Маршрутом называется конечная последовательность n ребер графа
u
1
,
u
2
,...,
u
n
(не обязательно различных), если существует последова-
тельность v
0
, v
1
, ..., v
n
из n + 1 (не обязательно различных) вершин
таких, что u
i
~ [v
i-1
, v
i
], для i = 1, 2, ..., n.
Длиной маршрута (n) называется число ребер, которые он содержит.
Маршрут замкнут, если v
0
= v
n
, и незамкнут, если v
0
≠ v
n
.
Цепью называется незамкнутый маршрут, если все его ребра различны.
Циклом называется цепь, которая начинается и заканчивается в од-
ной и той же вершине.
Простой цепью называется цепь, в которой все n + 1 вершин v
0
, v
1
, ..., v
n
различны (в этом случае ребра обязательно различны).
Простым циклом называется цикл, если v
0
= v
n
, но все остальные
вершины различны.
Связным называется граф G = (V,
U
), если для всех v
i
и v
j
∈V (v
i
≠ v
j
)
всегда существует цепь из v
i
в v
j
, т. е. если каждая пара различных вер-
шин может быть соединена, по крайней мере, одной цепью. В против-
ном случае граф называется несвязным.
Разновидности графов
Деревом называется связный граф без циклов. Граф является дере-
вом тогда и только тогда, когда каждая пара различных вершин соеди-
няется одной и только одной цепью.
Лесом из K деревьев называется граф без циклов, состоящий из K
компонент.
Обыкновенным называется граф, который не содержит петель и па-
раллельных ребер.
Полным называется граф, в котором любые две различные вершины
являются смежными, т. е. соединяются ребром.
Страницы
- « первая
- ‹ предыдущая
- …
- 10
- 11
- 12
- 13
- 14
- …
- следующая ›
- последняя »
