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

UptoLike

ВУЗ: 

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

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

Рубрика: 

32
Симметрическим называется граф G = (V, U ), в котором (∀v
i
∈V,
∀v
j
∈V) (v
i
, v
j
) ∈U ⇒ (v
j
, v
i
) ∈U (любые две смежные вершины v
i
и v
j
соединены двумя встречными, т. е. противоположно направленны-
ми дугами) (рис. 3, а).
Антисимметрическим называется граф G = (V, U), в котором (∀v
i
∈V,
∀v
j
∈V) (v
i
, v
j
)∈U ⇒ (v
j
, v
i
) ∉U (пара смежных вершин может быть со-
единена лишь в одном направлении, петли отсутствуют) (рис. 4, б).
Полным называется граф G = (V, U), в котором (∀v
i
∈V, ∀v
j
∈V) (v
i
, v
j
)
∉ U ⇒ (v
j
, v
i
) ∈U (i ≠ j) (любые две вершины соединены по крайней
мере одной дугой, т. е. смежны) (рис. 4, в).
Рефлексивным называется граф, имеющий петлю в каждой вер-
шине (v
i
, v
i
).
Транзитивным называется граф, в котором из наличия дуг u
1
= (v, v’)
и u
2
= (v’, v”) следует существование дуги u
3
= (v, v”).
Полным графом с петлями называется граф G = (V, Г), если (∀v
i
∈V)
Гv
i
= V (каждая пара вершин, различных или нет, соединяется дугой, т. е.
это симметрический, рефлексивный и транзитивный граф). Очевидно,
что каждому графу можно сопоставить полный граф с петлями.
Корень дереваv
2
v
1
v
3
v
4
- 1 й уровень
2-й уровень
Рис. 5. Прадерево
Элементарный контур в орграфе образует замкнутый путь с различны-
ми вершинами, кроме первой и последней. При поиске контуров следует
исключить петли, которые не позволяют сдвинуться от начальной верши-
ны. Контур можно задавать по вершинам и по дугам. Например, в графе
рис. 2 можно выделить три элементарных контура: по вершинам: (v
1
, v
2
,
v
1
), по дугам: (u
1
, u
2
); по вершинам: (v
1
, v
2
, v
3
, v
4
, v
1
), по дугам: (u
1
, u
3
, u
6
,
u
7
); по вершинам: (v
1
, v
2
, v
3
, v
4
, v
1
), по дугам: (u
1
, u
4
, u
6
, u
7
).
Прадерево – это бесконтурный иерархический орграф. Его построе-
ние можно начинать от любой вершины исходного графа, принимая ее
за корень дерева, если из нее исходит хотя бы одна дуга. На каждом
следующем уровне располагаются смежные вершины, отстоящие от вер-
шины предыдущего уровня на одну дугу, при этом вершины не повто-
ряются. Вершины каждого уровня упорядочиваются по возрастанию их

Страницы