Дискретная математика. Прокушев Л.А. - 14 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

12
Части графа
Суграфом G’ = (V, Г ’ ) графа G = (V, Г) называется граф, если (∀v
i
∈ V)
(Г’v
i
⊆ Гv
i
), т. е. из исходного графа удаляется некоторое количество дуг
(с сохранением вершин).
Подграфом G’ = (V’, Г’) графа G = (V, Г ) называется граф, если V’ ⊂ V и
(∀v
i
∈ V) (Г’v
i
= V’ ∩ Гv
i
), т. е. из исходного графа удаляются некоторые
вершины вместе со всеми дугами, инцидентными удаленной вершине.
Частичным подграфом G’ = (V’, Г’) графа G = (V, Г ) называется граф,
если V’ ⊂ V, Г’ ⊂ Г, т. е. к исходному графу применены обе описанные
выше операции.
Путем длины n является последовательность (не обязательно раз-
личных) дуг (u
1
, u
2
, …, u
n
) таких, что для соответствующей последова-
тельности n + 1 вершин v
0
, v
1
, …, v
n
справедливо u
i
= (v
i-1
, v
i
) для i = 1,
2, …, n (т. е. конец предыдущей дуги совпадает с началом следующей).
Путь можно задать последовательностью дуг или вершин, через кото-
рые он проходит.
Путь называется замкнутым, если v
0
= v
n
, и незамкнутым, если v
0
≠ v
n
.
Простым называется путь, в котором нет повторяющихся дуг. Элемен-
тарным называется путь, если все его вершины различны.
Контуром называется замкнутый путь, когда v
0
= v
n
. Элементарным
контуром называется контур с различными вершинами (кроме началь-
ной и конечной, которые совпадают).
Орграф называется циклическим (контурным), если он содержит, по
крайней мере, один контур, и ациклическим (бесконтурным) в против-
ном случае.
Ориентированным деревом (прадеревом), растущим из корня v
0
,
называется граф G = (V, U), если: 1) существует единственная вершина
v
0
(корень дерева), в которую не заходит ни одна дуга; 2) в каждую
другую вершину заходит только одна дуга (только одна вершина пред-
шествует вершине v
i
); 3) граф не содержит контуров.
Вершина v
i
называется висячей, если Гv
i
= ∅, т. е. из v
i
не исходит
дуга (нет следующей вершины), её также называют листом.
Прадеревом является граф без контуров и петель, в котором из корня
дерева в любую другую вершину можно прийти только по одному эле-
ментарному пути. Двоичным деревом называется прадерево, если из
каждой невисячей вершины исходит две дуги. Ветвящимся называется
граф, все связные компоненты которого являются прадеревьями.

Страницы