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

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

Голосов: 13

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
                }                            (åñëè íåò íóëåâûõ ñòîëáöîâ)
  15.     èíà÷å { âûâîä ñîîáùåíèÿ (“ ãðàôå åñòü êîíòóðû”) ;
                  ïåðåõîä íà êîíåö àëãîðèòìà – ï.18 ;
                 }
  16. } ïîêà (v<=n) ;         (óñëîâèå ïðîäîëæåíèÿ öèêëà ïî v – ï. 4)

  17. Âûâîä N ;                     (âåêòîð íîìåðîâ óðîâíåé âåðøèí)
  18. Êîíåö àëãîðèòìà.
   4.6.3. Ïîðÿäêîâàÿ ôóíêöèÿ êëàññîâ ýêâèâàëåíòíîñòåé ãðàôà.
        Âûäåëåíèå ïðåäïî÷òèòåëüíûõ îáúåêòîâ ñðàâíåíèÿ
   Êàê ïîêàçàíî â ï. 4.6.1, ãðàô áåç êîíòóðîâ ìîæíî óïîðÿäî÷èòü
ïî óðîâíÿì â ñîîòâåòñòâèè ñ ïîðÿäêîâîé ôóíêöèåé. Ðàññìîòðèì
êëàññû ýêâèâàëåíòíîñòåé ãðàôà ( êîíòóðû, ìàêñèìàëüíî ñèëüíî
ñâÿçíûå ïîäìíîæåñòâà âåðøèí). Êàê ìû âèäåëè â ï. 4.5.3, ýòè
êëàññû óïîðÿäî÷åíû è ãðàô êëàññîâ ýêâèâàëåíòíîñòåé (ðèñ. 4.4,á)
íå èìååò êîíòóðîâ, ïîýòîìó ìîæíî îïðåäåëèòü åãî óðîâíè. Íà-
ïðèìåð, ïîñëå ïðèìåíåíèÿ àëãîðèòìà ðàçáèåíèÿ ãðàôà íà óðîâíè
íà ðèñ. 4.7 ïîêàçàíû óðîâíè äëÿ ãðàôà êëàññîâ ýêâèâàëåíòíîñ-
òåé (ðèñ. 4.4,á).
   Èñõîäíûé ãðàô íà ðèñ. 4.3 áûë ïîñòðîåí íà îñíîâå îòíîøåíèÿ
