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

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

Голосов: 13

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    êîëè÷åñòâî ïàðàëëåëüíûõ äóã, âàæíîñòü êðèòåðèåâ è âåëè÷èíû îöå-
íîê ïî ðàçíûì êðèòåðèÿì. Äëÿ ó÷åòà ïîñëåäíèõ ïàðàìåòðîâ èñïîëü-
çóþòñÿ áîëåå ñëîæíûå ïðàâèëà è àëãîðèòìû ïðåîáðàçîâàíèÿ
GV→G=(V,U).
    Èñïîëüçóÿ ïðèíöèï ãîëîñîâàíèÿ (áîëüøèíñòâà) êàê îòíîøåíèå ïðå-
âîñõîäñòâà, èç ãðàôà GV (ðèñ. 4.2,à) ìîæíî ëåãêî ïîëó÷èòü ãðàô G=(V,U)
(ðèñ. 4.2,á), êîòîðûé ìîæåò áûòü íå òðàíçèòèâíûì, íåñìîòðÿ íà òî, ÷òî
âñå èñõîäíûå ãðàôû GV òðàíçèòèâíû.
    Ãðàô G îòðàæàåòñÿ áóëåâîé ìàòðèöåé ñìåæíîñòè ÂÌ×Ì (ðèñ. 4.2,â),
â êîòîðîé ýëåìåíò bij=1, åñëè äóãà (v,v')∈U (ñòðåëêà èäåò îò v ê v'), ò. å.
âåðøèíà v' ïðåâîñõîäèò (áîëåå ïðåäïî÷òèòåëüíà) v, â ïðîòèâíîì ñëó÷àå
bij=0.
                  à     G 8:
                                              3
                          v                   3                       v!
                                                      3
                                                          3
                           4         2                            5   1

                                                              6
                                                  2
                                v                1                   v"
                                                  5
   á     G:                                  â B"×"
                                                                  1    2   3   4
          v                              v!
                                                              1   0    1   1   1
                                                              2   0    0   1   1
                                                              3   1    1   0   1
                                                              4   0    0   0   0
           v                           v"
Ðèñ. 4.2. Ïðåîáðàçîâàíèå ìóëüòèãðàôà GV → G: à – ìóëüòèãðàô GV ; á – ãðàô
                  G=(V, U); ⠖ ìàòðèöà ñìåæíîñòè ãðàôà G

   Òàêèì îáðàçîì, â ðåçóëüòàòå äâóõ øàãîâ îáðàáîòêè èñõîäíîé ìàòðè-
öû îöåíîê PÌ×N ïîëó÷åíà áóëåâà ìàòðèöà ÂÌ×Ì, îòðàæàþùàÿ ãðàô G
ïðåâîñõîäñòâà (ïðåäïî÷òåíèÿ) âåðøèí (îáúåêòîâ ñðàâíåíèÿ).

                                                                                   61


                  4.5. Ìåòîäû è àëãîðèòìû âûáîðà
                     ïðåäïî÷òèòåëüíûõ îáúåêòîâ

         4.5.1. Ìåòîä è àëãîðèòì ïîèñêà êîíòóðîâ â ãðàôå
    Ðàññìîòðèì ãðàô G êàê ïàðó G= (V, Ã), ãäå Ã ïðåäñòàâëÿåò ìíîãî-
çíà÷íîå îòîáðàæåíèå ìíîæåñòâà âåðøèí V â ñåáÿ, íàïðèìåð, êàê áûëî
ïîêàçàíî âûøå Ãv, îáîçíà÷àåò ìíîæåñòâî âåðøèí-êîíöîâ äóã, èìåþùèõ
íà÷àëîì âåðøèíó v; Ãv è à − v ïðåäñòàâëÿþò òðàíçèòèâíîå è îáðàòíîå
                       ˆ     ˆ
òðàíçèòèâíîå çàìûêàíèå äëÿ âåðøèíû v.
     Îòñóòñòâèå òðàíçèòèâíîñòè â ãðàôå ïðåâîñõîäñòâà îáúåêòîâ ñðàâ-
