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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

R ( x
6
) = { x
6
} ∪ { x
3
, x
7
} ∪ { x
4
, x
6
} ∪ { x
3
, x
5
, x
7
} ∪ { x
4
, x
5
, x
6
} = { x
3
, x
4
, x
5
,
x
6
,x
7
},
R ( x
7
) = { x
7
} ∪ { x
4
, x
6
} ∪ { x
3
, x
5
, x
7
} ∪ { x
4
, x
5
, x
6
} = { x
3
, x
4
, x
5
, x
6
, x
7
}.
Матрица достижимостей имеет вид ,как показано на рис. 12,в. .Матрицу
достижимостей можно построить по матрице смежности (рис.12,б), формируя множества
T
+
( x
i
) по методу, описанному в п.2.2.3, для каждой вершины x
i
.
Матрица контрдостижимостей Q = [ q
ij
], i, j=1,2, ... n, где n-число вершин графа,
определяется следующим образом:
q
ij
=1, если из вершины x
j
можно достичь вершину x
i
,
q
ij
=0, в противном случае.
Контрдостижимым множеством Q ( x
i
) является множество таких вершин, что из любой
вершины этого множества можно достичь вершину x
i
. Аналогично
построению достижимого множества R ( x
i
) можно записать выражение для
Q ( x
i
):
Q ( x
i
) = { x
i
} ∪ Г
-1
( x
i
) ∪ Г
-2
( x
i
) ∪. .. ∪ Г
-p
( x
i
).
Таким образом, видно, что Q ( x
i
) - это есть не что иное как обратное
транзитивное замыкание вершины x
i
, т.е. Q ( x
i
) = Т
-
( x
i
). Из определений
очевидно, что столбец x
i
матрицы Q (в котором q
ij
=1, если x
j
∈ Q ( x
i
), и q
ij
=0 в
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
1
1 1 0 1 1 0 0
x
2
0 1 0 1 1 0 0
x
3
0 0 1 1 1 0 0
R= x
4
0 0 0 1 1 0 0
x
5
0 0 0 0 1 0 0
x
6
0 0 1 1 1 1 1
x
7
0 0 1 1 1 1 1
â)
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
1
1000000
x
2
1100000
x
3
0010011
Q=
x
4
1111011
x
5
1111111
x
6
0000011
x
7
0000011
ã)
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
1
0 1 0 0 1 0 0
x
2
0 1 0 1 0 0 0
x
3
0 0 0 1 0 0 0
x
4
0 0 0 0 1 0 0
x
5
0 0 0 0 1 0 0
x
6
0 0 1 0 0 0 1
x
7
0 0 0 1 0 1 0
Рис 12. а)- граф; б) - матрица смежности; с) – матрица
достижимости; г) - матрица контрдостижимости.
a)
b) 
                 R ( x6 ) = { x6 } ∪ { x3, x7 } ∪ { x4, x6 } ∪ { x3, x5, x7 } ∪ { x4, x5, x6 } = { x3, x4, x5,
       x6,x7},
                 R ( x7 ) = { x7 } ∪ { x4, x6 } ∪ { x3, x5, x7 } ∪ { x4, x5, x6 } = { x3, x4, x5, x6, x7 }.

                               x2                        x1   x2    x3       x4   x5        x6    x7
 x1
                                                    x1   0    1     0        0    1         0     0
                                          x3        x2   0    1     0        1    0         0     0
                                                    x3   0    0     0        1    0         0     0
                     x6                             x4   0    0     0        0    1         0     0
  x7                                                x5   0    0     0        0    1         0     0
                                                    x6   0    0     1        0    0         0     1    b)
               x5                              x4   x7   0    0     0        1    0         1     0
                                a)


          x1   x2   x3    x4   x5    x6   x7                  x1   x2   x3   x4   x5   x6    x7
   x1     1    1    0     1    1     0    0            x1     1    0    0    0    0    0     0
   x2     0    1    0     1    1     0    0            x2     1    1    0    0    0    0     0
   x3     0    0    1     1    1     0    0            x3     0    0    1    0    0    1     1
R= x4     0    0    0     1    1     0    0         Q= x4     1    1    1    1    0    1     1
   x5     0    0    0     0    1     0    0            x5     1    1    1    1    1    1     1
   x6     0    0    1     1    1     1    1            x6     0    0    0    0    0    1     1
   x7     0    0    1     1    1     1    1            x7     0    0    0    0    0    1     1
                     â) б) - матрица смежности; с) – матрица ã)
        Рис 12. а)- граф;
        достижимости; г) - матрица контрдостижимости.


                 Матрица достижимостей              имеет      вид ,как показано на рис. 12,в. .Матрицу
       достижимостей можно построить по матрице смежности (рис.12,б), формируя множества
       T+ ( xi ) по методу, описанному в п.2.2.3, для каждой вершины xi.
                 Матрица контрдостижимостей Q = [ qij ], i, j=1,2, ... n, где n-число вершин графа,
       определяется следующим образом:
                 qij=1, если из вершины xj можно достичь вершину xi,
                   qij=0, в противном случае.
       Контрдостижимым множеством Q ( xi ) является множество таких вершин, что из любой
       вершины этого множества можно достичь вершину xi. Аналогично
             построению достижимого множества R ( xi ) можно записать выражение для
       Q ( xi ):
                 Q ( xi ) = { xi } ∪ Г-1 ( xi ) ∪ Г-2 ( xi ) ∪. .. ∪ Г-p ( xi ).
                 Таким образом, видно, что Q ( xi ) - это есть не что иное как обратное
       транзитивное замыкание вершины xi, т.е. Q ( xi ) = Т- ( xi ). Из определений
       очевидно, что столбец xi матрицы Q (в котором qij=1, если xj ∈ Q ( xi ), и qij=0 в

Страницы