Page 26 - 4336

Рисуунок 2.1.

+1
+
+
+22
Г (v )=Г ((Г (v ))==Г (v , vv )={v }{v }={vv , v };
5
3
5
1
2
3
1
3
+2
+3
+
+
Г (v )=Г ((Г (v ))==Г (v , vv )={v }{v , v }={v , v ,, v }.
1
2
1
5
1
5
1
2
5
3
+3
Осскільки у відоображенння Г (vv ) не добавиллось ноових
1
вершинн (вершиини v , v та v уже роозглядаллись на попереддніх
2
1
55
кроках)), то ппошук прямих відобрражень для веершини v
1
припиняяється.
2.11.2 Звороотні віддображеення
Звооротнимм відобрраженняям 1-го порядкуу для веершини v є
i
множинна такихх вершинн графа v , для яких існнує дугаа (v , v ), що
i
j
j
належитть множжині дуг графа, ттобто
-1
Г (vv )={v :  дуга (v , v )E}. ( (2.2)
j
i
i
j j
Зворотні відобрааження 2-го, 3-го та n-гоо поряядку
визначааються ннаступниим чиномм:
-
-22
-1
Г (v )=Г (ГГ (v ));
i
i
-33
-
-
-2
-1
-
Г (v )=Г (ГГ (v ))=ГГ (Г (Г ((v )));
i
i
i
…
-
-nn
Г (v )=Г (ГГ -(n-1) (v ))).
i
i
Яккщо відоображення діє нне на однну вершшину, а нна множжину
- -
вершинн V ={v , v , …,, v }, тоо під Г (V ) роззуміють об'єднаання
1
k
2
k
k
-
-
-
Г (v )Г (v )Г (v ).
1
2
k k
26