íåíèÿ G ñâèäåòåëüñòâóþò î íàëè÷èè êîíòóðîâ, îáúåäèíÿþùèõ ïîäìíî-
æåñòâà îáúåêòîâ, íåðàçëè÷èìûõ ïî èíôîðìàöèè, ñîäåðæàùåéñÿ â ãðà-
ôå, â ñîîòâåòñòâèè ñ îòíîøåíèåì íåðàçëè÷èìîñòè Nf äëÿ îáúåêòîâ ñ
îäèíàêîâûìè îöåíêàìè p(v)=p(v') : (v,v')∈Nf. Ýòî îòíîøåíèå Nf ÿâëÿåòñÿ
òàêæå îòíîøåíèåì ýêâèâàëåíòíîñòè (òðàíçèòèâíûì, ðåôëåêñèâíûì è
ñèììåòðè÷íûì).
     Ïóñòü Ê ÿâëÿåòñÿ êîíòóðîì â ãðàôå G, òîãäà îáúåêòû v∈Ê ìîæíî
ðàññìàòðèâàòü êàê ýêâèâàëåíòíûå, ò. å. êîíòóðû îáðàçóþò êëàññû ýê-
âèâàëåíòíîñòåé (Ê1,…, Êm ) è ïðåäñòàâëÿþòñÿ â ãðàôå êàê òðàíçèòèâíûå,
ðåôëåêñèâíûå, ñèììåòðè÷íûå ïîäãðàôû, îïðåäåëåííûå âûøå (ñì. ï. 1.4.8)
êàê ñèëüíî ñâÿçíûå ãðàôû. Òàêèì îáðàçîì ìíîæåñòâî îáúåêòîâ V (âåð-
øèí ãðàôà G) ìîæíî ðàçëîæèòü íà êëàññû Ê1,…, Êm, êàæäûé èç êîòî-
ðûõ åñòü êîíòóð, ò. å. ñèëüíî ñâÿçíûé ãðàô.
    Ìàêñèìàëüíûì ñèëüíî ñâÿçíûì ïîäãðàôîì G' ãðàôà G=(V,Ã) íàçûâà-
åòñÿ òàêîé ïîäãðàô, äëÿ êîòîðîãî íå ñóùåñòâóåò ñèëüíî ñâÿçíîãî ãðàôà
G'', ñòðîãî ñîäåðæàùåãî G'.
    Ëåãêî ïîêàçàòü, ÷òî ïîäìíîæåñòâî êëàññîâ {Êi}, i= 1,m , óïîðÿäî÷è-
âàþòñÿ îòíîøåíèåì R': “ñóùåñòâóåò ïóòü èç êëàññà Êr â Ês”. Îòíîøå-
íèå R' ðåôëåêñèâíî è òðàíçèòèâíî. Îíî òàêæå àñèììåòðè÷íî (ò. å. â
ãðàôå íåò âñòðå÷íûõ äóã), òàê êàê åñëè áû ñóùåñòâîâàëè ïóòè êàê èç Êr
â Ês, òàê è èç Ês â Êr , òî Êr è Ês ñëåäîâàëî áû îáúåäèíèòü â îäèí êëàññ,
÷òî ïðîòèâîðå÷èò èõ ìàêñèìàëüíîñòè.
    Ïåðâûé øàã óïîðÿäî÷åíèÿ ãðàôà ïðåâîñõîäñòâà G = (V,Ã) ñîñòîèò â
íàõîæäåíèè êîíòóðîâ ãðàôà è ðàññìîòðåíèè èõ êàê îòäåëüíûõ îáúåê-
òîâ.
    Ìåòîä ïîèñêà êîíòóðîâ ñîñòîèò â ðàçëîæåíèè ãðàôà íà êëàññû ýêâè-
âàëåíòíîñòåé:
62


åñëè Ê(vi) – êëàññ, ñîäåðæàùèé âåðøèíó vi, òî

                                Ê(vi) = Ãvi ∩ Ã−1vi ,
                                        ˆ     ˆ
ò. å. êîíòóð äëÿ íåêîòîðîé âåðøèíû vi åñòü ïîäìíîæåñòâî âåðøèí, îá-
ðàçóåìîå ïåðåñå÷åíèåì ìíîæåñòâ òðàíçèòèâíîãî è îáðàòíîãî òðàíçè-
òèâíîãî çàìûêàíèé äëÿ âåðøèíû vi.  ÷àñòíîñòè, êëàññ Ê(vi) ìîæåò ñî-
ñòîÿòü è èç îäíîé âåðøèíû vi.
    Àëãîðèòì ìåòîäà âêëþ÷àåò ñëåäóþùèå îñíîâíûå øàãè.
    1. Äëÿ îáðàáàòûâàåìûõ âåðøèí âûáèðàåì íà÷àëüíóþ âåðøèíó vi è
