Единое окно доступа к образовательным ресурсам

Дискретная математика: Основы теории графов и алгоритмизация задач: Учебное пособие

Голосов: 13

Рассмотрены основные определения и понятия теории графов, необходимые для решения некоторых прикладных задач дискретной математики (определение оптимальных расстояний между множеством объектов, поиск критического пути в задаче сетевого планирования и управления, выбор предпочтительных вариантов системы по множеству критериев). Обсуждаются подходы к разработке компьютерных алгоритмов задач па основе моделей теории графов.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
        Äâîè÷íûì äåðåâîì íàçûâàåòñÿ ïðàäåðåâî, åñëè (∀vi∈V)|Ã{vi}|= 2 èëè
0, ò. å. èç êàæäîé âåðøèíû èñõîäèò äâå äóãè, åñëè ýòî íå âèñÿ÷àÿ âåð-
øèíà (ðèñ. 1.19,á).
    Âåòâÿùèìñÿ íàçûâàåòñÿ ãðàô, âñå ñâÿçíûå êîìïîíåíòû êîòîðîãî ÿâ-
ëÿþòñÿ ïðàäåðåâüÿìè (ðèñ 1.19,â).
                1.4.6. Îðãðàôû è áèíàðíûå îòíîøåíèÿ
    Ïóñòü V – ìíîæåñòâî îáúåêòîâ, ïîäëåæàùèõ èññëåäîâàíèþ ïóòåì èõ
