Page 7 - 4387

Якщо відображення діє не на одну вершину, а на множину

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

Розв'язок.
+1
Г (v )={v , v };
3
2
1
+
+1
+2
Г (v )=Г (Г (v ))=
1
1
+
=Г (v , v )={v }∪{v }={v , v };
3
3
3
5
2
5
+2
+
+3
Г (v )=Г (Г (v ))=
1
1
+
=Г (v , v )={v }∪{v , v }={v , v , v }.
2
5
5
3
2
1
1
5
+3
Оскільки у відображення Г (v )
1
не добавилось нових вершин Рисунок 1.1.
(вершини v , v та v уже розглядались
2
5
1
на попередніх кроках), то пошук прямих відображень для
вершини v припиняється.
1
Зворотним відображенням 1-го порядку для вершини v є
i
множина таких вершин графа v , для яких існує дуга (v , v ), що
j
i
j
належить множині дуг графа, тобто
-1
Г (v )={v : ∃ дуга (v , v )∈E}. (1.2)
i
j
j
i
Зворотні відображення 2-го, 3-го та n-го порядку
визначаються наступним чином:
-
-2
-1
Г (v )=Г (Г (v ));
i
i
-3
-
-
-2
-
-1
Г (v )=Г (Г (v ))=Г (Г (Г (v )));
i
i
i
…
6