îïðåäåëÿåì Ãvi , Ã −1vi , Ê(vi).
           ˆ     ˆ
   2. Óäàëÿåì èç äàëüíåéøåãî àíàëèçà âåðøèíû èç Ê(vi) ïóòåì ïîäàâ-
ëåíèÿ èõ ñâÿçåé, äëÿ ÷åãî â ìàòðèöå ñìåæíîñòè íåîáõîäèìî îáíóëèòü
ñòðîêè è ñòîëáöû äëÿ âåðøèí èç êëàññà Ê(vi).
   3. Åñëè åñòü åùå íåîáðàáîòàííûå âåðøèíû, òî ïåðåéòè íà øàã 1.
                               Ïðèìåð
   Äëÿ ãðàôà G=(V,U), ãäå V=11 (ðèñ. 4.3) íèæå ïðåäñòàâëåí ïðîöåññ
ïîëó÷åíèÿ êîíòóðîâ îò íà÷àëüíûõ âåðøèí. Ðåçóëüòèðóþùèé âåêòîð V
äîëæåí ñîäåðæàòü íîìåðà êîíòóðîâ, ïðè âåðøèíàõ èõ îáðàçóþùèõ.

                               v         v
                                                             v


                        v                                      v!


                   v'

                                                                      v"
                          v&                            v#

                                                  v$

                                     v%
                               Ðèñ. 4.3. Îðãðàô G

  Ýòàï 1. Îáðàáîòêà èñõîäíîé ìàòðèöû ñìåæíîñòè S. Íà÷àëüíàÿ âåð-
øèíà v1 îòìå÷åíà çíà÷åíèåì 0 â âåêòîðàõ çàìûêàíèé.

                                                                           63


       ||S||:          1   2   3   4   5   6   7   8       9   10   11   Ãv1
                                                                         ˆ
                   1   0   0   0   0   0   0   1   0       0   0    0     0
                  2    1   1   0   0   0   0   0   1       0   0    1    –1
                   3   0   0   1   1   0   0   0   0       1    1   0    –1
                  4    0   0   0   1   1   0   0   0       0   0    0     4
                   5   0   0   0   1   0   0   0   0       0   0    0     3
                  6    0   0   0   0   0   1   0   1       0   0    0     3
                  7    0   0   0   0   0   0   0   0       0   0    1     1
                  8    0   0   0   0   0   0   0   0       0   0    0     4
                  9    0   0   1   0   0   0   0   0       0   0    0    –1
                  10   1   0   0   1   1   0   0   0       1   0    0    –1
                  11   1   0   0   0   1   1   0   0       0   0    1     2


                Ã−1v1 0 1 2 –1 –1 –1 2 –1 3 1 1
                ˆ


   Çíà÷åíèåì –1 îòìå÷åíû âåðøèíû, íå âîøåäøèå â çàìûêàíèÿ. Îñ-
òàëüíûå âåðøèíû âõîäÿò â ïðÿìîå è (èëè) îáðàòíîå òðàíçèòèâíûå çà-
ìûêàíèÿ îò íà÷àëüíîé âåðøèíû v1 â ñîîòâåòñòâèè ñ àëãîðèòìîì ï. 2.3.2:
    Ãv ={v1, v4, v5, v6, v7, v8, v11 } (òðàíçèòèâíîå çàìûêàíèå – Z).
    ˆ
         1

      à −1v1 ={v1, v2, v3, v7, v9, v10, v11} (îáðàòíîå òðàíçèòèâíîå çàìûêàíèå – ZÎ).
      ˆ
     Âåðøèíû, âîøåäøèå â îáà çàìûêàíèÿ, îáðàçóþò êîíòóð K1 :
                             K1(v1)= Ãv1 ∩ Ã −1v = {v1, v7, v11}.
                                         ˆ      ˆ
                                                       1
    Â âåêòîðå V â ïîçèöèÿõ âåðøèí ñ íîìåðàìè 1, 7, 11 çàíîñèòñÿ íîìåð
êîíòóðà Ê1, ò. å. 1 :
    Íîìåðà âåðøèí ãðàôà:           1 2 3 4 5 6 7 8 9 10 11
    Âåêòîð íîìåðîâ êîíòóðîâ V : 1 0 0 0 0 0 1 0 0 0 1
    Â ìàòðèöå ñìåæíîñòè S îáíóëÿþòñÿ ñòðîêè è ñòîëáöû ñ íîìåðàìè 1,