ïîïàðíîãî (áèíàðíîãî) ñðàâíåíèÿ. Ìíîæåñòâî âñåõ óïîðÿäî÷åííûõ ïàð
v,v'∈V îáîçíà÷àåòñÿ V×V (äåêàðòîâî ïðîèçâåäåíèå). Ïîäìíîæåñòâî
B⊆V×V íàçûâàåòñÿ áèíàðíûì îòíîøåíèåì, ò. å. (v,v')∈B.
    Áèíàðíîå îòíîøåíèå íàçûâàåòñÿ: ðåôëåêñèâíûì, åñëè (v,v')∈B; àíòè-
ðåôëåêñèâíûì, åñëè (v,v)∉B; ñèììåòðè÷íûì, åñëè (v,v')∈B → (v',v)∈B; àí-
òèñèììåòðè÷íûì, åñëè (v,v')∈B è (v',v)∈B → v=v'; àñèììåòðè÷íûì, åñëè
(v,v')∈B → (v',v)∉B; òðàíçèòèâíûì, åñëè (v,v')∈B è (v',v'')∈B → (v,v'')∈B;
ëèíåéíûì, åñëè (v,v')∈B èëè (v',v)∈B.
    Áèíàðíûå îòíîøåíèÿ ëåãêî ïðåäñòàâëÿþòñÿ â âèäå îðãðàôà, ïðè ýòîì
âåðøèíû ãðàôà ñîîòâåòñòâóþò îáúåêòàì ñðàâíåíèÿ vi∈V, à äóãè îòîáðà-
æàþò áèíàðíîå îòíîøåíèå ìåæäó îáúåêòàìè. Åñëè (v, v')∈B, òî ïðîâî-
äèòñÿ äóãà èç v â v', ïðè ýòîì v – íà÷àëî, à v' – êîíåö äóãè, ò. å. äóãà
îïðåäåëÿåòñÿ ïàðîé (v,v'). Êàê ïîêàçàíî âûøå, ïîñëåäîâàòåëüíîñòü äóã
(vi-1, vi), i=1, 2, …, n, ñîñòàâëÿåò ïóòü â ãðàôå. Êîíå÷íûé ïóòü, ó êîòîðî-
ãî v0=vn, îáðàçóåò êîíòóð. Äóãà (v, v) íàçûâàåòñÿ ïåòëåé (îòðàæàåò ðåô-
ëåêñèâíîå îòíîøåíèå).
    Â äåéñòâèòåëüíîñòè, ëþáîå áèíàðíîå îòíîøåíèå Â, îïðåäåëåííîå
íà ìíîæåñòâå V, ìîæåò áûòü ïðåäñòàâëåíî îðèåíòèðîâàííûì ãðàôîì,
âåðøèíû êîòîðîãî ñîîòâåòñòâóþò ýëåìåíòàì V. Ãðàô ïîëíîñòüþ îïèñû-
âàåò îòíîøåíèå ïåðå÷èñëåíèåì âñåõ ñâÿçíûõ ýëåìåíòîâ. Òàêèì îáðà-
çîì, îðãðàô, â íåêîòîðîì ñìûñëå, ÿâëÿåòñÿ èñ÷åðïûâàþùåé ôîðìîé ïðåä-
ñòàâëåíèÿ îòíîøåíèÿ, ò. å. îí ïîëíîñòüþ ïåðå÷èñëÿåò âñå ïàðû, äëÿ
êîòîðûõ ðàññìàòðèâàåìîå îòíîøåíèå èìååò ìåñòî.
    Ðàññìîòðåííûå âûøå îïèñàíèÿ ñïåöèàëüíûõ êëàññîâ îðãðàôîâ, íå
èìåþùèõ ïàðàëëåëüíûõ ðåáåð, àíàëîãè÷íû òåðìèíîëîãèè áèíàðíûõ îò-
íîøåíèé. Äåéñòâèòåëüíî, ðåôëåêñèâíûì íàçûâàåòñÿ ãðàô, èìåþùèé
ïåòëþ (v, v) â êàæäîé âåðøèíå, ñèììåòðè÷åñêèì ÿâëÿåòñÿ ãðàô, â êîòî-
ðîì êàæäîé äóãå u=(v, w), ñîîòâåòñòâóåò âñòðå÷íàÿ äóãà u'=(w, v), òðàí-
çèòèâíûì íàçûâàåòñÿ ãðàô, â êîòîðîì èç ñóùåñòâîâàíèÿ äóã u1=(v, v') è
u2=(v', v'') ñëåäóåò ñóùåñòâîâàíèå äóãè u3=(v, v'').
                                                                         31


                      1.4.7. Òðàíçèòèâíûå çàìûêàíèÿ
   Äëÿ òîãî ÷òîáû äàòü ôîðìàëèçîâàííîå îïðåäåëåíèå ñèëüíî ñâÿçíîãî
ãðàôà, èãðàþùåãî âàæíóþ ðîëü ïðè ðåøåíèè ìíîãèõ çàäà÷ ìåòîäàìè
òåîðèè ãðàôîâ, ââåäåì ïîíÿòèå òðàíçèòèâíîãî è îáðàòíîãî òðàíçèòèâ-
íîãî çàìûêàíèÿ.
   Âûøå ìû îáîçíà÷èëè ÷åðåç Ãv ïîäìíîæåñòâî ñìåæíûõ âåðøèí-êîí-
öîâ äóã, èìåþùèõ íà÷àëîì âåðøèíó v, à ÷åðåç Öv ïîäìíîæåñòâî ñìåæ-
íûõ âåðøèí–íà÷àëà äóã, èìåþùèõ êîíöîì âåðøèíó v.
   Îáîçíà÷èì ÷åðåç Ãnv ïîäìíîæåñòâî òåõ âåðøèí, â êîòîðûå ìîæíî
ïðèéòè èç âåðøèíû v, èñïîëüçóÿ ïóòè äëèíû n (èëè, áûòü ìîæåò, ìåíü-
øåé), à ÷åðåç Ö nv ïîäìíîæåñòâî òåõ âåðøèí, èç êîòîðûõ ìîæíî ïðèéòè
â âåðøèíó v, èñïîëüçóÿ ïóòè äëèíû n (èëè, âîçìîæíî, ìåíüøåé).
   Íàïðèìåð, äëÿ ãðàôà íà ðèñ.1.20,à èìååì:
      Ãv1={v2, v3}, Ãv2={v1, v4, v5}, Ãv3={v4}, Ãv4={v1}, Ãv5={v4};

      Ã2v1=Ã{Ãv1}=Ã{v2, v3}=Ãv2∪Ãv3={v1, v4, v5}∪{v4}={v1, v4, v5};

      Ã3v1=Ã{Ã2v1}=Ã{v1, v4, v5}=Ãv1∪Ãv4∪Ãv5=
      ={v2, v3}∪{v1}∪{v4}={v1, v2, v3, v4};

      Ö1v1={v2, v4}; Ö1v2={v1}; Ö1v3={v1}; Ö1v4={v2, v3, v5}; Ö1v5={v2};

      Ö2v4=Ö{Öv4}=Ö{v2, v3, v5}=Öv2 ∪ Öv3 ∪ Öv5=
      ={v1}∪{v1}∪{v2}={v1, v2};

      Ö3v4=Ö{Ö2v4}=Ö{v1, v2}=Öv1 ∪ Öv2={v2,v4}∪{v1}={v1, v2, v4}.

     à              v             v#   á
                                                                v
                                         v                               v#


     v
                           v"
                                                                          v$
                                         v!                v"
          v!

                                Ðèñ. 1.20. Îðãðàôû

32


   Òðàíçèòèâíûì çàìûêàíèåì íàçûâàåòñÿ ìíîãîçíà÷íîå îòîáðàæåíèå,
îïðåäåëÿåìîå ôîðìóëîé

                     Γvi = {vi } ∪ Γvi ∪ Γ 2 vi ∪ ... ,
                     ˆ
ò. å. òðàíçèòèâíîå çàìûêàíèå åñòü ìíîæåñòâî âåðøèí, â êîòîðûå ìîæ-
íî ïðèéòè èç âåðøèíû vi ïî íåêîòîðîìó ïóòè áåç ïîâòîðåíèÿ äóã.
    Àíàëîãè÷íî îïðåäåëÿåòñÿ îáðàòíîå òðàíçèòèâíîå çàìûêàíèå:

                  Γ − vi = {vi } ∪ Γ −1vi ∪ Γ −2 vi ∪ ... ,
                  ˆ
ò. å. îáðàòíîå òðàíçèòèâíîå çàìûêàíèå åñòü ìíîæåñòâî âåðøèí, èç êî-
òîðûõ ïîïàäàþò â âåðøèíó vi ïî íåêîòîðîìó ïóòè áåç ïîâòîðåíèÿ äóã.
    Íàïðèìåð, äëÿ ãðàôà íà ðèñ.1.20,à
             Ã v1 = V, Ã v2= V, Ã v3 = V, Ã v4 = V, Ã v5 = V,
             ˆ         ˆ        ˆ         ˆ         ˆ
àíàëîãè÷íî
              à –v1=V, à –v2=V, à –v3=V, à –v4=V, à –v5=V,
              ˆ        ˆ        ˆ        ˆ        ˆ
ò. å. èç êàæäîé âåðøèíû ìîæíî ïðèéòè â ëþáóþ äðóãóþ âåðøèíó.
     Äëÿ ãðàôà íà ðèñ. 1.20,á Ãv6 = {v6}, ò. å. èç âåðøèíû v6 íåëüçÿ ïî-
ïàñòü íè â îäíó èç äðóãèõ âåðøèí, òîãäà êàê à – v6 = V, ò. å. â âåðøèíó v6
ìîæíî ïðèéòè èç ëþáûõ äðóãèõ âåðøèí ãðàôà.
                      1.4.8. Ñèëüíî ñâÿçíûé îðãðàô
   Ñèëüíî ñâÿçíûì ãðàôîì G = (V, Ã) íàçûâàåòñÿ ãðàô, åñëè
                           (∀vi ∈ V)Ãvi = V ,
                                    ˆ
ò. å. äëÿ ëþáûõ äâóõ âåðøèí vi, vj ñóùåñòâóåò ïóòü, èäóùèé èç vi â vj.
Íàïðèìåð, ãðàô íà ðèñ 1.20,à ÿâëÿåòñÿ ñèëüíî ñâÿçàííûì, à åãî íàäãðàô
íà ðèñ.1.20,á íå ÿâëÿåòñÿ òàêîâûì. Ñèëüíî ñâÿçíûé ãðàô ìîæíî îïðå-
äåëèòü òàêæå ñ ïîìîùüþ óñëîâèÿ
                          (∀vi ∈ V)Ã − vi = V .
                                   ˆ
   Áèíàðíîå îòíîøåíèå “ñóùåñòâóåò ïóòü èç vi â vj” ÿâëÿåòñÿ îòíîøå-
íèåì ÷àñòè÷íîãî ïîðÿäêà íà ìíîæåñòâå âåðøèí V, òàê êàê îíî òðàíçè-
òèâíî è ðåôëåêñèâíî. Áèíàðíîå îòíîøåíèå “ñóùåñòâóåò ïóòü èç vi â vj
è ïóòü èç vj â vi” çàäàåò îòíîøåíèå ýêâèâàëåíòíîñòè (R), òàê êàê îíî,
êðîìå òîãî, ñèììåòðè÷íî. Ýòî áèíàðíîå îòíîøåíèå ïîðîæäàåò êîíòóðû â
ãðàôå. Çíà÷èò, ñèëüíî ñâÿçíûé ãðàô – ýòî ãðàô, ñîäåðæàùèé êîíòóðû.
                                                                        33


       1.5. Ðåàëèçàöèÿ àëãîðèòìîâ òåîðèè ãðàôîâ íà ÝÂÌ
   Ðåøåíèå çàäà÷ ñ ïðèìåíåíèåì ìåòîäîâ òåîðèè ãðàôîâ äîëæíî ïîä-
÷èíÿòüñÿ îáùåé ïîñëåäîâàòåëüíîñòè ýòàïîâ ðåøåíèÿ çàäà÷ ñ ïðèìåíå-
íèåì ÝÂÌ.
   1-é ýòàï – ïîñòàíîâêà çàäà÷è. Äàåòñÿ ôîðìóëèðîâêà çàäà÷è, öåëåé åå
ðåøåíèÿ è îãðàíè÷åíèé íà “ñîäåðæàòåëüíîì” åñòåñòâåííîì ÿçûêå.
   2-é ýòàï – ôîðìàëèçàöèÿ çàäà÷è. Ñîäåðæàòåëüíîå îïèñàíèå çàäà÷è
ïåðåâîäèòñÿ íà ôîðìàëèçîâàííûé ÿçûê èñïîëüçóåìîé ìàòåìàòè÷åñêîé
òåîðèè, ò. å. ñîçäàåòñÿ ìàòåìàòè÷åñêàÿ ìîäåëü çàäà÷è.
   3-é ýòàï – âûáîð ÷èñëåííîãî ìåòîäà ðåøåíèÿ çàäà÷è â ñîîòâåòñòâèè
ñ çàäàííûìè êðèòåðèÿìè, íàïðèìåð ïðè èñïîëüçîâàíèè ÝÂÌ òàêèìè
êðèòåðèÿìè ìîãóò áûòü âðåìÿ ðåøåíèÿ è îáúåì çàíèìàåìîé ïàìÿòè.
   4-é ýòàï – àëãîðèòìèçàöèÿ. Ïðè ïîñòðîåíèè àëãîðèòìîâ îáðàáîòêè
ãðàôîâ äîëæíû ñîáëþäàòüñÿ îáùèå ñâîéñòâà àëãîðèòìîâ.
   1. Äèñêðåòíîñòü. Ïðèìåíåíèå àëãîðèòìà îñóùåñòâëÿåòñÿ â äèñêðåò-
íîì âðåìåíè â ñîîòâåòñòâèè ñ ïîñëåäîâàòåëüíîñòüþ ïðàâèë, äåéñòâèé,
îïåðàöèé, øàãîâ, ïðîöåäóð ïî îáðàáîòêå ãðàôîâ.
   2. Äåòåðìèíèðîâàííîñòü. Äåéñòâèÿ íàä ãðàôîì â ñîîòâåòñòâèè ñ ïðà-
âèëàìè îáðàáîòêè äîëæíû áûòü ïðîñòûìè è îïðåäåëåííûìè, ïðè ýòîì
ìîãóò èñïîëüçîâàòüñÿ èçâåñòíûå ïðîöåäóðû.
   3. Ðåçóëüòàòèâíîñòü. Àëãîðèòì ñîñòîèò èç ñîâîêóïíîñòè êîíå÷íî-
ãî ÷èñëà ïðàâèë è äåéñòâèé, êîòîðûå äîëæíû îò èñõîäíûõ äàííûõ ïðè-
âåñòè ê èñêîìîìó ðåçóëüòàòó çà êîíå÷íîå ÷èñëî øàãîâ. Âûáîð ïðàâèë è
äåéñòâèé çàâèñèò òîëüêî îò ðåçóëüòàòîâ ïðåäûäóùèõ øàãîâ, íàïðèìåð
îò ðåçóëüòàòà àíàëèçà âåðøèí ñìåæíûõ ñ äàííîé âåðøèíîé.
   4. Ìàññîâîñòü. Àëãîðèòì äîëæåí ïðèìåíÿòüñÿ äëÿ öåëîãî êëàññà
çàäà÷, à íå îäíîé çàäà÷è.
   Îäíàêî, åñëè ðåøåíèå çàäà÷è ïðåäñòàâëåíî â âèäå àëãîðèòìà ñ ñî-
áëþäåíèåì ñâîéñòâ 1–4, îí ìîæåò èìåòü ñâîþ ñïåöèôèêó, ñâÿçàííóþ ñ
ÿçûêîì òåîðèè ãðàôîâ è îòðàæàþùóþñÿ â åãî ôîðìóëèðîâêå. Èìååòñÿ
îïðåäåëåííîå ðàçëè÷èå â ñòåïåíè ïîäãîòîâëåííîñòè çàïèñè àëãîðèò-
ìîâ äëÿ èõ ðåàëèçàöèè íà ÝÂÌ. Ïîýòîìó íåîáõîäèìî ïðèâåñòè àëãî-
ðèòì, íàïèñàííûé íà ñîäåðæàòåëüíîì óðîâíå è íà óðîâíå àáñòðàêöèé
òåîðèè ãðàôîâ, ê âèäó ìàøèííî-îðèåíòèðîâàííûõ àëãîðèòìîâ.
   Ìàøèííî-îðèåíòèðîâàííûìè, ò. å. êîìïüþòåðíûìè, ÿâëÿþòñÿ àëãî-
ðèòìû, êîòîðûå ìîæíî çàïèñûâàòü â âèäå ïðîãðàììû äëÿ ÝÂÌ.
   5-é ýòàï – ïðîãðàììèðîâàíèå. ÝÂÌ ìîæåò áûòü ïðèìåíåíà äëÿ ðå-
øåíèÿ çàäà÷è òåîðèè ãðàôîâ òîëüêî ïîñëå òîãî, êàê åå àëãîðèòì áóäåò
34


çàïèñàí â âèäå ïðîãðàììû, ò. å. äåòàëüíûõ èíñòðóêöèé ïî îáðàáîòêå
ãðàôà íà ÿçûêå, ïîíÿòíîì ÝÂÌ.
    Â ïðîãðàììå äîëæíî áûòü ïðåäóñìîòðåíî, êàêèå äàííûå è â êàêîì
âèäå äîëæíû áûòü ââåäåíû â ÝÂÌ äëÿ èõ ïîñëåäóþùåé îáðàáîòêè.
×àùå âñåãî ãðàô ââîäèòñÿ â ÝÂÌ ñ ïîìîùüþ ìàòðèöû ñìåæíîñòè âåð-
øèí. Íàïðèìåð, äëÿ ãðàôà G=(V,U) áåç ïàðàëëåëüíûõ äóã ìàòðèöà ñìåæ-
íîñòè – ýòî êâàäðàòíàÿ áóëåâà ìàòðèöà ||Sij|| ðàçìåðîì n×n, ãäå n – ÷èñëî
âåðøèí ãðàôà. Ýëåìåíò Sij = 1, åñëè äóãà(vi, vj)∈ U, è Sij = 0 â ïðîòèâíîì
ñëó÷àå. Êðîìå òîãî, ìîæåò ïîòðåáîâàòüñÿ ââåäåíèå äîïîëíèòåëüíîé
èíôîðìàöèè î ãðàôå â âèäå ìàññèâîâ (ìàòðèö è âåêòîðîâ). Âîçìîæíî
äóãàì è/èëè âåðøèíàì ìîãóò áûòü ïðèïèñàíû íåêîòîðûå ÷èñëà (óñëîâ-
íî ãîâîðÿ, äëèíû äóã, âåñà âåðøèí), îòðàæàþùèå äîïîëíèòåëüíûå ñâîé-
ñòâà ñâÿçåé ìåæäó âåðøèíàìè. Íàïðèìåð, äëèíà äóãè – ýòî ðàññòîÿíèå
ìåæäó óäàëåííûìè îáúåêòàìè, ïðåäñòàâëåííûìè âåðøèíàìè ãðàôà.
    Ïðîãðàììà äîëæíà ÷åòêî ïðåäïèñàòü ïîñëåäîâàòåëüíîñòü îïåðàöèé,
êîòîðûå íóæíî ïðîèçâåñòè íàä ìàòðèöåé ñìåæíîñòè ãðàôà, äðóãèìè
âõîäíûìè äàííûìè è ïðîìåæóòî÷íûìè ðåçóëüòàòàìè (ìàòðèöàìè, âåê-
òîðàìè, ÷èñëàìè), ôîðìèðóåìûìè â ïðîöåññå ðåøåíèÿ, ÷òîáû ïîëó-
÷èòü âûõîäíûå ðåçóëüòàòû, à òàêæå ïðåäóñìîòðåòü, â êàêîì âèäå ýòè
ðåçóëüòàòû áóäóò âûäàíû ÝÂÌ äëÿ ïîëüçîâàòåëÿ.
   6-é ýòàï – îòëàäêà, ò. å. ïîèñê è èñïðàâëåíèå ñèíòàêñè÷åñêèõ (ôîð-
ìàëüíûõ) îøèáîê, à òàêæå ñåìàíòè÷åñêèõ (ñìûñëîâûõ) îøèáîê ñ èñ-
ïîëüçîâàíèåì ñïåöèàëüíûõ òåñòîâûõ äàííûõ.
   7-é ýòàï – èñïîëüçîâàíèå îòëàæåííîé ïðîãðàììû äëÿ ðàñ÷åòîâ ñ ðå-
àëüíûìè èñõîäíûìè äàííûìè.
   8-é ýòàï – èíòåðïðåòàöèÿ ðåçóëüòàòîâ, ïîëó÷åííûõ â õîäå ðàáîòû
ïðîãðàììû è ðåêîìåíäàöèè ïî èõ èñïîëüçîâàíèþ.
   Ïîñëå ýòèõ êðàòêèõ çàìå÷àíèé íåòðóäíî ïîíÿòü, êàêàÿ áîëüøàÿ äèñ-
òàíöèÿ, êàê ïðàâèëî, èìååòñÿ ìåæäó ôîðìóëèðîâêîé àëãîðèòìà íà ÿçû-
êå òåîðèè ãðàôîâ è ïðîãðàììîé äëÿ ÝÂÌ. Èìåííî ðàçðàáîòêà êîìïüþ-
òåðíîãî àëãîðèòìà äîëæíà áûòü ðåçóëüòàòîì ýòàïîâ ôîðìàëèçàöèè è
àëãîðèòìèçàöèè ïðè ðåøåíèè ïðèêëàäíûõ çàäà÷ ñ ïðèìåíåíèåì òåîðå-
òè÷åñêèõ ìîäåëåé òåîðèè ãðàôîâ.
    Íèæå áóäåò ðàññìîòðåíî ðåøåíèå íåêîòîðûõ çàäà÷ ñ èñïîëüçîâàíè-
åì àëãîðèòìîâ òåîðèè ãðàôîâ ñ âîçìîæíûì ïðèìåíåíèåì êîìïüþòåð-
íûõ àëãîðèòìîâ.


                                                                       35


                  2. ÇÀÄÀ×È Î ÏÓÒßÕ Â ÎÐÃÐÀÔÅ
   Àëãîðèòìû ýòèõ çàäà÷ èãðàþò áîëüøóþ ðîëü â òåîðèè ãðàôîâ, ïî-
ñêîëüêó ñ èõ ïîìîùüþ ðåøàþòñÿ ìíîãèå ïðèêëàäíûå çàäà÷è. Íàïðè-
ìåð, ýòî çàäà÷è î ñóùåñòâîâàíèè ïóòåé ìåæäó âåðøèíàìè ãðàôà, î êî-
ëè÷åñòâå ïóòåé ìåæäó äâóìÿ âåðøèíàìè, î ïóòè ñ íàèìåíüøèì ÷èñëîì
äóã ìåæäó âåðøèíàìè, î êðàò÷àéøåì ïóòè ìåæäó äâóìÿ âåðøèíàìè, î
äëèííåéøåì ïî âðåìåíè ïóòè îò íà÷àëüíîé âåðøèíû äî êîíå÷íîé âåð-
øèíû ãðàôà (òàê íàçûâàåìûé êðèòè÷åñêèé ïóòü), î äåðåâå êðàò÷àéøèõ
ðàññòîÿíèé è äðóãèå çàäà÷è.

                 2.1. Ñóùåñòâîâàíèå ïóòåé â îðãðàôå
    Ïîñòàíîâêà çàäà÷è.  îðãðàôå òðåáóåòñÿ îïðåäåëèòü, ñóùåñòâóþò
ëè êàêèå-ëèáî ïóòè ìåæäó âåðøèíàìè ãðàôà.
   Ïóñòü N0 = {1,2,3, ...} – ìíîæåñòâî íàòóðàëüíûõ ÷èñåë áåç íóëÿ. Äëÿ ãðàôà
G=(V, Ã) ïóòü ïîëîæèòåëüíîé äëèíû èç âåðøèíû vi â vj ñóùåñòâóåò, åñëè
                        (∃p ∈ N 0 ) v j ∈ Ã p vi .                    (2.1)
     Åñëè ðàññìàòðèâàòü ïóòè äëèíû íîëü, òî (2.1) ìîæíî çàïèñàòü òàê:
                               v j ∈ Ãvi ,
                                     ˆ                                (2.2)
ò. å.vj âõîäèò â ìíîæåñòâî òðàíçèòèâíîãî çàìûêàíèÿ âåðøèíû vi.
             2.1.1. Ìåòîä ðåøåíèÿ çàäà÷è î ïóòÿõ â ãðàôå
   Áóëåâà ìàòðèöà ñìåæíîñòè ||S||n×n ãðàôà G=(V, Ã) áåç ïàðàëëåëüíûõ
äóã ïîêàçûâàåò, êàêèå ñóùåñòâóþò ïóòè äëèíû 1 (íàïðèìåð, ðèñ. 2.1),
ïðè ýòîì |V| = n.
   Ïðèìåíèì ê ìàòðèöå ||S|| îïåðàöèè áóëåâûõ óìíîæåíèÿ è ñëîæåíèÿ.
Ïóñòü
                             ||S||2 = ||S||∧||S||,
                                ||S||4 = ||S||2∧||S||2,
                                 .......................
36


òîãäà
            2r        2r −1        2r −1           2r −1       2r −1                    2r −1           2r −1
        S ij = S i1            ∧ S 1 j ∨ S i 2 ∧ S 2 j ∨ L ∨ S in                               ∧ S nj          ,
ãäå i, j=1(1)n (èçìåíåíèå îò 1 ñ øàãîì 1 äî n); ∧ – áóëåâî óìíîæåíèå;
∨ – áóëåâî ñëîæåíèå; r – íîìåð íîâîé áóëåâîé ìàòðèöû.
                          A                                                ||S|| 6×6:
                                                                                )       *   +       ,   -       .
                                                                            )                              
    .                                          B                            *                              
                                                                            +                              
                                                                            ,                              
                                                                            -                              
                                           C
                                                                            .                              
    E

                      D
                     Ðèñ. 2.1. Ãðàô è åãî áóëåâà ìàòðèöà ñìåæíîñòè

    Óìíîæåíèå ïðîäîëæàåòñÿ äî òåõ ïîð, ïîêà íå ñðàâíÿþòñÿ äâå ïîñëå-
                          2r       2r −1                                                                            r −1
äíèå ìàòðèöû S = S           . Òîãäà íåíóëåâûå ýëåìåíòû ìàòðèöû S 2
ïîêàæóò, êàêèå âåðøèíû â ãðàôå ñâÿçàíû êàêèìè-ëèáî ïóòÿìè.
                                  Ïðèìåð
    Íà ðèñ.2.1 èçîáðàæåí ãðàô è åãî ìàòðèöà ñìåæíîñòè ||S||, à íà ðèñ.2.2
ïðåäñòàâëåíû ìàòðèöû ||S||2, ||S||4, ||S||8.
  ||S||2:                 ||S||4:                  ||S||8:

    )   *   +    ,    -    .               )   *      +    ,   -       .                )       *   +    ,      -   .
)                             )                                       )                            
*                             *                                       *                            
+                             +                                       +                            
,                             ,                                       ,                            
-                             -                                       -                            
.                             .                                       .                            
                 Ðèñ. 2.2. Áóëåâû ìàòðèöû ñóùåñòâîâàíèÿ ïóòåé
                              ìåæäó âåðøèíàìè ãðàôà
                                                                                                                     37


   Ìàòðèöà ||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) ìàòðèöû ïîýëåìåíòíî ñðàâ-