ïðåäïî÷òåíèÿ ( ïðåâîñõîäñòâà – ñì. ï. 4.4) P f : (v,v')∈P f, ò. å. v'
ïðåâîñõîäèò v, à ãðàô êîíòóðîâ (ðèñ. 4.4,á) áûë ïîñòðîåí íà îñíî-
âå îòíîøåíèÿ R': “åñòü ïóòü èç K r â K s”, çíà÷èò, âèñÿ÷èå âåðøè-
íû (íå èìåþùèå ïðåâîñõîäÿùèõ
âåðøèí) ãðàôà íà ðèñ. 4.7 (ò. å.
êëàññû K 4 ={v 4, v 5} è K 6 ={v 8}) ñî-  K!             K"
äåðæàò âåðøèíû-îáúåêòû ñðàâíå-
íèÿ, êîòîðûå ÿâëÿþòñÿ ïðåäïî÷òè-                   K
òåëüíûìè â äàííîì àíàëèçå è íå-                          K#
ñðàâíèìû ìåæäó ñîáîé ïî èíôîð-
                                          K                     K$
ìàöèè, ñîäåðæàùåéñÿ â ãðàôå. Òà-
êèì îáðàçîì, çàäà÷à âûáîðà ïðåä-
ïî÷òèòåëüíûõ îáúåêòîâ èç ìíîæå-           N       N     N     N!
ñòâà ñðàâíèâàåìûõ ìåæäó ñîáîé ïî
íåñêîëüêèì êðèòåðèÿì ðåøåíà, íî            Ðèñ. 4.7. Óðîâíè ãðàôà
ýòî íå åäèíñòâåííûé ìåòîä.               êëàññîâ ýêâèâàëåíòíîñòåé

                                                                   71


                   4.7. Âûäåëåíèå ÿäåð ãðàôà
   Â òåîðèè ãðàôîâ âîçìîæíî èñïîëüçîâàòü ìåòîäû îòûñêàíèÿ ÿäåð ãðà-
ôà G, ñîñòîÿùèõ èç ïîäìíîæåñòâà íåñðàâíèìûõ ìåæäó ñîáîé îáúåêòîâ,
êàê îñíîâó äëÿ âûäåëåíèÿ íàèáîëåå ïðåäïî÷òèòåëüíûõ îáúåêòîâ. Ðàñ-
ñìîòðèì ïîíÿòèÿ è ïîäõîäû, íåîáõîäèìûå äëÿ ðåøåíèÿ ýòîé çàäà÷è.
           4.7.1. Âíóòðåííå óñòîé÷èâîå ïîäìíîæåñòâî
   Ïóñòü çàäàí ãðàô G=(V,Ã) ; ïîäìíîæåñòâî S⊂V íàçûâàåòñÿ âíóòðåí-
íå óñòîé÷èâûì, åñëè S∩ÃS=∅, ò. å. íèêàêèå äâå âåðøèíû S íå ñìåæíû
(íå ñâÿçàíû äóãîé ).
   Èç îïðåäåëåíèÿ ñëåäóåò, ÷òî âåðøèíà, èìåþùàÿ ïåòëþ (v,v), íå ìî-
æåò ïðèíàäëåæàòü âíóòðåííå óñòîé÷èâîìó ïîäìíîæåñòâó, ïîýòîìó äà-
ëåå áóäóò ðàññìàòðèâàòüñÿ òîëüêî ãðàôû áåç ïåòåëü. Äëÿ ãðàôà ñ ïåòëÿ-
ìè ìîæíî ðàññìàòðèâàòü ñîîòâåòñòâóþùèé ãðàô áåç ïåòåëü.
                               Ïðèìåð
   Ðàññìîòðèì ãðàô íà ðèñ. 4.8. Ïîäìíîæåñòâà S1={A,D}, S2={B,E},
S3={A,C,D} âíóòðåííå óñòîé÷èâû. Ïðîâåðèì ýòî, íàïðèìåð, äëÿ S1 :
                                       ÃA={B,E}, ÃD={E},
            B        C                 ÃS1=ÃA∪ÃD={B,E},
                                    S1 ∩ÃS1={A,D}∩{B,E}=∅.
A                    D      Ìàêñèìàëüíîå âíóòðåííå óñòîé÷èâîå ïîä-
                         ìíîæåñòâî. Ýòî âíóòðåííå óñòîé÷èâîå ïîä-
                         ìíîæåñòâî, íå ÿâëÿþùååñÿ ñîáñòâåííûì ïîä-
            E
                         ìíîæåñòâîì íèêàêîãî äðóãîãî âíóòðåííå óñ-
    Ðèñ. 4.8. Îðãðàô     òîé÷èâîãî ïîäìíîæåñòâà. Íàïðèìåð, â ïðå-
       áåç ïåòåëü        äûäóùåì ïðèìåðå S1⊂S3, ãäå S3 – ìàêñèìàëü-
íîå âíóòðåííå óñòîé÷èâîå ïîäìíîæåñòâî. Ãðàô ìîæåò îáëàäàòü íåñêîëü-
êèìè ìàêñèìàëüíûìè âíóòðåííå óñòîé÷èâûìè ïîäìíîæåñòâàìè.
     4.7.2. Ìåòîä ïîèñêà ñåìåéñòâà ìàêñèìàëüíûõ âíóòðåííå
             óñòîé÷èâûõ ïîäìíîæåñòâ (ìåòîä Ìàãó)
    Ýòîò ìåòîä èñïîëüçóåò ñâîéñòâà áóëåâûõ óðàâíåíèé. Ïóñòü S –
íåêîòîðîå âíóòðåííå óñòîé÷èâîå ïîäìíîæåñòâî. Ëþáîé âåðøèíå ãðà-
ôà vi∈V ïîñòàâèì â ñîîòâåòñòâèå áóëåâó ïåðåìåííóþ xi, ïîëàãàÿ, ÷òî,
åñëè vi ∉ S, òî xi = 0 èëè xi = 1 . Ââåäåì ïåðåìåííóþ αij:
     äëÿ j≠i, åñëè vj∈Ãvi (ò. å. âåðøèíû ñìåæíûå, vj – êîíåö äóãè), òî
αij=1,
72


    åñëè vj∉Ãvi (ò. å. âåðøèíû íåñìåæíûå), òî αij=0,
÷òî ñîîòâåòñòâóåò ìàòðèöå ñìåæíîñòè.
   Äëÿ ëþáîé ïàðû âåðøèí vi è vj (ñ ó÷åòîì S∩ÃS=∅) ñïðàâåäëèâî óò-
âåðæäåíèå :
                  (i≠j ; vi∈Ãvj èëè vj∈Ãvi) ⇒ (vi∉S èëè vj∉S),
   (çäåñü èëè îçíà÷àåò îïåðàöèþ íåèñêëþ÷àþùåå “èëè”), ò. å. òîëüêî
îäèí èç êîíöîâ äóãè ìîæåò âõîäèòü â S, ëèáî îáà íå âõîäÿò. Ýòî ìîæíî
çàïèñàòü òàê äëÿ âåðøèí, íå âõîäÿùèõ â S (ïðè i≠j):

                     (αij ∨ α ji ) ∨ xi ∨ õ j = 1,
                    èëè (αij α ji ) ∨ xi ∨ õ j = 1.

   Âûïîëíèâ áóëåâî óìíîæåíèå ïî âñåì âåðøèíàì ãðàôà, ïðèõîäèì ê
óðàâíåíèþ

                                       (
                 Ô S = ∏∏ αij α ji ∨ xi ∨ õ j = 1 ,       )
                        i       j ≠i
çäåñü ∨ – çíàê äèçúþíêöèè; ∏ – çíàê áóëåâà óìíîæåíèÿ (êàæäûé ÷ëåí
ó÷èòûâàåòñÿ îäèí ðàç).
   Èìåÿ â âèäó, ÷òî S ∩ Ö1S = ∅, ò. å. ìíîæåñòâî âåðøèí èç âíóòðåííå
óñòîé÷èâîãî ïîäìíîæåñòâà è âíå åãî íå ïåðåñåêàþòñÿ, ìîæíî óïðîñ-
òèòü ýòî óðàâíåíèå, çàìåíèâ âûðàæåíèå αij α ji íà αij

                                           (
                  Ô S = ∏∏ αij ∨ xi ∨ õ j = 1,     )
                            i     j ≠i

                                                      
              èëè Ô S = ∏  xi ∨  ∏ αij ∨ õ j
                                 j ≠i
                                               (       )   = 1.
                                                         
                                                                    (4.1)
                        i                             

   Äëÿ äàëüíåéøåãî óïðîùåíèÿ óðàâíåíèÿ íåîáõîäèìî ðàñêðûòü ñêîá-
êè è ïðèâåñòè ïîäîáíûå ÷ëåíû ñ ó÷åòîì îïåðàöèè ïîãëîùåíèÿ : x∨x⋅y=x
è îïåðàöèè ïðèâåäåíèÿ ïîäîáíûõ ÷ëåíîâ x⋅x=x.
    ðåçóëüòàòå óïðîùåíèÿ ïîëó÷èì, ÷òî äëÿ êàæäîãî ÷ëåíà óðàâíåíèÿ
ÔS ñîâîêóïíîñòü âñåõ âåðøèí, ñîîòâåòñòâóþùèõ ïåðåìåííûì, íå ïðåä-
ñòàâëåííûì â íåì, îáðàçóåò ìàêñèìàëüíîå âíóòðåííå óñòîé÷èâîå ïîä-
ìíîæåñòâî ãðàôà.
                                                                 73


                                   Ïðèìåð
       Ðàññìîòðèì áóëåâó ìàòðèöó (ðèñ.4.9) îðãðàôà ïðåäñòàâëåííîãî íà ðèñ.
4.8.
                              Äëÿ ýëåìåíòîâ ìàòðèöû αi j = 1 ïîëó÷àåì ÷ëå-
       A   B   C   D   E    íû óðàâíåíèÿ âèäà
 A     0   1   0   0   1
 B     1   0   1   1   0             α AB ∨ a ∨ b = 0 ∨ a ∨ b = a ∨ b ,
 C     0   0   0   0   0    à äëÿ ýëåìåíòîâ ìàòðèöû αij=0 :
 D     0   0   0   0   1               α AÑ ∨ a ∨ ñ = 1 ∨ a ∨ ñ = 1.
 E     0   0   0   1   0
                                Ïîñêîëüêó ÷ëåíû óðàâíåíèÿ âèäà ( a ∨ b ) è
     Ðèñ. 4.9. Áóëåâà       ( b ∨ a ) ïîäîáíû, òî óðàâíåíèå ÔS ñ ðàçíûìè ÷ëå-
     ìàòðèöà îðãðàôà        íàìè èìååò âèä

               Ô S = (a ∨ b ) (a ∨ e ) (b ∨ ñ )(b ∨ d )(d ∨ e ) = 1.
       Óïðîùàÿ, ïîëó÷àåì

                       Ô S = (a ∨ be )(b ∨ ñd )(d ∨ e ) = 1,

è, íàêîíåö, Ô S = abd ∨ añd ∨ be = 1.
    Òàêèì îáðàçîì, ãðàô íà ðèñ. 4.8 îáëàäàåò òðåìÿ ìàêñèìàëüíûìè
âíóòðåííå óñòîé÷èâûìè ïîäìíîæåñòâàìè : {C,E}, {B,E}, {A,C,D}.
                   4.7.3. Âíåøíå óñòîé÷èâîå ïîäìíîæåñòâî
   Ïóñòü çàäàí ãðàô G=(V,Ã) ; ïîäìíîæåñòâî T⊂V íàçûâàåòñÿ âíåøíå
óñòîé÷èâûì, åñëè (∀v∉T) T∩Ãv ≠ ∅, ò. å. âåðøèíà v, íå ïðèíàäëåæàùàÿ
Ò, ñâÿçàíà ïî êðàéíåé ìåðå ñ îäíîé âåðøèíîé èç Ò äóãîé, íà÷àëî êîòî-
ðîé ëåæèò â V–Ò. Ýòî ìîæíî çàïèñàòü òàêæå â ñëåäóþùåì âèäå:
                     (∀v ∈ V) ({v}∪Ãv) ∩T ≠ ∅.                  (4.2)
                                Ïðèìåð
    Äëÿ ãðàôà íà ðèñ. 4.8 ïîäìíîæåñòâî {C,D,E} âíåøíå óñòîé÷èâîå,
÷òî ëåãêî ïðîâåðÿåòñÿ : T={C,D,E}, ÃA={B,E}, ÃB={A,C,D},
                   T∩ÃA={C,D,E}∩{B,E}={E}≠∅,
                T∩ÃB={C,D,E}∩{A,C,D}={C,D}≠∅.
   Î÷åâèäíî, ÷òî åñëè Ò⊂Ò'⊂V, òî Ò'– âíåøíå óñòîé÷èâîå ïîäìíîæå-
ñòâî. Ëþáàÿ âèñÿ÷àÿ âåðøèíà v (Ãv=∅, ò. å. èç íåå íå èñõîäèò äóãà)
ïðèíàäëåæèò êàæäîìó âíåøíå óñòîé÷èâîìó ïîäìíîæåñòâó.
74


   Ìèíèìàëüíîå âíåøíå óñòîé÷èâîå ïîäìíîæåñòâî íå ñîäåðæèò ñòðî-
ãî íèêàêîãî äðóãîãî âíåøíå óñòîé÷èâîãî ïîäìíîæåñòâà, íàïðèìåð äëÿ
ãðàôà íà ðèñ. 4.8 ïîäìíîæåñòâî {C,E} âíåøíå óñòîé÷èâîå è ìèíèìàëü-
íîå. Ãðàô ìîæåò îáëàäàòü íåñêîëüêèìè ìèíèìàëüíûìè âíåøíå óñòîé-
÷èâûìè ïîäìíîæåñòâàìè.
              4.7.4. Ìåòîä ïîèñêà ñåìåéñòâà ìèíèìàëüíûõ
             âíåøíå óñòîé÷èâûõ ïîäìíîæåñòâ (ìåòîä Ìàãó)
   Èç óñëîâèÿ (4.2) ñëåäóåò, ÷òî ïîäìíîæåñòâî Ò äîëæíî ñîäåðæàòü âìå-
ñòå ñ vi ïî êðàéíåé ìåðå îäíó èç âåðøèí Ãvi. Ñëåäîâàòåëüíî, ñïðàâåäëè-
âî óñëîâèå
                 (∀vi ∈V) ( vi ∈T èëè (∃vj)( vj ∈Ò è vj ∈Ãvi)).
   Ïóñòü xi =1, åñëè vi∈Ò è αij=1 (αij îïðåäåëåíî âûøå), òîãäà

                                               
                          ∏  xi ∨  ∑ αij x j   = 1,
                                             
                            i          i       

                                    
     Òàê êàê (∀vi)  xi ∨  ∑ αij x j   = ∑ αij x j ,
                                    
                          i             j


òî                          ÔT =    ∏∑ αij x j = 1.             (4.3)
                                     i       j

    Ïðè ðàçëîæåíèè ÔT ïîñëå îïåðàöèé ïîãëîùåíèÿ (x∨x⋅y=x) è ïðèâå-
äåíèÿ ïîäîáíûõ ÷ëåíîâ êàæäûé ÷ëåí ýòîãî ðàçëîæåíèÿ äàåò ìèíèìàëü-
íîå âíåøíå óñòîé÷èâîå ïîäìíîæåñòâî. Äåéñòâèòåëüíî, òàêîé ÷ëåí íå
ñîäåðæèò ïåðåìåííûõ ñ îòðèöàíèåì, è ïîýòîìó èç ìíîæåñòâà âåðøèí
vi, ñîîòâåòñòâóþùèõ ïåðåìåííûì xi, âñòðå÷àþùèõñÿ â ýòîì ÷ëåíå,
íåëüçÿ óäàëèòü íè îäíó.
                                   Ïðèìåð
    Ðàññìîòðèì ãðàô (ðèñ. 4.8) è åãî áóëåâó ìàòðèöó (ðèñ. 4.9).
    Òàê, äëÿ 1-é ñòðîêè ìàòðèöû ìîæíî ïîëó÷èòü âûðàæåíèå
                       αAA a ∨ αAB b ∨ αAE e = a ∨ b ∨ e.
    Àíàëîãè÷íûå âûðàæåíèÿ ìîæíî ïîëó÷èòü äëÿ îñòàëüíûõ ñòðîê. Â
ñèëó (4.3)
                 ÔT = (a ∨ b ∨ e) (b ∨ a ∨ c ∨ d) c (d ∨ e) = 1.
                                                                    75


     Óïðîùàÿ, èìååì
                       ÔT = (a ∨ b ∨ e) c (d ∨ e) = 1,
èëè ÔT = acd ∨ bcd ∨ ce = 1.
   Òàêèì îáðàçîì, ãðàô îáëàäàåò òðåìÿ ìèíèìàëüíûìè âíåøíå óñòîé-
÷èâûìè ïîäìíîæåñòâàìè :
                         {A,C,D}, {B,C,D}, {C,E}.
                                       4.7.5. ßäðà ãðàôà
    Ïóñòü çàäàí ãðàô G=(V,Ã). Ïîäìíîæåñòâî N⊂V íàçûâàåòñÿ ÿäðîì
ãðàôà G, åñëè N îäíîâðåìåííî âíóòðåííå è âíåøíå óñòîé÷èâîå ïîä-
ìíîæåñòâî, ò. å.
    (∀vi ∈N) N∩Ãvi=∅, (ò. å. âåðøèíû N íå ñìåæíû);
    (∀vj ∉N) N∩Ãvj≠∅, (ò. å. â N âõîäÿò êîíöû äóã, íà÷àëà êîòîðûõ âíå N).
    Îòñþäà ñëåäóåò, ÷òî ÿäðî ñîäåðæèò âñÿêóþ âåðøèíó vi ñ Ãvi = ∅ (ò. å.
âèñÿ÷óþ âåðøèíó) è íå ñîäåðæèò âåðøèí ñ ïåòëÿìè. Î÷åâèäíî, ÷òî ∅
íå åñòü ÿäðî ãðàôà.
    Ãðàô ìîæåò îáëàäàòü íåñêîëüêèìè ÿäðàìè èëè âîîáùå íå èìåòü ÿäðà.
                     4.7.6. Ïîèñê ÿäåð ãðàôà ( ìåòîä Ìàãó)
   Ïîëàãàåì xi =1, åñëè vi ∈N è ðàññìîòðèì óðàâíåíèÿ ÔS=1 è ÔÒ=1.
Òàê êàê ýòè ðàâåíñòâà äîëæíû âûïîëíÿòüñÿ, òî
                            ÔN = ÔS·ÔÒ = 1,

                                                                   
ò. å.        
             
                 ∏     xi ∨
                      
                               ∏(              )
                                      αij ∨ õ j   
                                                 
                                                        ∏∑      αij x j  = 1,
                                                                        
                i            j ≠i                  i   j           

                                                                 
èëè                  ∏  xi ∑ αij x j ∨ xi ∏ (αij ∨ õ j )  = 1.
                                                         
                                                                                 (3.4)
                      i        j               j ≠i              
    ðåçóëüòàòå ðåøåíèÿ óðàâíåíèÿ ÔN ïîëó÷èì ÿäðà ãðàôà.
                                Ïðèìåð
   Äëÿ ãðàôà íà ðèñ. 4.8. ñîãëàñíî (3.4) ïî áóëåâîé ìàòðèöå íà ðèñ.4.9
íàõîäèì ÷ëåíû óðàâíåíèÿ ÔN (çàìå÷àÿ, ÷òî xx =0, õõ=õ, õ∨õy=x) :
                 a (a ∨ b ∨ e) ∨ a ( b e ) = a (b ∨ e) ∨ a ( b e ),
        b ( a ∨ b ∨ c ∨ d) ∨ b ( a ñ d ) = b ( a ∨ c ∨ d) ∨ b ( a ñ d ),
76


                        d (d ∨ e) ∨ d e = d e ∨ d e ,
                       e (d ∨ e) ∨ e d = d e ∨ d e.
       ÔN = ( a b ∨ a e ∨ a b e ) ( b a ∨ b c ∨ b d) c ( d e ∨ d e ) =
                  = ( a b ∨ a e ∨ a b e )( b c) ( d e∨d e ) =
       = ( a b ce ∨ a b c e ) ( d e ∨ d e ) = a b c d e ∨ a b cd e = 1,

ò. å. ÔN = a b c d e ∨ a b cd e = 1.
    Òàêèì îáðàçîì, ãðàô îáëàäàåò äâóìÿ ÿäðàìè : N1={C,E} è N2={A,C,D},
êîòîðûå âûäåëåíû íà ðèñ. 4.10.
    Èç ðèñ. 4.10 âèäíî, ÷òî ìåæäó âåðøèíàìè ÿäðà ïðîèçâîëüíîãî
ãðàôà ìîæåò íàðóøàòüñÿ îòíîøåíèå ïðåâîñõîäñòâà : (v,v')∈U, åñëè
(v,v')∈Pf, ò. å. åñëè v' ïðåâîñõîäèò v, òî ñóùåñòâóåò äóãà (v,v')∈U. Ýòî
ïðîèñõîäèò âñëåäñòâèå ïðèñóòñòâèÿ êîíòóðîâ â ãðàôå, íàïðèìåð âåð-
øèíû êîíòóðà {E,D}, ïðèíàäëåæàò ðàçíûì ÿäðàì, à òàêæå èç-çà íà-
ðóøåíèÿ îòíîøåíèÿ òðàíçèòèâíîñòè ìåæäó âåðøèíàìè ÿäåð, íàïðè-
ìåð ìåæäó âåðøèíàìè A è C åñòü ïóòü (À,Â,Ñ). Ïîýòîìó ïîèñê ïðåä-
ïî÷òèòåëüíûõ îáúåêòîâ ñ èñïîëüçîâàíèåì ÿäåð ãðàôà ìîæíî ðàçáèòü
íà äâà ýòàïà.


                                    B            C
                   N                                     N

                        A                       D


                                     E

                  Ðèñ. 4.10. Ãðàô ñ âûäåëåííûìè ÿäðàìè

   1 ýòàï. Â èñõîäíîì ãðàôå îñóùåñòâëÿåòñÿ ïîèñê êëàññîâ ýêâèâà-
ëåíòíîñòåé âåðøèí (ò. å. êîíòóðîâ) â ñîîòâåòñòâèè ñ àëãîðèòìîì ï.
4.5.2 è òðàíñôîðìàöèÿ èñõîäíîãî ãðàôà â ãðàô êëàññîâ ýêâèâàëåíò-
íîñòåé, êîòîðûé ÿâëÿåòñÿ ãðàôîì áåç êîíòóðîâ, ò. å. àöèêëè÷åñêèì.
   2 ýòàï. Â òåîðèè ãðàôîâ äîêàçàíà ñëåäóþùàÿ òåîðåìà : ãðàô áåç
êîíòóðîâ âñåãäà îáëàäàåò ÿäðîì. Íà îñíîâå ýòîé òåîðåìû îñóùåñòâ-
ëÿåòñÿ ïîèñê ÿäåð àöèêëè÷åñêîãî ãðàôà è âûäåëåíèå ñðåäè íèõ âèñÿ-
                                                                          77


      à                                     á
                                    K!                        K!

                    B          C                       N
      K
                                                  K
           A
                                                       N
                                D
                                                              K
                                         K
                    E


             Ðèñ. 4.11. Ïîèñê ïðåäïî÷òèòåëüíûõ îáúåêòîâ:
           à – âûäåëåíèå êëàññîâ ýêâèâàëåíòíîñòåé âåðøèí;
                        á – âûäåëåíèå ÿäåð ãðàôà
÷èõ âåðøèí. Ýòîò ïðîöåññ ïîèñêà ïðåäïî÷òèòåëüíûõ îáúåêòîâ ïðî-
èëëþñòðèðîâàí íà ðèñ. 4.11.
     4.7.7. Âûäåëåíèå ïðåäïî÷òèòåëüíûõ îáúåêòîâ â ÿäðàõ ãðàôà
   Ðàññìîòðèì ñïîñîá, êîòîðûé ââîäèò â ïðîöåññ ïîèñêà ÿäåð ãðàôà
îòíîøåíèå ïðåâîñõîäñòâà, ÷òî ïîçâîëÿåò îáúåäèíèòü â îäèí àëãîðèòì
ýòàïû âûäåëåíèÿ êîíòóðîâ â ãðàôå è ïîèñêà ïðåäïî÷òèòåëüíûõ îáúåê-
òîâ â ÿäðàõ ãðàôà ïóòåì ñòÿãèâàíèÿ êîíòóðîâ.
   Ïóñòü Pf îòíîøåíèå ïðåâîñõîäñòâà : (v,v')∈Pf → (v,v')∈U â ãðàôå
G=(V,U). Â äóãå (v,v') âåðøèíó-êîíåö äóãè (v') áóäåì íàçûâàòü îñòàâëÿ-
åìîé (ïðåâîñõîäÿùåé, ïðåäïî÷òèòåëüíîé), à âåðøèíó-íà÷àëî äóãè – èñ-
êëþ÷àåìîé.
   Ïóñòü Ð – ìíîæåñòâî îñòàâëÿåìûõ âåðøèí v', à V–P – ìíîæåñòâî
èñêëþ÷àåìûõ âåðøèí v. Ìíîæåñòâî Ð äîëæíî óäîâëåòâîðÿòü ñëåäóþ-
ùèì äâóì ñâîéñòâàì:
   1) âíóòðåííåé óñòîé÷èâîñòè:
    ∀ v∈P è ∀ v'∈P → (v, v')∉U, ò. å. íèêàêîé îáúåêò èç ìíîæåñòâà Ð íå
ïðåâîñõîäèòñÿ äðóãèì îáúåêòîì èç Ð;
   2) âíåøíåé óñòîé÷èâîñòè :
    ∀ v∈V–P ∃ v'∈P → (v,v')∈U, ò. å. äëÿ ëþáîé èç èñêëþ÷àåìûõ âåðøèí