7, 11, òåì ñàìûì âåðøèíû ñ ýòèìè íîìåðàìè èñêëþ÷àþòñÿ èç äàëüíåé-
øåãî àíàëèçà. Åñëè â âåêòîðå V åñòü íåîáðàáîòàííûå âåðøèíû (çíà÷å-
íèå íîìåðà êîíòóðà = 0), òî ïðîäîëæàþòñÿ ýòàïû ïîèñêà êîíòóðîâ â
ãðàôå.
    Ýòàï 2. Îáðàáîòêà ìàòðèöû S ïîñëå ïîäàâëåíèÿ ñâÿçåé âåðøèí
{v1, v7, v11}. Íà÷àëüíàÿ âåðøèíà v2 = 0.

64


          ||S||:        1   2   3   4   5   6   7   8   9   10   11   Ãv1
                                                                      ˆ
                    1   0   0   0   0   0   0   0   0   0   0    0    –1
                   2    0   1   0   0   0   0   0   1   0   0    1     0
                    3   0   0   1   1   0   0   0   0   1    1   0    –1
                   4    0   0   0   1   1   0   0   0   0   0    0    –1
                    5   0   0   0   1   0   0   0   0   0   0    0    –1
                   6    0   0   0   0   0   1   0   1   0   0    0    –1
                   7    0   0   0   0   0   0   0   0   0   0    0    –1
                   8    0   0   0   0   0   0   0   0   0   0    0     1
                   9    0   0   1   0   0   0   0   0   0   0    0    –1
                   10   0   0   0   1   1   0   0   0   1   0    0    –1
                   11   0   0   0   0   0   0   0   0   0   0    0    –1

             à −1v1 –1 0 –1 –1 –1 –1 –1 –1 –1 –1 –1
             ˆ

      Ãv1 ={v2, v8 } (òðàíçèòèâíîå çàìûêàíèå – Z).
      ˆ

      à −1v1 ={v2} (îáðàòíîå òðàíçèòèâíîå çàìûêàíèå – ZÎ).
      ˆ
      Âåðøèíû, âîøåäøèå â îáà çàìûêàíèÿ, îáðàçóþò êîíòóð K2 :
      K2(v2)= Ãv2 ∩ à −1v = {v2}, ò. å. êîíòóð âêëþ÷àåò òîëüêî îäíó âåðøè-
               ˆ      ˆ
                                2
íó.
   Â âåêòîðå V â ïîçèöèè âåðøèíû ñ íîìåðîì 2 çàíîñèòñÿ íîìåð êîí-
òóðà K2, ò. å. 2 :
   Íîìåðà âåðøèí ãðàôà:                   1 2 3 4 5 6 7 8 9 10 11
   Âåêòîð íîìåðîâ êîíòóðîâ V :            1 2 0 0 0 0 1 0 0 0 1
   Àíàëîãè÷íî ïîëó÷àþòñÿ ñëåäóþùèå êëàññû ýêâèâàëåíòíîñòåé (ðå-
êîìåíäóåòñÿ ïðîâåðèòü ñàìîñòîÿòåëüíî):
   K3(v3) = {v3, v9, v10 }; K4(v4) = {v4, v5 }; K5(v6) = {v6}; K6(v8) = {v8}.
   Â ðåçóëüòàòå ïîëíîé îáðàáîòêè ìàòðèöû ñìåæíîñòè S ìîæíî ïîëó-
÷èòü âåêòîð V, ñîäåðæàùèé íîìåðà êîíòóðîâ â ïîçèöèÿõ âåðøèí, âêëþ-
÷åííûõ â äàííûé êîíòóð:
   Íîìåðà âåðøèí ãðàôà:                   1 2 3 4 5 6 7 8 9 10 11
   Âåêòîð íîìåðîâ êîíòóðîâ V:             1 2 3 4 4 5 1 6 3 3 1
   Ðàññìîòðåííûé âûøå ïðîöåññ îáðàáîòêè ìàòðèöû ñìåæíîñòè S è
ïîëó÷åíèÿ âåêòîðà êîíòóðîâ V ìîæíî ïðåäñòàâèòü â âèäå ìàøèííîãî
àëãîðèòìà.

                                                                            65


  4.5.2. Îïèñàíèå ìàøèííîãî àëãîðèòìà ïîèñêà êîíòóðîâ â ãðàôå
   Âîçìîæíûé âàðèàíò ìàøèííîãî àëãîðèòìà ìîæåò âêëþ÷àòü ñëåäóþ-
