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

UptoLike

ВУЗ: 

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

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

Рубрика: 

13
Орграфы и бинарные отношения
Пусть V – множество объектов попарного (бинарного) сравнения.
Множество всех упорядоченных пар v, v’∈V обозначается V × V (декар-
тово произведение). Подмножество B ⊆ V
× V называется бинарным
отношением, т. е. (v, v’) ∈ B. Бинарные отношения легко представляют-
ся в виде орграфа, при этом вершины графа соответствуют объектам
сравнения v
i
∈ V, а дуги отображают бинарное отношение между объек-
тами. Если (v, v’) ∈ B, то проводится дуга из v в v’, при этом v – начало,
а v’ – конец дуги, т. е. дуга определяется парой (v, v’).
Описания специальных классов орграфов, не имеющих параллель-
ных дуг, аналогичны терминологии бинарных отношений. Рефлексив-
ным называется граф, имеющий петлю (v, v) в каждой вершине; сим-
метрическим является граф, в котором каждой дуге u = (v, w) соответ-
ствует встречная дуга u’ = (w, v); транзитивным называется граф, в
котором из существования дуг u
1
= (v, v’) и u
2
= (v’, v’’) следует суще-
ствование дуги u
3
= (v, v’’).
Выше были обозначены через Гv подмножество смежных вершин-
концов дуг, имеющих началом вершину v, а через Г
-
v подмножество
смежных вершин-начал дуг, имеющих концом вершину v.
Обозначим через Г
n
v подмножество тех вершин, в которые можно
прийти из вершины v, используя пути длины n (или меньшей), а через
Г
- n
v подмножество тех вершин, из которых можно прийти в вершину
v, используя пути длины n (или меньшей).
Транзитивным замыканием называется многозначное отображение,
определяемое следующей формулой:
2
ˆ
{} ,
ii i i
vv v vΓ = ∪Γ ∪Γ ∪
…
т. е. множество вершин, в которые можно прийти из вершины v
i
по
некоторому пути без повторения дуг. Аналогично определяется обрат-
ное транзитивное замыкание:
12
ˆ
{} ,
ii i i
vv v v
−−−
Γ= ∪Γ ∪Γ ∪
…
т. е. множество вершин, из которых попадают в вершину v
i
по некото-
рому пути без повторения дуг.
Сильно связным графом G = (V, Г ) называется граф, если,
ˆ
(),
ii
vVГv V∀∈ =
т. е. для любых двух вершин v
i
, v
j
существует путь, идущий из v
i
в v
j
.
Сильно связный граф – это граф, содержащий контуры.

Страницы