Составители:
Рубрика:
38
Ìàòðèöà ||S||
2
ïîêàçûâàåò, êàêèå ñóùåñòâóþò ïóòè äëèíû 2 èëè ìåíü-
øå. Ïîñêîëüêó ||S||
4
= ||S||
8
, ïîñòîëüêó ||S||
4
ïîêàçûâàåò, êàêèå âåðøèíû â
ãðàôå ñâÿçàíû ïóòÿìè.
2.1.2. Îïèñàíèå ìàøèííîãî àëãîðèòìà çàäà÷è
î ñóùåñòâîâàíèè ïóòåé â ãðàôå
Âîçìîæíûé âàðèàíò àëãîðèòìà çàäà÷è îïðåäåëåíèÿ ñóùåñòâîâàíèÿ
ïóòåé â ãðàôå ìîæåò âêëþ÷àòü ñëåäóþùèå øàãè.
1. Ââåñòè áóëåâó ìàòðèöó ñìåæíîñòè (S) è åå ðàçìåð (n).
2.Ñêîïèðîâàòü ìàòðèöó S â ðàáî÷óþ ìàòðèöó R (R=S), ñáðîñèòü ñ÷åò-
÷èê íîâûõ ìàòðèö (r=0).
3. Ñ ïîìîùüþ ïðîöåäóðû áóëåâîãî óìíîæåíèÿ ìàòðèö âû÷èñëèòü
íîâóþ ìàòðèöó R1=R ∧ S, âûâåñòè åå è óâåëè÷èòü ñ÷åò÷èê r = r+1.
4. Â öèêëàõ ïî ñòðîêàì (i) è ñòîëáöàì (j) ìàòðèöû ïîýëåìåíòíî ñðàâ-
íèâàòü R1
ij
è R
ij.
Åñëè R1
ij
≠ R
ij
, òî ñêîïèðîâàòü R=R1 è ïåðåéòè ê øàãó
3, èíà÷å âûâåñòè ñ÷åò÷èê äëèí ïóòåé L = 2
r1
êàê ðåçóëüòàò ðåøåíèÿ
çàäà÷è.
2.2. Ïåðåñ÷åò ïóòåé â îðãðàôå
Ïîñòàíîâêà çàäà÷è.  îòëè÷èå îò ïðåäûäóùåé çàäà÷è òðåáóåòñÿ âû-
÷èñëèòü êîëè÷åñòâî ïóòåé êîíêðåòíîé äëèíû (êàê ÷èñëî äóã) ìåæäó
êàæäîé ïàðîé âåðøèí ãðàôà.
2.2.1. Ìåòîä ðåøåíèÿ çàäà÷è ïåðåñ÷åòà ïóòåé
Ïåðåñ÷åò ðàçëè÷íûõ ïóòåé äëèíû r îñóùåñòâëÿåòñÿ ïîëó÷åíèåì ñòå-
ïåíåé èñõîäíîé ìàòðèöû ñìåæíîñòè ãðàôà (||S||) ñ ïîìîùüþ îïåðàöèè
ëèíåéíîé àëãåáðû îáû÷íîãî óìíîæåíèÿ äâóõ ìàòðèö:
||S|| äàåò ÷èñëî ïóòåé äëèíû 1,
||S||
2
= ||S||×||S|| äàåò ÷èñëî ïóòåé äëèíû 2.
||S||
3
=||S||
2
×||S|| äàåò ÷èñëî ïóòåé äëèíû 3,
.. . . . . . . . . . .
||S||
L
=||S||
L1
×||S|| äàåò ÷èñëî ïóòåé äëèíû L äëÿ êàæäîé ïàðû âåð-
øèí (v
i
,v
j
), ãäå
11 1 1
11 22
1
... , 2.
n
kk k k k
ij i j i j in nj im mj
m
SS SS S S S S Sk
−− − −
=
=⋅+⋅++⋅= ⋅ ≥
∑
Страницы
- « первая
- ‹ предыдущая
- …
- 36
- 37
- 38
- 39
- 40
- …
- следующая ›
- последняя »
