Page 6 - 4387

ЛАБОРАТОРНА РОБОТА № 1

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

замикань

1.1 Мета і завдання роботи роботи

Мета роботи – засвоїти поняття багатозначного

відображення та транзитивного замикання.
Завдання роботи – знайти багатозначні відображення та

транзитивні замикання для заданих діаграм графів. Знайти
транзитивні замикання для заданої вершини за матрицею

суміжності графа.
Тривалість лабораторної роботи – 4 год. (2 пари).

1.2 Основні теоретичні положення

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