Page 8 - 4387

-n
-
Г (v )=Г (Г -(n-1) (v )).
i
i
Якщо відображення діє не на одну вершину, а на множину
-
вершин V ={v , v , …, v }, то під Г (V ) розуміють об'єднання
1
k
2
k
k
-
-
-
Г (v ) ∪Г (v ) ∪... ∪Г (v ).
k
2
1
Зворотні багатозначні відображення знаходяться до тих пір,
поки в них або добавляються нові вершини, або не будуть
перелічені усі вершини графа.
Приклад 1.2. Знайти зворотні відображення для вершини v
1
графа, зображеного на рис. 1.1.

Розв'язок.

-
-1
-1
-2
-
Г (v )={v }; Г (v )=Г (Г (v ))=Г (v )={v , v };
1
5
1
1
4
3
5
-
-
-2
-3
Г (v )=Г (Г (v ))=Г (v , v )={v , v , v }∪{∅}={v , v , v }.
2
1
3
1
2
1
4
1
4
4
+1
+3
Оскільки у відображення Г (v ) – Г (v ) увійшли усі
1
1
вершини графа, то пошук зворотних відображень для вершини v
1
припиняється.
+
Прямим транзитивним замиканням деякої вершини v Т (v )
i
i
є об'єднання самої вершини v з прямим відображенням 1-го
i
порядку, 2-го порядку і т.д., тобто
+2
+
+1
Т (v )={v }∪Г (v ) ∪Г (v ) ∪… . (1.3)
i
i
i
i
Таким чином, пряме транзитивне замикання деякої вершини
+
v Т (v ) – це множина вершин, в які існують шляхи з вершини v ,
i
i
i
тобто
+
Т (v )={v : ∃ шлях з v в v }. (1.4)
i
j
j
i
Так, пряме транзитивне замикання для вершини v графа,
1
зображеного на рис. 1.1, буде таким:
+
Т (v )={v }∪{v , v }∪{v , v }∪{v , v , v }={v , v , v , v }.
2
5
1
1
5
5
2
1
3
3
2
1
3
7