Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 54 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

На рисунке 26,а представлена матрица смежности графа, изображенного на
рис.25. Результат возведения матрицы смежности в квадрат А
2
показан на рис.
26,б.
Так “1”, стоящая на пересечении второй строки и четвертого столбца,
говорит о существовании одного пути длиной 2 из вершины x
2
к вершине x
4
.
Действительно, как видим в графе на рис.25, существует такой путь: а
6
,a
5
. "2" в
матрице A
2
говорит о существовании двух путей длиной 2 от вершины x
3
к
вершине x
6
: a
8
,a
4
и a
10
,a
3
.
Аналогично для матрицы смежности возведенной в третью степень A
3
(рис.26,в) a
(3)
ik
равно числу путей длиной 3, идущих от x
i
к x
k
. Из четвертой строки
матрицы A
3
видно, что пути длиной 3 существуют: один из x
4
в x
4
(a
9
, a
8
, a
5
), один
из x
4
в x
5
(a
9
, a
10
, a
6
) и два пути из x
4
в x
6
(a
9
, a
10
, a
3
и a
9
, a
8
, a
4
). Матрица A
4
показывает существование путей длиной 4(рис.26,г).
Таким образом, если a
p
ik
является элементом матрицы A
p
,то a
p
ik
равно
числу путей (не обязательно орцепей или простых орцепей) длины p, идущих от x
i
к x
k
.
Если необходимо узнать не только о наличии путей, но и о вершинах графа
, входящих в эти пути, то следует вспомнить определения прямого и обратного
транзитивных замыканий. Так как T
+
(x
i
) - это множество вершин, в которые есть
пути из вершины x
i
, а T
-
(х
j
) -множество вершин, из которых есть пути в x
j
, то T
+
(x
i
)
∩ T
-
(x
j
) - множество вершин, каждая из которых принадлежит по крайней мере
x
1
x
2
x
3
x
4
x
5
x
6
x
1
0 1 0 0 0 1
x
2
0 0 0 0 1 1
A= x
3
0 1 0 0 1 1
x
4
0 0 1 0 0 0
x
5
0 0 0 1 0 1
x
6
0 0 0 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
x
1
0 0 0 0 1 1
x
2
0 0 0 1 0 1
A
2
=x
3
0 0 0 1 1 2
x
4
0 1 0 0 1 1
x
5
0 0 1 0 0 0
x
6
0 0 0 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
x
1
0 0 0 1 0 1
x
2
0 0 1 0 0 0
A
3
= x
3
0 0 1 1 0 1
x
4
0 0 0 1 1 2
x
5
0 1 0 0 1 1
x
6
0 0 0 0 0 0
x
1
x
2
x
3
x
4
x
5
x
6
x
1
0 0 1 0 0 0
x
2
0 1 0 0 1 1
A
4
=x
3
0 1 1 0 1 1
x
4
0 0 0 1 1 1
x
5
0 0 0 1 1 2
x
6
0
0
0
0
0
0
Рис. 26. Нахождение путей 
         На рисунке 26,а представлена матрица смежности графа, изображенного на
рис.25. Результат возведения матрицы смежности в квадрат А2 показан на рис.
26,б.


               x1   x2   x3   x4   x5   x6                 x1   x2   x3   x4    x5   x6
          x1   0    1    0    0    0    1            x1    0    0    0    0     1    1
          x2   0    0    0    0    1    1            x2    0    0    0    1     0    1
    A=    x3   0    1    0    0    1    1      A2=   x3    0    0    0    1     1    2
          x4   0    0    1    0    0    0            x4    0    1    0    0     1    1
          x5   0    0    0    1    0    1            x5    0    0    1    0     0    0
          x6   0    0    0    0    0    0            x6    0    0    0    0     0    0
               x1   x2   x3   x4   x5   x6                 x1   x2   x3   x4    x5   x6
       x1      0    0    0    1    0    1            x1    0    0    1    0     0    0
       x2      0    0    1    0    0    0            x2    0    1    0    0     1    1
   A3= x3      0    0    1    1    0    1     A4=    x3    0    1    1    0     1    1
       x4      0    0    0    1    1    2            x4    0    0    0    1     1    1
       x5      0    1    0    0    1    1            x5    0    0    0    1     1    2
       x6      0    0    0    0    0    0            x6    0    0    0    0     0    0

                               Рис. 26. Нахождение путей


         Так “1”, стоящая на пересечении второй строки и четвертого столбца,
говорит о существовании одного пути длиной 2 из вершины x2 к вершине x4.
Действительно, как видим в графе на рис.25, существует такой путь: а6,a5. "2" в
матрице A2 говорит о существовании двух путей длиной 2                         от вершины x3 к
вершине x6 : a8,a4 и a10,a3.
         Аналогично для матрицы смежности возведенной в третью степень A3
(рис.26,в) a(3)ik равно числу путей длиной 3, идущих от xi к xk. Из четвертой строки
матрицы A3 видно, что пути длиной 3 существуют: один из x4 в x4(a9, a8, a5), один
из x4 в x5(a9, a10, a6) и два пути из x4 в x6(a9, a10, a3 и a9, a8, a4). Матрица A4
показывает существование путей длиной 4(рис.26,г).
         Таким образом, если apik является элементом матрицы Ap ,то apik равно
числу путей (не обязательно орцепей или простых орцепей) длины p, идущих от xi
к xk.
         Если необходимо узнать не только о наличии путей, но и о вершинах графа
, входящих в эти пути, то следует вспомнить определения прямого и обратного
транзитивных замыканий. Так как T+(xi) - это множество вершин, в которые есть
пути из вершины xi, а T-(хj) -множество вершин, из которых есть пути в xj, то T+(xi)
∩ T-(xj) - множество вершин, каждая из которых принадлежит по крайней мере

Страницы