íèâàòü R1ij è Rij. Åñëè R1ij ≠ Rij, òî ñêîïèðîâàòü R=R1 è ïåðåéòè ê øàãó
3, èíà÷å âûâåñòè ñ÷åò÷èê äëèí ïóòåé L = 2r–1 êàê ðåçóëüòàò ðåøåíèÿ
çàäà÷è.

                           2.2. Ïåðåñ÷åò ïóòåé â îðãðàôå
   Ïîñòàíîâêà çàäà÷è.  îòëè÷èå îò ïðåäûäóùåé çàäà÷è òðåáóåòñÿ âû-
÷èñëèòü êîëè÷åñòâî ïóòåé êîíêðåòíîé äëèíû (êàê ÷èñëî äóã) ìåæäó
êàæäîé ïàðîé âåðøèí ãðàôà.
               2.2.1. Ìåòîä ðåøåíèÿ çàäà÷è ïåðåñ÷åòà ïóòåé
    Ïåðåñ÷åò ðàçëè÷íûõ ïóòåé äëèíû r îñóùåñòâëÿåòñÿ ïîëó÷åíèåì ñòå-
ïåíåé èñõîäíîé ìàòðèöû ñìåæíîñòè ãðàôà (||S||) ñ ïîìîùüþ îïåðàöèè
ëèíåéíîé àëãåáðû îáû÷íîãî óìíîæåíèÿ äâóõ ìàòðèö:
   ||S|| –                äàåò ÷èñëî ïóòåé äëèíû 1,
   ||S||2 = ||S||×||S|| äàåò ÷èñëî ïóòåé äëèíû 2.
   ||S||3=||S||2×||S|| äàåò ÷èñëî ïóòåé äëèíû 3,
   .. . . . . . . . . . .
   ||S||L=||S||L–1×||S|| – äàåò ÷èñëî ïóòåé äëèíû L äëÿ êàæäîé ïàðû âåð-
