Page 25 - 4336

2 БАГАТОЗНАЧНІ ВІДОБРАЖЕННЯ. ТРАНЗИТИВНІ

ЗАМИКАННЯ. ЗНАХОДЖЕННЯ ТРАНЗИТИВНИХ

ЗАМИКАНЬ ПО МАТРИЦІ СУМІЖНОСТІ

2.1 Багатозначні відображення

2.1.1 Прямі відображення

+1
Прямим відображенням 1-го порядку вершини v (Г (v )) є
i
i
множина таких вершин графа v , для яких існує дуга (v , v ), що
j
j
i
належить множині дуг графа, тобто
+1
Г (v )={v :  дуга (v , v )E}. (2.1)
j
i
i
j
Пряме відображення 2-го порядку вершини v – це пряме
i
відображення від прямого відображення 1-го порядку, тобто
+2
+1
+
Г (v )=Г (Г (v )).
i
i
Аналогічно можна записати для прямого відображення 3-го
і т.д. n-го порядку:
+
+1
+
+
+2
+3
Г (v )=Г (Г (v ))=Г (Г (Г (v )));
i
i
i
…
+
+n
Г (v )=Г (Г +(n-1) (v )).
i
i
Якщо відображення діє не на одну вершину, а на множину
+
вершин V ={v , v , …, v }, то під Г (V ) розуміють об'єднання
k
k
2
1
k
+
+
+
Г (v )Г (v )Г (v ).
1
k
2
Прямі багатозначні відображення знаходяться до тих пір,
поки в них або добавляються нові вершини, або не будуть
перелічені усі вершини графа.
Приклад 2.1. Знайти прямі відображення для вершини v
1
графа, зображеного на рис. 2.1.
Розв'язок.
+1
Г (v )={v , v };
2
3
1
25