Page 27 - 4336

Зворотні багатозначні відображення знаходяться до тих пір,

поки в них або добавляються нові вершини, або не будуть

перелічені усі вершини графа.

Приклад 2.2. Знайти зворотні відображення для вершини v
1
графа, зображеного на рис. 2.1.

Розв'язок.

-1
Г (v )={v };
5
1
-
-
-2
-1
Г (v )=Г (Г (v ))=Г (v )={v , v };
4
5
1
1
3
-2
-3
-
-
Г (v )=Г (Г (v ))=Г (v , v )={v , v , v }{}={v , v , v }.
1
4
1
1
3
4
2
2
1
4
+1
+3
Оскільки у відображення Г (v ) – Г (v ) увійшли усі
1
1
вершини графа, то пошук зворотних відображень для вершини v
1
припиняється.
Багатозначні відображення для н-графа будуються, якщо
представити кожне ребро двома протилежно направленими
дугами.
2.2 Транзитивні замикання
2.2.1 Прямі транзитивні замикання
+
Прямим транзитивним замиканням деякої вершини v Т (v )
i
i
є об'єднання самої вершини v з прямим відображенням 1-го
i
порядку, 2-го порядку і т.д., тобто
+2
+1
+
Т (v )={v }Г (v )Г (v )… . (2.3)
i
i
i
i
Багатозначні відображення знаходяться до тих пір, поки в
них добавляються нові вершини.
Приклад 2.3. Знайти пряме транзитивне замикання для
вершини v графа, зображеного на рис. 2.1.
2
Розв'язок.

+1
Г (v )={v };
3
2
27