Page 34 - 4336

3 ДОСЯЖНІСТЬ І КОНТРДОСЯЖНІСТЬ НА ГРАФАХ.

МАТРИЧНИЙ МЕТОД ЗНАХОДЖЕННЯ ШЛЯХІВ У

ГРАФАХ

Задач, в яких використовується поняття досяжності, досить
багато. При розгляді графа в якості моделі деякої дорожньої

мережі можна поставити питання, чи можливо від перехрестя v
i
досягти перетин вулиць v , тобто чи існує шлях, що веде від
j
вершини v до вершини v . Якщо такий шлях існує, то говорять,
i
j
що вершина v досяжна з вершини v .
i
j

3.1 Досяжність на графах

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

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,j
j
i
в матриці досяжності дорівнює 1. Очевидно, що всі діагональні
елементи в матриці R дорівнюють 1, оскільки кожна вершина

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

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

34