v ñóùåñòâóåò ñðåäè îñòàâëÿåìûõ ïî êðàéíåé ìåðå îäíà âåðøèíà v', êî-
òîðàÿ ïðåâîñõîäèò v.

78


   Ïîäìíîæåñòâî âåðøèí, óäîâëåòâîðÿþùèõ îáîèì ñâîéñòâàì, ñîñòàâ-
ëÿþò ÿäðà ãðàôà ñ ó÷åòîì îòíîøåíèÿ ïðåäïî÷òåíèÿ Ðf.
   Ïóñòü å∈K (ãäå K– êîíòóð) åñòü ýëåìåíò (îáúåêò), ðàññìàòðèâàåìûé
êàê ýêâèâàëåíòíûé äðóãèì îáúåêòàì èç êîíòóðà K â ãðàôå G. Ïîëîæèì,
÷òî v∈V–K ïðåâîñõîäèò å, åñëè ñóùåñòâóåò e'∈K òàêîé, ÷òî v ïðåâîñõî-
äèò e', ò. å. v ïðåâîñõîäèò K â öåëîì, òàêîå ïðåîáðàçîâàíèå â òåîðèè
ãðàôîâ íàçûâàåòñÿ ñòÿãèâàíèåì êîíòóðà K.
   Íà îñíîâå ââåäåííîãî îòíîøåíèÿ ïðåâîñõîäñòâà ðàçðàáîòàí àëãîðèòì,
