Page 16 - 4387

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

Знаходження досяжності та контрдосяжність на графах.

Матричний метод знаходження шляхів у графах

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

Мета роботи – засвоїти поняття досяжності та

контрдосяжності на графах.

Завдання роботи – побудувати матриці досяжності та

контрдосяжності для заданих діаграм графів. Знайти усі шляхи

заданої довжини матричним методом.

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

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

Досяжність у графі описується матрицею досяжності

R=[r ], i, j=1, 2, ..., n, де n – кількість вершин графа, а кожний
i,j
елемент визначається наступним чином:

1) r =1, якщо вершина v досяжна з v ;
j
i,j
i
2) r =0 у іншому випадку.
i,j
Множина вершин R(v ) графа G, досяжних із заданої
i
вершини v , складається з таких елементів v , для яких елемент r
i
i,j
j
в матриці досяжності дорівнює 1. Очевидно, що всі діагональні
елементи в матриці R дорівнюють 1, оскільки кожна вершина

досяжна з себе самої шляхом довжини 0. Оскільки пряме

+1
відображення 1-го порядку Г (v ) є множиною таких вершин v ,
j
i
які досяжні з вершини v з використанням шляхів довжини 1, то
i
+1
+2
+
множина Г (Г (v ))=Г (v ) складається з вершин, досяжних з
i
i
+k
вершини v з використанням шляхів довжини 2. Аналогічно Г (v )
i
i
15