øèí (vi,vj), ãäå

                                                                  n
     Sij = Sik −1 ⋅ S1 j + Sik2−1 ⋅ S2 j + ... + Sin−1 ⋅ Snj =
       k
             1
                                                   k
                                                                 ∑ Sim−1 ⋅ Smj , k ≥ 2.
                                                                     k

                                                                 m =1

38


   Çíà÷åíèå 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. Ìàòðèöû ïåðåñ÷åòà äëèí ïóòåé ìåæäó âåðøèíàìè ãðàôà
                                                                     39


                2.3. Ïóòü ñ íàèìåíüøèì ÷èñëîì äóã.
              Ïîèñê òðàíçèòèâíîãî çàìûêàíèÿ âåðøèí
   Ïîñòàíîâêà çàäà÷è. Ïóñòü çàäàí ïðîèçâîëüíûé ãðàô G=(V,U). Òðåáó-
åòñÿ ïîñòðîèòü òàêîé ïóòü, ñîåäèíÿþùèé äâå çàäàííûå âåðøèíû v è w,
êîòîðûé ñîäåðæèò íàèìåíüøåå ÷èñëî äóã (ýòî ïóòü ìèíèìàëüíîé äëè-
íû, åñëè ñ÷èòàòü, ÷òî äëèíû âñåõ äóã îäèíàêîâû, ò. å. ýëåìåíòàðíûé
ïóòü).
              2.3.1. Ìåòîä ðåøåíèÿ çàäà÷è ïîèñêà ïóòè
                       ñ íàèìåíüøèì ÷èñëîì äóã
    Ðàññìîòðèì àëãîðèòì ýòîé çàäà÷è, êîòîðûé ïðîèëëþñòðèðîâàí íà