ùèå îñíîâíûå øàãè.
   1. Ââîä ìàòðèöû ñìåæíîñòè îðãðàôà (S) è åå ðàçìåðà (n).
   2. Îáíóëåíèå V – âåêòîðà âåðøèí êàê íåîáðàáîòàííûõ è NK-ñ÷åò÷è-
êà êîíòóðîâ.
   3. Öèêë i=1(1)n                             (ïî âåðøèíàì âåêòîðà V)
          { åñëè (Vi = 0)                      (âåðøèíà íå îáðàáîòàíà)
              { ïîëó÷åíèå ïî ïîäïðîãðàììå äëÿ âåðøèíû Vi âåêòîðà
                òðàíçèòèâíîãî çàìûêàíèÿ (Z);
                òðàíñïîíèðîâàíèå ìàòðèöû S (ST);
                ïîëó÷åíèå âåêòîðà îáðàòíîãî òðàíçèòèâíîãî
                çàìûêàíèÿ (ZÎ);
                NK=NK + 1;                  (ïîëó÷åíèå íîìåðà êîíòóðà)
   4.           öèêë j=i(1)n          (äëÿ îïðåäåëåíèÿ âåðøèí êîíòóðà)
                 {åñëè (Zj≥0 è ZÎj≥0 )       (íàéäåíà âåðøèíà êîíòóðà)
                    { Vj=NK; (çàíåñåíèå íîìåðà êîíòóðà â âåêòîð V )
   5.                 öèêë m=1(1)n(ïîäàâëåíèå ñâÿçåé âåðøèí êîíòóðà)
                        { Smj=0; Sjm=0; (îáíóëåíèå ñòðîêè è ñòîëáöà j â S )
                        }                            (êîíåö öèêëà ïî m)
                    }
                  }                                   (êîíåö öèêëà ïî j )
              }
          }                                           (êîíåö öèêëà ïî i )
   6. Âûâîä ðåçóëüòàòîâ: V, NK (âåêòîð êîíòóðîâ è èõ êîëè÷åñòâî).
   Íà îñíîâå ïîëó÷åííîãî âåêòîðà êîíòóðîâ V ìîæíî èçîáðàçèòü îðã-
ðàô G ñ âûäåëåííûìè êëàññàìè ýêâèâàëåíòíîñòåé ( êîíòóðàìè).
                  4.5.3. Ïîñòðîåíèå ãðàôà êîíòóðîâ
     Ðèñ. 4.4,à ïîêàçûâàåò, êàê ìîæíî óïîðÿäî÷èòü êëàññû ýêâèâàëåíò-
íûõ îáúåêòîâ, îáðàçóþùèõ êîíòóðû, äëÿ ãðàôà íà ðèñ. 4.3. Íà ðèñ. 4.4,á
ïîêàçàí ãðàô ñàìèõ êîíòóðîâ êàê îòäåëüíûõ îáúåêòîâ, ïîñëå óäàëåíèÿ
êðàòíûõ äóã ìåæäó êîíòóðàìè. Ïîäîáíîå ïðåäñòàâëåíèå êîíòóðà â âèäå
îäíîãî îáúåêòà íàçûâàåòñÿ ñòÿãèâàíèåì êîíòóðà.
    Ãðàô êîíòóðîâ, ïîëó÷åííûé íà îñíîâå îòíîøåíèÿ R': “ñóùåñòâóåò ïóòü
èç êëàññà Kr â Ks”, ÿâëÿåòñÿ òðàíçèòèâíûì, ðåôëåêñèâíûì, àñèììåòðè÷-
íûì (íå èìååò âñòðå÷íûõ äóã), çíà÷èò, îí îòðàæàåò ÷àñòè÷íûé ïîðÿäîê, ò.
å. ÿâëÿåòñÿ êâàçèñåðèåé, à ïîñêîëüêó â ñèëó îòíîøåíèÿ íåðàçëè÷èìîñòè
66


