Составители:
Рубрика:
39
Çíà÷åíèå L îïðåäåëÿåòñÿ â ïðåäûäóùåé çàäà÷å ñóùåñòâîâàíèÿ ïóòåé
â ãðàôå êàê ðåçóëüòèðóþùåå çíà÷åíèå ñòåïåíè ìàòðèöû, ïîñëå êîòîðîé
íà÷èíàåòñÿ ïîâòîðåíèå ïóòåé.  ïðåäûäóùåì ïðèìåðå L=4.
Ï ð è ì å ð
Äëÿ ãðàôà (ðèñ.2.1) ìàòðèöû (ðèñ.2.3) äàþò ÷èñëî ïóòåé äëèí ñîîò-
âåòñòâåííî k=1,2,3,4. Íàïðèìåð, èìååòñÿ ïÿòü ïóòåé äëèíû 3 îò B ê D
(ñì. ||S||
3
), äåâÿòü ïóòåé äëèíû 4 îò B ê D (ñì. ||S||
4
).
2.2.2. Îïèñàíèå ìàøèííîãî àëãîðèòìà
ïåðåñ÷åòà ïóòåé â ãðàôå
Àëãîðèòì ïåðåñ÷åòà äëèí ïóòåé ìîæíî îïèñàòü ñëåäóþùèì îáðàçîì:
1. Ââåñòè ìàòðèöó ñìåæíîñòè (S), åå ðàçìåð (n) è êîíå÷íóþ äëèíó
ïóòè (L), ïîëó÷åííóþ â ïðåäûäóùåé çàäà÷å.
1. Ñêîïèðîâàòü S â ðàáî÷óþ ìàòðèöó R.
2. Â öèêëå k=2(1)L èñïîëüçîâàòü ïðîöåäóðó óìíîæåíèÿ äâóõ ìàòðèö
(R1=R×S), âûâîäèòü ìàòðèöó R1 êàê ðåçóëüòàò è êîïèðîâàòü R1 â R.
||S||: ||S||
2
:
||S||
3
: ||S||
4
:
)*+,-.
)
*
+
,
-
.
)*+,-.
)
* !
+
,
-
.
)*+,-.
) !
* !!#!$
+
,
- !
.
)*+,-.
) ! !$" %
*! # #'&
+
, !
- !#!
.
Ðèñ. 2.3. Ìàòðèöû ïåðåñ÷åòà äëèí ïóòåé ìåæäó âåðøèíàìè ãðàôà
Страницы
- « первая
- ‹ предыдущая
- …
- 37
- 38
- 39
- 40
- 41
- …
- следующая ›
- последняя »