ðèñ. 2.4. Àëãîðèòì ìîæíî ðàçäåëèòü íà äâà ýòàïà: ïðÿìîé õîä – ïðèñâà-
èâàíèå âåðøèíàì ãðàôà ìåòîê; îáðàòíûé õîä – îïðåäåëåíèå ìèíèìàëü-
íîãî ïóòè îò êîíå÷íîé âåðøèíû äî èñõîäíîé.
    Ïðÿìîé õîä:
    1. Ïðèñâîèòü âåðøèíå v ìåòêó 0.
    2. Åñëè xi ∈ Ãv è xi≠ v, òî ïðèñâîèòü êàæäîé òàêîé âåðøèíå ìåòêó 1,
(ò. å. ýòî âåðøèíû-êîíöû äóã, èñõîäÿùèõ èç âåðøèíû v, êðîìå ñàìîé
âåðøèíû v, ïðè ýòîì èñêëþ÷àþòñÿ ïåòëè).
    3. Ïóñòü X(m) (m=0,1,2,...) – ìíîæåñòâî âåðøèí, èìåþùèõ ìåòêó m.
Âåðøèíàì X(m + 1) = {x ∈ ÃX(m), x ∉ X(k ) ïðè k ≤ m} (ò. å. âåðøèíàì–
êîíöàì äóã, èñõîäÿùèõ èç âåðøèí ìíîæåñòâà Õ(m), êðîìå âåðøèí, óæå
ïîëó÷èâøèõ ìåòêè ðàíåå, – òåì ñàìûì èñêëþ÷àþòñÿ êîíòóðû) ïðèñâî-
èòü ìåòêè m+1.
    4. Ïðîöåññ ïðèñâîåíèÿ âåðøèíàì ìåòîê ïðåêðàòèòü, êàê òîëüêî âåð-
øèíà w ïîëó÷èò ìåòêó n (w∈X(n)).
    Îáðàòíûé õîä:
    5. Ðàññìîòðåòü âåðøèíû xi1 , xi2 ,..., xin òàêèå, ÷òî
                               xi1 ∈ X(n–1), w ∈ à xi1 ,
                              xi2 ∈ X(n–2), xi1 ∈ à xi2 ,
                             .....................................
                              xin ∈ X(0), xin −1 ∈ Ã xin .
    Ïóòü µ = ( v = xin , xin −1 , . .., xi2 , xi1 , w ) äàåò ðåøåíèå çàäà÷è.
    Çàìå÷àíèå. Åñëè íà íåêîòîðîì øàãå íåâîçìîæíî ïðèñâîåíèå ìåòêè
m+1 âåðøèíàì, ïîñêîëüêó ìíîæåñòâî ÃX(m) ïóñòî è âåðøèíà w íå ïî-
ëó÷èëà ìåòêè, òî ýòî îçíà÷àåò, ÷òî â ãðàôå G íå ñóùåñòâóåò ïóòè, ñî-
åäèíÿþùåãî âåðøèíó v ñ âåðøèíîé w.
40



    
Яндекс цитирования Яндекс.Метрика