(ýêâèâàëåíòíîñòè) ýëåìåíòîâ êîíòóðà ((v,v')∈Nf è (v,v')∈Nf → v=v') îíè
ñâåäåíû (ñòÿíóòû) ê îäíîìó îáúåêòó (K), ïîñòîëüêó ãðàô êîíòóðîâ ÿâëÿåò-
ñÿ òàêæå àíòèñèììåòðè÷íûì, ò. å. îòðàæàåò ïîëíûé ïîðÿäîê, èëè ñåðèþ.
à                                                   á
 K!           v'                         v    K
      v!                       K                         K!             K
                    v        v
                                                               K
K"    v"                  v%
                   v#               v
                                             v& K$                  K#       K$
                                                          K"

                               v$
                                    K#

       Ðèñ. 4.4. Ãðàô, ðàçëîæåííûé íà ìàêñèìàëüíî ñèëüíî ñâÿçíûå
      ïîäãðàôû (êîíòóðû): à – ãðàô êëàññîâ ýêâèâàëåíòíûõ îáúåêòîâ;
                             á – ãðàô êîíòóðîâ


   Ãðàô êëàññîâ ýêâèâàëåíòíîñòåé ÿâëÿåòñÿ àöèêëè÷åñêèì, à äëÿ âû-
ÿâëåíèÿ â íåì ïîðÿäêà, êîòîðûé íå âûãëÿäèò î÷åâèäíûì, ñóùåñòâó-
þò ðàçëè÷íûå ìåòîäû óïîðÿäî÷åíèÿ âåðøèí, êîòîðûå áóäóò ðàññìîò-
ðåíû íèæå.

           4.6. Ðàçáèåíèå àöèêëè÷åñêîãî ãðàôà íà óðîâíè
  Ïîñòàíîâêà çàäà÷è.  ýòîé çàäà÷å îñóùåñòâëÿåòñÿ óïîðÿäî÷åíèå âåð-
øèí ïî óðîâíÿì ïîñëåäîâàòåëüíîñòåé äóã â àöèêëè÷åñêîì ãðàôå.
                        4.6.1. Ïîðÿäêîâàÿ ôóíêöèÿ ãðàôà
   Ðàññìîòðèì ãðàô áåç êîíòóðîâ G=(V,Ã) è îïðåäåëèì åãî ïîäìíîæå-
ñòâà N0, N1, ... , Nr ñëåäóþùèì îáðàçîì:
   N0={ vi vi ∈V, à −1vi =∅}, ãäå ñèìâîë  ÷èòàåòñÿ êàê “åñëè”, ò. å. N0 –
                      ˆ
ýòî ïîäìíîæåñòâî âåðøèí V, åñëè èì íå ïðåäøåñòâóåò íè îäíà âåðøèíà
(íåò âõîäÿùèõ äóã) ;
   N1={ vi vi ∈V– N0, à −1vi ⊂ N0}, ò. å. N1 – ïîäìíîæåñòâî èç îñòàâøèõ-
                       ˆ
ñÿ âåðøèí-êîíöîâ äóã, ïðè÷åì âåðøèíû-íà÷àëà äóã, íàõîäÿòñÿ â ïðåä-
øåñòâóþùåì ìíîæåñòâå N0 ;
                                                                       67


   N2={ vi vi ∈V–( N0 ∪N1 ), à −1vi ⊂ N0 ∪N1}, ò. å. N2 – ïîäìíîæåñòâî èç
                              ˆ
îñòàâøèõñÿ âåðøèí-êîíöîâ äóã, ïðè÷åì âåðøèíû-íà÷àëà äóã ìîãóò íà-
õîäèòüñÿ â ëþáûõ ïðåäûäóùèõ ìíîæåñòâàõ; íàêîíåö,
                        r −1                       r −1
     Nr={ vi vi ∈ V–   U      N k , à −1v ⊂
                                     ˆ
                                          i        U N k }, ãäå r – òàêîå íàèìåíüøåå
                        k =0                       k =0
÷èñëî, ÷òî ÃNr=∅, ò. å. èç âåðøèí ýòîãî ïîäìíîæåñòâà íå èñõîäèò íè
îäíà äóãà (ýòî âèñÿ÷èå âåðøèíû).
   Ïîäìíîæåñòâà Nk, k=0, 1, 2, … , r îáðàçóþò ðàçáèåíèå V è óïîðÿäî-
÷åíû îòíîøåíèåì ñëåäîâàíèÿ (→) :
                             Nk →Nk' ⇔ k<k'.
   Ïîðÿäêîâàÿ ôóíêöèÿ ãðàôà áåç êîíòóðîâ (Î(v)) îïðåäåëÿåòñÿ ðàâåí-
ñòâîì
                           vi ∈ Nk ⇒ O (vi )=k.
   Äðóãèìè ñëîâàìè, ïðåäëàãàåòñÿ ðàçáèòü ìíîæåñòâî âåðøèí ãðàôà
áåç êîíòóðîâ íà íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà, óïîðÿäî÷åííûå òàê,
÷òî åñëè âåðøèíà ïðèíàäëåæèò ïîäìíîæåñòâó ñ íîìåðîì k, òî ñëåäóþ-
ùàÿ çà íåé âåðøèíà âõîäèò â ïîäìíîæåñòâî ñ íîìåðîì, áîëüøèì k.
    Ïîäìíîæåñòâà ýòîãî ðàçáèåíèÿ íàçûâàþòñÿ óðîâíÿìè. Îíè óïîðÿ-
äî÷èâàþò ïîñëåäîâàòåëüíîñòü ïóòåé â ãðàôå.
                                Ïðèìåð
   Àëãîðèòì íàõîæäåíèÿ óðîâíåé àöèêëè÷åñêîãî ãðàôà è åãî ïîðÿäêî-
âîé ôóíêöèè ðàññìîòðèì íà ïðèìåðå ãðàôà íà ðèñ 4.5,à.
   Ïðåäñòàâèì ãðàô åãî ìàòðèöåé ñìåæíîñòè S è ðàññìîòðèì îñíîâíûå
øàãè àëãîðèòìà íàõîæäåíèÿ óðîâíåé ãðàôà (ñì.ðèñ. 4.5,á).
à)                 á) ||S||:

          B       A     0      0   0   0   1   1               A    B C    D E     .
