Составители:
Рубрика:
36
2. ÇÀÄÀ×È Î ÏÓÒßÕ Â ÎÐÃÐÀÔÅ
Àëãîðèòìû ýòèõ çàäà÷ èãðàþò áîëüøóþ ðîëü â òåîðèè ãðàôîâ, ïî-
ñêîëüêó ñ èõ ïîìîùüþ ðåøàþòñÿ ìíîãèå ïðèêëàäíûå çàäà÷è. Íàïðè-
ìåð, ýòî çàäà÷è î ñóùåñòâîâàíèè ïóòåé ìåæäó âåðøèíàìè ãðàôà, î êî-
ëè÷åñòâå ïóòåé ìåæäó äâóìÿ âåðøèíàìè, î ïóòè ñ íàèìåíüøèì ÷èñëîì
äóã ìåæäó âåðøèíàìè, î êðàò÷àéøåì ïóòè ìåæäó äâóìÿ âåðøèíàìè, î
äëèííåéøåì ïî âðåìåíè ïóòè îò íà÷àëüíîé âåðøèíû äî êîíå÷íîé âåð-
øèíû ãðàôà (òàê íàçûâàåìûé êðèòè÷åñêèé ïóòü), î äåðåâå êðàò÷àéøèõ
ðàññòîÿíèé è äðóãèå çàäà÷è.
2.1. Ñóùåñòâîâàíèå ïóòåé â îðãðàôå
Ïîñòàíîâêà çàäà÷è.  îðãðàôå òðåáóåòñÿ îïðåäåëèòü, ñóùåñòâóþò
ëè êàêèå-ëèáî ïóòè ìåæäó âåðøèíàìè ãðàôà.
Ïóñòü N
0
= {1,2,3, ...} ìíîæåñòâî íàòóðàëüíûõ ÷èñåë áåç íóëÿ. Äëÿ ãðàôà
G=(V, Ã) ïóòü ïîëîæèòåëüíîé äëèíû èç âåðøèíû v
i
â v
j
ñóùåñòâóåò, åñëè
0
(N)
Ã.
p
ji
pvv
∃∈ ∈
(2.1)
Åñëè ðàññìàòðèâàòü ïóòè äëèíû íîëü, òî (2.1) ìîæíî çàïèñàòü òàê:
ˆ
Ã
ji
vv
∈
, (2.2)
ò. å.v
j
âõîäèò â ìíîæåñòâî òðàíçèòèâíîãî çàìûêàíèÿ âåðøèíû v
i
.
2.1.1. Ìåòîä ðåøåíèÿ çàäà÷è î ïóòÿõ â ãðàôå
Áóëåâà ìàòðèöà ñìåæíîñòè ||S||
n×n
ãðàôà G=(V, Ã) áåç ïàðàëëåëüíûõ
äóã ïîêàçûâàåò, êàêèå ñóùåñòâóþò ïóòè äëèíû 1 (íàïðèìåð, ðèñ. 2.1),
ïðè ýòîì |V| = n.
Ïðèìåíèì ê ìàòðèöå ||S|| îïåðàöèè áóëåâûõ óìíîæåíèÿ è ñëîæåíèÿ.
Ïóñòü
||S||
2
= ||S||∧||S||,
||S||
4
= ||S||
2
∧||S||
2
,
.......................
Страницы
- « первая
- ‹ предыдущая
- …
- 34
- 35
- 36
- 37
- 38
- …
- следующая ›
- последняя »