êîòîðûé ïîçâîëÿåò âåñòè ïîèñê ÿäåð ãðàôà ñîâìåñòíî ñî ñòÿãèâàíèåì
âñòðå÷àþùèõñÿ êîíòóðîâ. Îñíîâíûå ýòàïû àëãîðèòìà :
   1. Ðåøåíèå çàäà÷è ïîèñêà êîíòóðîâ â ãðàôå è ïîëó÷åíèå âåêòîðà V ñ
íîìåðàìè êîíòóðîâ.
   2. Â öèêëàõ ïðîñìîòðà êîíòóðîâ è âåðøèí âíå êîíòóðà îïðåäåëåíèå
âåðøèí âíå êîíòóðà, ïðåâîñõîäÿùèõ õîòÿ áû îäíó âåðøèíó êîíòóðà, è
èñêëþ÷åíèå òàêîãî êîíòóðà èç âåêòîðà V.
   Îñòàâøèåñÿ â âåêòîðå V âåðøèíû è êîíòóðû ñîñòàâëÿþò ÿäðà ãðàôà.
Åñëè ÿäåð ãðàôà áîëüøå îäíîãî, òî îíè íåñðàâíèìû ïî èíôîðìàöèè,
ñîäåðæàùåéñÿ â ãðàôå, ïîýòîìó íåîáõîäèì äîïîëíèòåëüíûé àíàëèç
îáúåêòîâ ñðàâíåíèÿ.
     4.7.8. Îïèñàíèå ìàøèííîãî àëãîðèòìà ïîèñêà ÿäåð ãðàôà
   Âîçìîæíûé âàðèàíò àëãîðèòìà âêëþ÷àåò ñëåäóþùèå øàãè.
   1. Ââîä áóëåâîé ìàòðèöû ñìåæíîñòè ãðàôà (S) è åå ðàçìåðà (n).
   2. Âûçîâ ïîäïðîãðàììû ïîèñêà êîíòóðîâ CONTUR (S, n, V, nk),
 ãäå S, n – âõîäíûå äàííûå, à ðåçóëüòàòû: V– âåêòîð íîìåðîâ êîíòóðîâ â
