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

   4. Ïóòè è ìàðøðóòû â ãðàôàõ
   Ñóùåñòâóåò áîëüøîå ðàçíîîáðàçèå çàäà÷, ñâÿçàííûõ ñ ïó-
òÿìè è ìàðøðóòàìè â ãðàôå, íà÷èíàÿ îò ñòàíäàðòíûõ çàäà÷
íà ñóùåñòâîâàíèå, ïåðåñ÷åò è ïåðå÷èñëåíèå è êîí÷àÿ çàäà÷à-
ìè ïîèñêà ïóòåé, îòâå÷àþùèõ îïðåäåëåííûì òðåáîâàíèÿì. Òà-
êèìè òðåáîâàíèÿìè ìîãóò áûòü: òðåáîâàíèÿ ìàêñèìàëüíîñòè
(ìèíèìàëüíîñòè) äëèíû, ïðîïóñêíîé ñïîñîáíîñòè èëè íàäåæ-
íîñòè ïóòè; òðåáîâàíèÿ ê ìíîæåñòâó âåðøèí (ðåáåð), ïðèíàä-
ëåæàùèõ (íå ïðèíàäëåæàùèõ) ïóòè, è ò. ï. Ïðè ýòîì ñàìè ãðà-
ôû ìîãóò èìåòü ðàçëè÷íûå ñâîéñòâà, íàïðèìåð, áûòü èëè íå
áûòü îðèåíòèðîâàííûìè, öèêëè÷åñêèìè, âçâåøåííûìè è ò. ä.
Íàêîíåö, îäèí è òîò æå ãðàô ìîæåò áûòü îïèñàí ïî-ðàçíîìó.
Ïîýòîìó äàæå îäíà è òà æå çàäà÷à äëÿ ðàçëè÷íûõ ïî ñâîèì
õàðàêòåðèñòèêàì è ñïîñîáó îïèñàíèÿ ãðàôîâ ìîæåò ðåøàòüñÿ
ïî-ðàçíîìó.


   4.1. Ñóùåñòâîâàíèå ïóòåé
   Ýòà çàäà÷à ýêâèâàëåíòíà çàäà÷å íà äîñòèæèìîñòü â îðãðà-
ôå, ðåøåíèå êîòîðîé ðàññìîòðåíî â ðàçä. 2. Äåéñòâèòåëüíî,
ìàòðèöà äîñòèæèìîñòè ïîëíîñòüþ îïðåäåëÿåò íàëè÷èå èëè
îòñóòñòâèå ïóòè äëÿ ëþáîé óïîðÿäî÷åííîé ïàðû âåðøèí. Ïî-
ýòîìó îãðàíè÷èìñÿ ïðèìåðîì.
   Íà ðèñ. 4.1 èçîáðàæåíû ãðàô G è åãî ìàòðèöà äîñòèæè-
ìîñòè R , ïîëó÷åííàÿ îäíèì èç ðàíåå ðññìîòðåííûõ ñïîñîáîâ.
             dr
                                           a   b   c   d   e
           @ 6                          
                                        a 1    1   1   1   1
        ar - rb@R rc
                 @                      b 1   1   1   1   1
    G
         @
         I@                        R = c
                                         1    1   1   1   1.
            @?r                        d 1    1   1   1   1
             e                          e 1    1   1   1   1
                        Ðèñ. 4.1

   Ïðîñòàÿ ïðîâåðêà óáåæäàåò, ÷òî äëÿ ëþáîé ïàðû âåðøèí
â ãðàôå èìååòñÿ õîòÿ áû îäèí ïóòü. Èìåííî ýòî è ñëåäóåò èç
ïðèâåäåííîé ìàòðèöû, ïîñêîëüêó âñå åå ýëåìåíòû ðàâíû 1.


                               70