Page 39 - 4336

Аналогічно для матриці суміжності, зведеної до третього

3
3
ступеня A (рис. 3.2, г), елементи a рівне числу шляхів
i,j
3
завдовжки 3, що йдуть від v до v . З четвертого рядка матриці A
i
j
випливає, що існують наступні шляхи завдовжки 3:
 один з v у v – v v v v ;
4 3 5 4
4
4
 один з v у v – v v v v ;
4 3 2 5
5
4
 два з v в v – v v v v та v v v v .
4
4 3 5 6
6
4 3 2 6
4
Матриця A (рис. 3.2, д) показує існування шляхів завдовжки
k
k
k
4. Таким чином, якщо a є елементом матриці A , то a рівне
i,j
i,j
числу шляхів довжини k, що ведуть від вершини v до v .
i
j
Якщо необхідно дізнатися про вершини графа, що входять в
ці шляхи, то слід пригадати визначення прямого і зворотного
+
транзитивних замикань. Оскільки Т (v ) – це множина вершин, в
i
-
які існують шляхи з вершини v , а Т (v ) – множина вершин, з яких
j
i
+
-
існують шляхи в v , то Т (v )Т (v ) – множина вершин, кожна з
j
i
j
яких належить, принаймні, одному шляху, що йде від v до v . Ці
i
j
вершини називаються істотними або невід'ємними щодо двох
кінцевих вершин v та v . Усі решта вершин графа називаються
j
i
неістотними або надмірними, оскільки їх видалення не впливає
на шляхи від v до v .
i
j
Так, для графу на рис. 3.2, а. знаходження вершин, що
входять в шлях, наприклад з вершини v у вершину v , зводиться
4
2
+
+
-
-
до знаходження множин Т (v ), Т (v ) та їх перетину Т (v )Т (v ):
4
2
2
4
+
Т (v )={v , v , v , v , v },
3
4
2
2
5
6
-
Т (v )={v , v , v , v , v },
1
4
2
3
4
5
-
+
Т (v )Т (v )={v , v , v , v }.
3
4
5
2
4
2
Таким чином, вершини v , v , v , v входять до усіх шляхів,
5
4
2
3
що ведуть з вершини v у вершину v .
2
4

39