ãðàôå, nk – êîëè÷åñòâî êîíòóðîâ.
   3. Öèêë k=1(1)nk                                  (ïî íîìåðàì êîíòóðîâ)
   4. { öèêë i=1(1)n                          (âûäåëåíèå âåðøèí êîíòóðà)
   5.       { åñëè (Vi=k)                  (âåðøèíà Vi âõîäèò â êîíòóð k )
   6.           { öèêë j=1(1)n            (âûäåëåíèå âåðøèí âíå êîíòóðà)
   7.               { åñëè (Vi ≠Vj ∧ Sij =1)      ( âåðøèíà âíå êîíòóðà Vj
                                     ïðåâîñõîäèò âåðøèíó èç êîíòóðà Vi )
   8.                   { öèêë m=1(1)n       (èñêëþ÷åíèå âåðøèí êîíòóðà)
   9.                      { åñëè (Vm=k)             (ýòî âåðøèíà êîíòóðà )
                               Vm=0 ;         (èñêëþ÷åíèå íîìåðà êîíòóðà
                                                              èç âåêòîðà V )
   10.                      }                            (êîíåö öèêëà ïî m)

                                                                         79


     11.                 ïåðåõîä íà ïðîäîëæåíèå öèêëà ïî k ;
     12.               }
     13.           }                                (êîíåö öèêëà ïî j)
     14.        }
     15.   }                                         (êîíåö öèêëà ïî i)
     16. }                                         (êîíåö öèêëà ïî k)
     17. Âûâîä âåêòîðà V ( íîìåðà êîíòóðîâ, îáðàçóþùèõ ÿäðà ãðàôà).




                    Áèáëèîãðàôè÷åñêèé ñïèñîê
   1. Êîôìàí À. Ââåäåíèå â ïðèêëàäíóþ êîìáèíàòîðèêó. Ì.: Íàóêà, 1975.
480 ñ.
   2. Áåëîâ Â. Â. è äð. Òåîðèÿ ãðàôîâ. Ì.: Âûñøàÿ øêîëà, 1976. 392 ñ.
   3. Áàñàêåð Ð., Ñààòè Ò. Êîíå÷íûå ãðàôû è ñåòè. Ì.: Íàóêà, 1974.
386 ñ.
   4. Ïðîêóøåâ Ë. À. Äèñêðåòíàÿ ìàòåìàòèêà – 2: Ìåòîäè÷åñêèå óêàçà-
íèÿ ïî àëãîðèòìèçàöèè çàäà÷ òåîðèè ãðàôîâ/ ÃÓÀÏ. ÑÏá., 1998. 24 ñ.




80



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