A               C B     1      0   1   0   1   0          C0    2    0 4    0 3     1   N0={B,D}
                  C     0      0   0   0   0   0          C1    0   –1 2   –1 1     1   N1={A}
               D D      1      0   1   0   1   0          C2   –1   –1 2   –1 0     0   N2={E,.}
     .
          E       E     0      0   1   0   0   0          C3   –1   –1 0   –1 –1   –1   N3={C}
                  .     0      0   1   0   0   0
                        A      B   C   D   E   .
              Ðèñ. 4.5. Âûäåëåíèå óðîâíåé àöèêëè÷åñêîãî ãðàôà:
         à – èñõîäíûé ãðàô G; á – ìàòðèöà ñìåæíîñòè è óðîâíè ãðàôà
68


   Øàã 1. Îáðàçóåì ñòðîêó Ñ0, çàïèñûâàÿ äëÿ êàæäîé âåðøèíû êîëè÷å-
ñòâî ïðåäøåñòâóþùèõ åé âåðøèí, äëÿ ÷åãî íåîáõîäèìî ïðîñóììèðî-
âàòü çíà÷åíèÿ â ñòîëáöàõ ìàòðèöû ãðàôà.  ìíîæåñòâî N0 âîéäóò âåð-
øèíû B è D, êîòîðûì íå ïðåäøåñòâóåò íè îäíà âåðøèíà (íóëè â ñîîò-
âåòñòâóþùèõ ïîçèöèÿõ ñòðîêè Ñ0).
    Øàã 2. Çàïîëíÿåì ñòðîêó Ñ1 ñëåäóþùèì îáðàçîì : 1) â ïîçèöèÿõ
ñòðîêè Ñ1, â êîòîðûõ áûë 0 â ñòðîêå Ñ0 (B, D), çàïèøåì –1 (âåðøèíû
îáðàáîòàíû, ò. å. ïîïàëè íà ñâîé óðîâåíü);
   2) èñêëþ÷àåì âåðøèíû ïðåäûäóùåãî óðîâíÿ N0 ïóòåì îáíóëåíèÿ
ñòðîê B è D ìàòðèöû S;
   3) ñóììèðóåì ñòîëáöû, êðîìå B è D. Âåðøèíû, êîòîðûì ñîîòâåò-
ñòâóþò íóëè â ñòðîêå C1, ñîñòàâëÿþò óðîâåíü N1, â ïðèìåðå ýòî âåðøè-
íà A.
   Øàã i. Àíàëîãè÷íî øàãó 2 çàïîëíÿåì ñòðîêó Ñi è çàïèñûâàåì óðîâíè
Ni äî òåõ ïîð, ïîêà âîçìîæíî.
   Çàìå÷àíèå. Åñëè ãðàô ñîäåðæèò êîíòóð, òî îáÿçàòåëüíî ïîÿâèòñÿ
ñòðîêà Ñi áåç íóëåé. Îòñþäà ñëåäóåò, ÷òî îïèñàííûé àëãîðèòì äàåò
âîçìîæíîñòü óñòàíîâèòü íàëè÷èå êîíòóðîâ â ãðàôå.
   Íà ðèñ. 4.6,à ïîêàçàí èñõîäíûé ãðàô (ðèñ.4.5,à), ðàçáèòûé íà óðîâ-
