Составители:
Рубрика:
37
òîãäà
1111 11
22 2 2 2 2 2
11 22
SS S S S S S,
rr r r r r r
ij i j i j in nj
−−−− −−
=∧∨∧∨∨∧
L
ãäå i, j=1(1)n (èçìåíåíèå îò 1 ñ øàãîì 1 äî n); ∧ áóëåâî óìíîæåíèå;
∨ áóëåâî ñëîæåíèå; r íîìåð íîâîé áóëåâîé ìàòðèöû.
Óìíîæåíèå ïðîäîëæàåòñÿ äî òåõ ïîð, ïîêà íå ñðàâíÿþòñÿ äâå ïîñëå-
äíèå ìàòðèöû
1
22
SS
rr−
=
. Òîãäà íåíóëåâûå ýëåìåíòû ìàòðèöû
1
2
S
r
−
ïîêàæóò, êàêèå âåðøèíû â ãðàôå ñâÿçàíû êàêèìè-ëèáî ïóòÿìè.
Ï ð è ì å ð
Íà ðèñ.2.1 èçîáðàæåí ãðàô è åãî ìàòðèöà ñìåæíîñòè ||S||, à íà ðèñ.2.2
ïðåäñòàâëåíû ìàòðèöû ||S||
2
, ||S||
4
, ||S||
8
.
||S||
2
: ||S||
4
: ||S||
8
:
)*+,-.
)
*
+
,
-
.
A
F
E
D
C
B
Ðèñ. 2.1. Ãðàô è åãî áóëåâà ìàòðèöà ñìåæíîñòè
)*+,-.
)
*
+
,
-
.
)*+,-.
)
*
+
,
-
.
)*+,-.
)
*
+
,
-
.
Ðèñ. 2.2. Áóëåâû ìàòðèöû ñóùåñòâîâàíèÿ ïóòåé
ìåæäó âåðøèíàìè ãðàôà
||S||
6×6
:
Страницы
- « первая
- ‹ предыдущая
- …
- 35
- 36
- 37
- 38
- 39
- …
- следующая ›
- последняя »
