Page 18 - 4387

R(v )={v }∪{v }∪{v }={v , v , v };
4
3
5
3
4
3
5
R(v )={v }∪{v }={v , v };
4
5
5
4
4
R(v )={v }∪{v }={v };
5
5
5
5
R(v )={v }∪{v , v }∪{v , v }∪{v , v , v }={v , v , v , v , v };
5
3
6
7
6
7
3
4
4
3
5
7
6
6
R(v )={v }∪{v , v }∪{v , v , v }∪{v , v }={v , v , v , v , v }.
4
6
4
3
5
7
6
5
3
7
6
4
7
7
Матриця досяжності R має вигляд, як показано на рис. 2.1 б.
Матриця контрдосяжності Q=[q ], i, j=1, 2, ..., n, де n –
i,j
кількість вершин графа, а кожний елемент визначається
наступним чином:
1) q =1, якщо з вершина v можна досягти вершину v ;
j
i
i,j
2) q =0 у іншому випадку.
i,j
Контрдосяжною множиною Q(v ) є множина таких вершин,
i
що з будь-якої вершини цієї множини можна досягти вершину v .
i
Аналогічно побудові досяжної множини R(v ) можна записати
i
вираз для Q(v ):
i
-k
-2
-1
Q(v )={v }∪Г (v ) ∪Г (v ) ∪... ∪Г (v ). (2.2)
i
i
i
i
i
Таким чином, Q(v ) – це є не що інше, як зворотне
i
-
транзитивне замикання вершини v , тобто Q(v )=Т (v ). З визначень
i
i
i
очевидно, що стовпець v матриці Q(v ) (в якому q =1, якщо
i
i,j
i
v ∈Q(v ), і q =0 в іншому випадку) співпадає з рядком v матриці
i
j
i,j
i
T
T
R(v ), тобто Q(v )=R(v ) , де R(v ) – матриця, транспонована до
i
i
i
i
матриці досяжності R(v ).
i
Матриця контрдосяжності для графа, наведеного на рис. 2.1
а, показана на рис. 2.2.
Матриця суміжності повністю визначає структуру графа.
Зведемо матрицю суміжності в квадрат за правилами математики.
2
Кожен елемент матриці А визначається за формулою:

17