Элементы теории графов. Домнин Л.Н. - 118 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

P
(l)
v
n
O(n
3
).
P
(l)
v
(l+1)<n,
v.
G
A, v = a.
G
s
a
s
b
s
c
s
d
s
e
s
f
- -
?
?
6
-
6
*
a b c d e f
A =
a
b
c
d
e
f
0 1 0 0 0 0
0 0 1 0 1 0
1 0 0 1 0 0
0 0 1 0 0 1
0 0 1 1 0 0
1 1 1 0 0 0
P
(0)
a
P
0
a b c d e f
P
0
=
a
b
c
d
e
f
0 b 0 0 0 0
0 0 c 0 e 0
a 0 0 d 0 0
0 0 c 0 0 f
0 0 c d 0 0
a b c 0 0 0
, P
(0)
a
=
0
0
1
0
0
1
.
                                                                                (l)
   Ðàáîòà òîëüêî ñ îäíèì ñòîëáöîì ìàòðèöû Pv ïîçâîëÿ-
åò â n ðàç óìåíüøèòü òðóäîåìêîñòü âû÷èñëåíèé. Ïîñëåäíÿÿ,
îäíàêî, è â ýòîì ñëó÷àå îñòàåòñÿ âåñüìà ñóùåñòâåííîé O(n3 ).
   Äîïîëíèòåëüíûé âûèãðûø ìîæíî ïîëó÷èòü, åñëè íà êàæ-
                                               (l)
äîì øàãå ïîñëå ïîëó÷åíèÿ î÷åðåäíîãî ñòîëáöà Pv èñêëþ÷àòü
èç íåãî ïðîèçâåäåíèÿ ñ ïîâòîðÿþùèìèñÿ ñîìíîæèòåëÿìè, à
òàêæå ïðîèçâåäåíèÿ, â êîòîðûõ õîòü îäèí èç ýëåìåíòîâ ñîâïà-
äàåò ñ êîíöåâîé âåðøèíîé ñîîòâåòñòâóþùåé öåïè. Êðîìå òîãî,
öåëåñîîáðàçíî "îáíóëÿòü" è äèàãîíàëüíûé ýëåìåíò ñòîëáöà,
òàê êàê ïîñëåäíèé îòðàæàåò ëèøü öèêëû äëèíû (l+1)

Страницы