íè. Êàæäîé âåðøèíå vi ýòîãî ãðàôà ñîîòâåòñòâóåò íåêîòîðîå Nk, ò. å.
íåêîòîðîå k∈{0,1,2,3}. Ýòà ïîðÿäêîâàÿ ôóíêöèÿ vi→k çàäàåòñÿ òàá-
ëèöåé:
                   Âåðøèíà     A    B    C    D   E    .
                  Óðîâåíü (k ) 1    0    3    0   2    2

à                                  á
           A       .                              V!
                                         V                          V$
                                C
     B                                                     V#



                   E
     D
                                         V                 V"

     N    N     N        N!            N       N       N    N!
                    Ðèñ. 4.6. Ãðàô, ðàçáèòûé íà óðîâíè:
            à – èñõîäíûé ãðàô; á – ãðàô ñ íîâûìè âåðøèíàìè
                                                                     69


   Ïîðÿäêîâàÿ ôóíêöèÿ ïîçâîëÿåò ïåðåíóìåðîâàòü âåðøèíû òàê, ÷òî
âåðøèíû óðîâíÿ Ni èìåþò íîìåðà ìåíüøèå, ÷åì âåðøèíû óðîâíÿ Ni+1
(ðèñ. 4.6,á.). Ïîðÿäêîâàÿ ôóíêöèÿ èãðàåò âàæíóþ ðîëü âî ìíîãèõ êîì-
áèíàòîðíûõ çàäà÷àõ, íàïðèìåð ïîçâîëÿåò ðåøèòü çàäà÷ó âûáîðà ïðåä-
ïî÷òèòåëüíûõ îáúåêòîâ.
     4.6.2. Îïèñàíèå ìàøèííîãî àëãîðèòìà ðàçáèåíèÿ ãðàôà
                          íà óðîâíè
  Âîçìîæíûé âàðèàíò àëãîðèòìà âêëþ÷àåò ñëåäóþùèå øàãè.
  1. Ââîä ìàòðèöû ñìåæíîñòè (S) ãðàôà è åå ðàçìåðà (n);
  2. k=0;                   (íà÷àëüíûé íîìåð óðîâíÿ ðàçáèåíèÿ ãðàôà)
     v=0;                                (ñ÷åò÷èê îáðàáîòàííûõ âåðøèí)
  3. Öèêë j=1(1)n
             C[j]=0;                                (îáíóëåíèå âåêòîðà Ñ)
  4. Íà÷àëî öèêëà ïî v            (öèêë ïî îáðàáàòûâàåìûì âåðøèíàì)
      { k0=0; (ñ÷åò÷èê íóëåâûõ ñòîëáöîâ â öèêëå îáðàáîòêè âåðøèí)
  5. Öèêë j=1(1)n                            (çàïîëíåíèå âåêòîðîâ C è N)
  6.       { åñëè (C[j] ≠ –1)                  (âåðøèíà j íå îáðàáîòàíà )
                       { sum=0;           (íà÷àëî ñ÷åòà “1” äëÿ ñòîëáöà)
  7.                      öèêë i=1(1)n
                             sum = sum+S[i,j]; (ñóììèðîâàíèå ñòîëáöà j)
  8.                      åñëè (sum≠0)               (ñòîëáåö j íå ïóñòîé)
                             C[j]=sum;                      (çàïîëíåíèå Cj )
  9.                      èíà÷å
                             { C[j] = –1 ;          (âåðøèíà îáðàáîòàíà)
                                N[j]=k ;         (çàïèñü óðîâíÿ âåðøèíû)
                               v = v+1 ; (ïîäñ÷åò îáðàáîòàííûõ âåðøèí)
                                k0=k0+1; (ïîäñ÷åò íóëåâûõ ñòîëáöîâ)
                             }
           }                                            ( êîíåö öèêëà ïî j)
 10.       åñëè (k0 ≠ 0 )                          (åñòü íóëåâûå ñòîëáöû)
 11.          { öèêë i=1(1)n                        (èñêëþ÷åíèå â S ñòðîê
                                                   îáðàáîòàííûõ âåðøèí)
 12.               { åñëè (N[i]=k)      ( âåðøèíà i ïîïàëà íà óðîâåíü k)
 13.                      öèêë j=1(1)n S[i,j]=0; ( îáíóëåíèå ñòðîêè i )
                   }                                     (êîíåö öèêëà ïî i)
 14.         k=k+1;                   (ïîëó÷åíèå íîâîãî íîìåðà óðîâíÿ)
70



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