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

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

Голосов: 13

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    îáîçíà÷àòü G=(V, U ). Ïðè òàêîì îïðåäåëåíèè ãðàôà îòíîøåíèå èíöè-
äåíòíîñòè âåðøèí è ðåáåð çàäàåòñÿ íå ÿâíî. Íàïðèìåð, äëÿ ãåîìåòðè-
÷åñêîãî ãðàôà (ðèñ.1.2) ñîîòâåòñòâóþùèé àáñòðàêòíûé ãðàô ìîæíî îïè-
ñàòü êàê ìíîæåñòâà:
                    âåðøèí V={v1, v2, v3, v4} è
        ðåáåð U ={[v1, v2], [v2, v3], [v3, v4], [v4, v2], [v4, v1]}.
   Ìîæíî ââåñòè îòîáðàæåíèå èíöèäåíòíîñòè (èëè èíöèäåíöèè) – Ã
ãðàôà G. Åñëè âåðøèíû v, w∈V ÿâëÿþòñÿ ãðàíè÷íûìè (êîíöåâûìè) òî÷-
êàìè ðåáðà u ∈ U , òî ýòî ìîæíî îáîçíà÷èòü u ~[v, w] (÷èòàåòñÿ “ u
ñîåäèíÿåò âåðøèíû v è w”) è ââåñòè îòîáðàæåíèå Ã( u )=[v, w] – ýòî
îçíà÷àåò, ÷òî ðåáðî u èíöèäåíòíî êàæäîé èç âåðøèí v è w è íàîáîðîò
– âåðøèíû èíöèäåíòíû ðåáðó.

          L              L                    L       u1     L

                                                      u5            u2
                                              u4

          L"              L!                   L"      u3      L!

 Ðèñ. 1.2. Ãåîìåòðè÷åñêèé ãðàô           Ðèñ. 1.3. Ãåîìåòðè÷åñêèé ãðàô
      áåç îáîçíà÷åíèÿ ðåáåð                  ñ îáîçíà÷åíèåì ðåáåð


   Òîãäà ãðàô G ìîæíî îïèñàòü êàê ìàòåìàòè÷åñêóþ ñèñòåìó G=(V, U ,
Ã), ñîñòîÿùóþ èç äâóõ ìíîæåñòâ V (âåðøèí) è U (ðåáåð) è îòîáðàæåíèÿ
à èíöèäåíòíîñòè ìíîæåñòâà U â V&V (ìíîæåñòâî íåóïîðÿäî÷åííûõ
ïàð ýëåìåíòîâ âèäà [v, w]∈V).
   Íàïðèìåð, äëÿ ãåîìåòðè÷åñêîãî ãðàôà (ðèñ.1.3) ñîîòâåòñòâóþùèé
àáñòðàêòíûé ãðàô ìîæíî îïèñàòü êàê ìíîæåñòâà:
V={v1, v2, v3, v4}, U ={ u 1, u 2, u 3, u 4, u 5} è îòîáðàæåíèÿ èíöèäåíòíîñòè
Ã={ u 1~[v1, v2], u 2~[v2, v3], u 3~[v3, v4], u 4~[v4, v1], u 5~[v4, v2]}.
   Ïîñêîëüêó îòîáðàæåíèå èíöèäåíòíîñòè ãðàôà à âêëþ÷àåò ìíîæå-
ñòâî ðåáåð ãðàôà U , ïîñòîëüêó îïèñàíèå ãðàôà êàê ñîâîêóïíîñòè ìíî-
æåñòâà âåðøèí V è îòîáðàæåíèÿ Ã ìíîæåñòâà U â V&V âèäà G=(V, Ã)
ïîëíîñòüþ îïðåäåëÿåò ãðàô.
                                                                          11


       1.3.2. Ëîêàëüíûå ñâîéñòâà íåîðèåíòèðîâàííûõ ãðàôîâ
   Äëÿ îïèñàíèÿ ðàçëè÷íûõ ñòðóêòóðíûõ ñâîéñòâ ãðàôîâ ïîëåçíî ââåñ-
òè ðÿä äîïîëíèòåëüíûõ ïîíÿòèé, êîòîðûå îñîáåííî íàãëÿäíî èëëþñò-
ðèðóþòñÿ íà ïðèìåðå ãåîìåòðè÷åñêèõ ãðàôîâ, ïîêàçàííûõ âûøå, à òàê-
æå íà ðèñ. 1.4.
   Åñëè u =[v, w], òî v è w íàçûâàþòñÿ ãðàíè÷íûìè òî÷êàìè u íåçàâè-
ñèìî îò òîãî, ÿâëÿåòñÿ ãðàô ãåîìåòðè÷åñêèì èëè íåò.
   Ïåòëåé u =[v, v] íàçûâàåòñÿ ðåáðî u c åäèíñòâåííîé ãðàíè÷íîé òî÷-
êîé, ò. å. ïåòëÿ èíöèäåíòíà îäíîé âåðøèíå, íàïðèìåð ïåòëè u 4 è u 5 íà
ðèñ. 1. 4.
                                      Ïàðàëëåëüíûìè (êðàòíûìè) íàçûâà-
               u1
                                   þòñÿ ðåáðà, åñëè îíè ñîåäèíÿþò îäíè
  L                       L       è òå æå âåðøèíû, íàïðèìåð u 1~[v1, v2]
               u2
                           u3      è u 2~[v1, v2].  ÷àñòíîñòè, äâå ïåòëè,
                                   èíöèäåíòíûå îäíîé è òîé æå âåðøèíå,
 L"
                        L!         ÿâëÿþòñÿ ïàðàëëåëüíûìè, íàïðèìåð
                     u4            u 4 è u 5.
                              u5      Ãðàô G, èìåþùèé ïàðàëëåëüíûå
        Ðèñ. 1.4. Ïðèìåð           ðåáðà, íàçûâàåòñÿ ìóëüòèãðàôîì, íà-
 íåîðèåíòèðîâàííîãî ãðàôà          ïðèìåð ìóëüòèãðàôû íà ðèñ. 1.1 è 1.4.
                                      Ñìåæíûìè âåðøèíàìè íàçûâàþòñÿ
âåðøèíû v è w, îáðàçóþùèå ãðàíè÷íûå òî÷êè ðåáðà u ~[v, w]. Îäíà
âåðøèíà ìîæåò èìåòü íåñêîëüêî ñìåæíûõ âåðøèí, åñëè â íåé ñõîäÿòñÿ
íåñêîëüêî ðåáåð, íàïðèìåð äëÿ âåðøèíû v2 ñìåæíûìè ÿâëÿþòñÿ âåðøè-
íû v1 è v3 (ðèñ. 1.4).  ÷àñòíîñòè, âåðøèíà v ñìåæíà ñàìà ñ ñîáîé, åñëè
ñóùåñòâóåò ïåòëÿ, èíöèäåíòíàÿ v, íàïðèìåð âåðøèíà v3 ñìåæíà ñàìà ñ
ñîáîé (ðèñ. 1. 4), â ïðîòèâíîì ñëó÷àå v íå ìîæåò áûòü ñìåæíîé ñàìà ñ
ñîáîé.
   Ñìåæíûìè ðåáðàìè íàçûâàþòñÿ òàêèå, êîòîðûå èìåþò, ïî êðàéíåé
ìåðå, îäíó îáùóþ ãðàíè÷íóþ òî÷êó. Íàïðèìåð, íà ðèñ. 1.4 ñìåæíûìè
ÿâëÿþòñÿ ðåáðà u 1, u 2, u 3 ñ îáùåé âåðøèíîé v2. Ñìåæíûìè ìîæíî
ñ÷èòàòü òàêæå ïàðàëëåëüíûå ðåáðà ( u 1 è u 2) è ïåòëè ( u 4 è u 5).
   Çàìåòèì, ÷òî ñìåæíîñòü ÿâëÿåòñÿ îòíîøåíèåì ìåæäó äâóìÿ ïîäîá-
íûìè ýëåìåíòàìè (ìåæäó âåðøèíàìè èëè ðåáðàìè), òîãäà êàê èíöèäåí-
òíîñòü åñòü îòíîøåíèå ìåæäó ðàçíîðîäíûìè ýëåìåíòàìè (âåðøèíàìè è
ðåáðàìè).
12


                         1.3.3. Ñòåïåíü âåðøèíû
   Ñòåïåíüþ âåðøèíû δ(v) íàçûâàåòñÿ ÷èñëî êîíöîâ ðåáåð, èíöèäåíò-
íûõ âåðøèíå v (ò. å. ïåòëÿ ó÷èòûâàåòñÿ äâàæäû). Íàïðèìåð, δ(v3)=5
(ðèñ. 1.4).
   Èçîëèðîâàííîé âåðøèíîé íàçûâàåòñÿ òà, äëÿ êîòîðîé δ(v)=0, íàïðè-
ìåð δ(v4)=0 (ðèñ. 1.4).
   Âûðîæäåííûì íàçûâàåòñÿ ãðàô, ó êîòîðîãî âñå âåðøèíû èçîëèðî-
âàíû.
   Ïóñòü äàíî |V| – ÷èñëî âåðøèí, à | U | – ÷èñëî ðåáåð êîíå÷íîãî ãðàôà
G=(V, U ). Ïîÿâëåíèå êàæäîãî íîâîãî ðåáðà äîáàâëÿåò ïî åäèíèöå ê
ñòåïåíÿì äâóõ âåðøèí (èëè â ñëó÷àå ïåòëè äîáàâëÿåò äâà ê ñòåïåíè

îäíîé âåðøèíû), ïîýòîìó ñïðàâåäëèâî âûðàæåíèå          ∑ δ(v) = 2| U |, ò. å.
                                                       v∈V
ýòî ÷åòíîå çíà÷åíèå.
   Åñëè V0 è V1 – ìíîæåñòâà âåðøèí, èìåþùèõ ÷åòíûå è íå÷åòíûå
ñòåïåíè ñîîòâåòñòâåííî, òî çíà÷åíèå      ∑ δ(v) ÷åòíî, òàê êàê ýòî êîíå÷-
                                         v∈V0
íàÿ ñóììà ÷åòíûõ ÷èñåë. Îòñþäà ñëåäóåò, ÷òî çíà÷åíèå

                    ∑ δ( v ) – ∑ δ ( v ) = ∑ δ ( v )
                   v∈V          v∈V0       v∈V1

òàêæå îáÿçàòåëüíî ÷åòíî, ÷òî äîêàçûâàåò ñëåäóþùåå óòâåðæäåíèå: â
êîíå÷íîì ãðàôå ÷èñëî âåðøèí íå÷åòíîé ñòåïåíè ÷åòíî. Íàïðèìåð, äëÿ
ãðàôà ðèñ.1.4 èìååì δ(v 1 )=2, δ(v 2 )=3, δ(v 3 )=5, δ(v 4 )=0, îòñþäà
δ(v1)+δ(v4)=2, δ(v2)+δ(v4)=8.

            1.3.4. Ðàçäåëåíèå íåîðèåíòèðîâàííîãî ãðàôà
                          íà ñîñòàâëÿþùèå
   Ðàññìîòðèì ïîíÿòèÿ, èñïîëüçóåìûå äëÿ âûäåëåíèÿ âàæíåéøèõ ÷àñ-
òåé ãðàôà. Ïóñòü çàäàí ãðàô G=(V, U ) (ðèñ.1.4).
   Ñóãðàôîì ãðàôà G íàçûâàåòñÿ ãðàô G'=(V, U '), ãäå U '⊂ U , ò. å.
ñóãðàô ïîëó÷àåòñÿ èç èñõîäíîãî ãðàôà óäàëåíèåì íåêîòîðîãî ÷èñëà ðå-
áåð (ñ ñîõðàíåíèåì âåðøèí). Íàïðèìåð, íà ðèñ. 1.5,à ïîêàçàí ñóãðàô
ãðàôà (ðèñ. 1.4) áåç êðàòíûõ ðåáåð è ïåòåëü.

                                                                          13


 à          u1                 á                              â
                                             u1                           u1
      v          v                  v                 v            v        v
                                             u2

                  u3                                                           u3

                   v!                v"
     v"                                                                        v!
                  u4

                            Ðèñ. 1. 5. Ïðèìåðû äåëåíèÿ ãðàôà:
                      à – ñóãðàô; á – ïîäãðàô; ⠖ ÷àñòè÷íûé ãðàô

    Ïîäãðàôîì ãðàôà G íàçûâàåòñÿ ãðàô G'=(V', U '), ãäå V'⊂V,
 U '= U ∩(V'&V'), ò. å. ïîäãðàô ïîëó÷àåòñÿ èç èñõîäíîãî ãðàôà óäàëåíè-
åì íåêîòîðîãî ÷èñëà âåðøèí âìåñòå ñî âñåìè ðåáðàìè, èíöèäåíòíûìè
óäàëåííîé âåðøèíå. Íàïðèìåð, íà ðèñ. 1.5,á ïîêàçàí ïîäãðàô ãðàôà
(ðèñ. 1.4) ïîñëå óäàëåíèÿ âåðøèíû v3 è èíöèäåíòíûõ åé ðåáåð è ïåòåëü
( u 3, u 4, u 5).
    ×àñòüþ (÷àñòè÷íûì ãðàôîì) ãðàôà G íàçûâàåòñÿ ãðàô G'=(V', U '),
ãäå V'⊂V, U '⊂ U , ò. å. ÷àñòü ãðàôà ïîëó÷àåòñÿ èç èñõîäíîãî ãðàôà ïðè-
ìåíåíèåì îáåèõ îïèñàííûõ îïåðàöèé. Íàïðèìåð, íà ðèñ. 1.5,â ïîêàçàíà
÷àñòü ãðàôà (ðèñ. 1.4) áåç êðàòíûõ ðåáåð è ïåòåëü ( u 2, u 4, u 5), áåç èçî-
ëèðîâàííîé âåðøèíû v4.
    Èñõîäíûé ãðàô G íàçûâàåòñÿ íàäãðàôîì äëÿ âñåõ åãî ÷àñòåé.
           1.3.5. Äèíàìè÷åñêèå ñâîéñòâà íåîðèåíòèðîâàííîãî ãðàôà
   Äî ñèõ ïîð ìû ðàññìàòðèâàëè ñòàòè÷åñêèå ñòðóêòóðíûå ñâîéñòâà
ãðàôà è îòðàæàþùèå èõ ïîíÿòèÿ. Îäíàêî ãðàô îáëàäàåò è äèíàìè÷åñ-
êèìè ñâîéñòâàìè, êîòîðûå ïîçâîëÿþò ïåðåìåùàòüñÿ ïî ñìåæíûì ðåá-
ðàì îò îäíîé âåðøèíû ê äðóãîé. Äëÿ èçó÷åíèÿ ýòèõ ñâîéñòâ, êîòîðûå
èãðàþò ôóíäàìåíòàëüíóþ ðîëü â òåîðèè ãðàôîâ, ââåäåì â ðàññìîòðå-
íèå ñîîòâåòñòâóþùèå ïîíÿòèÿ.
   Ìàðøðóòîì íàçûâàåòñÿ êîíå÷íàÿ ïîñëåäîâàòåëüíîñòü n ðåáåð ãðàôà u 1,
u 2, ... , u n (íå îáÿçàòåëüíî ðàçëè÷íûõ), åñëè ñóùåñòâóåò ïîñëåäîâàòåëü-
íîñòü v0, v1, ... , vn èç n+1 (íå îáÿçàòåëüíî ðàçëè÷íûõ) âåðøèí òàêèõ, ÷òî
                         u i~[vi–1, vi], äëÿ i=1, 2, ... , n.

14


    Äëèíîé ìàðøðóòà (n) íàçûâàåòñÿ ÷èñëî ðåáåð, êîòîðûå îí ñîäåðæèò.
    Ãîâîðÿò, ÷òî ìàðøðóò çàìêíóò, åñëè v0=vn, è íå çàìêíóò, åñëè v0≠vn.
 ïîñëåäíåì ñëó÷àå ìîæíî ñêàçàòü, ÷òî ìàðøðóò ñîåäèíÿåò âåðøè-
íû v0 è vn. Çàìåòèì, ÷òî îäíî ðåáðî ìîæíî ðàññìàòðèâàòü êàê ìàðø-
ðóò äëèíû 1.
    Äëÿ ãðàôà íà ðèñ. 1.6 ïîñëåäîâà-
                                                u1     v      u2
òåëüíîñòü ðåáåð u 1, u 5, u 2, u 3, u 4, v                              v!
u 6 îáðàçóåò íåçàìêíóòûé ìàðøðóò              u6                u4        u3
äëèíû 6, ñîåäèíÿþùèé âåðøèíû v1                        u5
è v5. Åìó ñîîòâåòñòâóåò ïîñëåäîâà-
òåëüíîñòü âåðøèí v1, v2, v2, v3, v4, v#                                   v"
v2, v5. Åñëè çàìåíèòü â ìàðøðóòå             Ðèñ. 1. 6. Ïðèìåð ãðàôà
ðåáðî u 6 íà u 1, òî ïîëó÷èì ïðèìåð
çàìêíóòîãî ìàðøðóòà ñ âåðøèíàìè
v1, v2, v2, v3, v4, v2, v1.
    Öåïüþ íàçûâàåòñÿ íåçàìêíóòûé ìàðøðóò, åñëè âñå åãî ðåáðà ðàçëè÷-
íû. Íàïðèìåð, äëÿ ãðàôà íà ðèñ.1.6 ìîæíî âûäåëèòü ìíîæåñòâî ðåáåð
u 1, u 5, u 4, u 3, u 2, îáðàçóþùèõ öåïü ñ ïîñëåäîâàòåëüíîñòüþ âåðøèí
v1, v2, v2, v4, v3, v2.
    Öèêëîì íàçûâàåòñÿ öåïü, êîòîðàÿ íà÷èíàåòñÿ è çàêàí÷èâàåòñÿ â îä-
íîé è òîé æå âåðøèíå (v0=vn). Íàïðèìåð, äëÿ ãðàôà ðèñ.1.6 öèêë îáðà-
çóåò ïîñëåäîâàòåëüíîñòü ðåáåð u 2, u 3, u 4, u 5 ñ ïîñëåäîâàòåëüíîñòüþ
âåðøèí v2, v3, v4, v2, v2.
    Ïðîñòîé öåïüþ íàçûâàåòñÿ öåïü, â êîòîðîé âñå n+1 âåðøèí v0, v1, ... , vn
ðàçëè÷íû (î÷åâèäíî, ÷òî â ýòîì ñëó÷àå ðåáðà îáÿçàòåëüíî ðàçëè÷íû).
Íàïðèìåð, äëÿ ãðàôà íà ðèñ.1.6 ïðîñòóþ öåïü ñîñòàâëÿþò ðåáðà u 6, u 2, u 3
ñ âåðøèíàìè v5, v2, v3, v4.
    Ïðîñòûì öèêëîì íàçûâàåòñÿ öèêë, åñëè v0= vn, íî âñå îñòàëüíûå
âåðøèíû ðàçëè÷íû. Íàïðèìåð, äëÿ ãðàôà ïðîñòîé öèêë îáðàçóþò ðåáðà
u 2, u 3, u 4 ñ ïîñëåäîâàòåëüíîñòüþ âåðøèí v2, v3, v4, v2.

             1.3.6. Ñâÿçíîñòü íåîðèåíòèðîâàííîãî ãðàôà
   Ãðàô G=(V, U ) íàçûâàåòñÿ ñâÿçíûì, åñëè äëÿ âñåõ vi è vj∈V (vi≠vj)
âñåãäà ñóùåñòâóåò öåïü èç vi â vj, ò. å. åñëè êàæäàÿ ïàðà ðàçëè÷íûõ âåð-
øèí ìîæåò áûòü ñîåäèíåíà, ïî êðàéíåé ìåðå, îäíîé öåïüþ. Â ïðîòèâ-
íîì ñëó÷àå ãðàô íàçûâàåòñÿ íåñâÿçíûì. Íàïðèìåð, ãðàô ðèñ.1.6 ÿâëÿåò-
ñÿ ñâÿçíûì, à ãðàôû ðèñ. 1.4 è 1.7 – íåñâÿçíûìè.
                                                                         15


               v      u1     v             v$        u7   v%

                      u2
               u4                  u5            u6
                                                      u8

               v!      u3     v"            v#

                    Ðèñ. 1.7. Ïðèìåð íåñâÿçíîãî ãðàôà
   Äëÿ âåðøèíû vi îáîçíà÷èì ÷åðåç Ñ(vi) ñîâîêóïíîñòü âåðøèí ãðà-
ôà, êîòîðûå ìîæíî ñîåäèíèòü öåïüþ ñ vi. Êîìïîíåíòîé ñâÿçíîñòè
G(vi) íàçûâàåòñÿ ïîäãðàô ãðàôà G, ïîðîæäåííûé Ñ(vi). Íàïðèìåð,
ãðàô G=(V, U ) íà ðèñ. 1.7 èìååò äâå êîìïîíåíòû ñâÿçíîñòè ñ ïîäìíî-
æåñòâàìè âåðøèí V1={v1, v2, v3, v4}, V2={v5, v6, v7}.
   Ïóñòü G1, G2,... – êîìïîíåíòû ñâÿçíîñòè, ïîðîæäåííûå ïîäìíîæå-
ñòâàìè âåðøèí V1, V2,... . Òîãäà
   1. (∀i ∀j) Vi≠Vj, ò. å. íåò îäèíàêîâûõ ïîäìíîæåñòâ âåðøèí.
   2. (∀i ∀j) Vi≠Vj ⇒ Vi ∩Vj=∅, ò. å. ïîäìíîæåñòâà âåðøèí íå ñîäåðæàò
îáùèõ âåðøèí.
     3. ∪ Vi = V , ò. å. îáúåäèíåíèå ïîäìíîæåñòâ âåðøèí ñîñòàâëÿåò ìíî-
        i
æåñòâî âåðøèí ãðàôà, à òàêæå ∪ Ñ(vi)=V.
                                   vi∈V .
   Íà îñíîâå ïîíÿòèÿ êîìïîíåíò ñâÿçíîñòè ìîæíî äàòü äðóãîå îïðåäå-
ëåíèå ñâÿçíîñòè ãðàôà:
     Ãðàô G=(V, U ) ñâÿçåí òîãäà è òîëüêî òîãäà, êîãäà ìíîæåñòâî åãî
     âåðøèí íåëüçÿ ðàçáèòü íà äâà íåïóñòûõ ïîäìíîæåñòâà V1 è V2 òàê,
     ÷òî îáå ãðàíè÷íûå òî÷êè êàæäîãî ðåáðà íàõîäÿòñÿ â îäíîì è òîì æå
     ïîäìíîæåñòâå.
    Ïóñòü G=(V, U ) – ïðîèçâîëüíûé ãðàô. Çàäàäèì áèíàðíîå îòíî-
øåíèå ρ ìåæäó ïàðàìè âåðøèí ñëåäóþùèì îáðàçîì: v1 ρ v2 òîãäà è
òîëüêî òîãäà, êîãäà v1 = v2 èëè êîãäà ñóùåñòâóåò öåïü, ñîåäèíÿþùàÿ
v1 ñ v2. Îòíîøåíèå ρ ðåôëåêñèâíî (v ρ v äëÿ ëþáîãî v), ñèììåòðè÷íî
(èç v1 ρ v2 ñëåäóåò v2 ρ v1) è òðàíçèòèâíî (èç v1 ρ v2 è v2 ρ v3 ñëåäóåò v1
ρ v3). Òàêèì îáðàçîì, ρ åñòü îòíîøåíèå ýêâèâàëåíòíîñòè. Îíî ðàç-
áèâàåò ìíîæåñòâî V åäèíñòâåííûì îáðàçîì íà êëàññû ýêâèâàëåíò-
íîñòè âçàèìíî ñâÿçíûõ âåðøèí. Äëÿ ãðàôà íà ðèñ. 1.7 òàêèìè êëàñ-
16


ñàìè ýêâèâàëåíòíîñòè ÿâëÿþòñÿ V1={v1, v2, v3, v4} è V2={v5, v6, v7}.
Êàæäûé êëàññ ýêâèâàëåíòíîñòè âåðøèí âìåñòå ñ ðåáðàìè èç U , èí-
öèäåíòíûìè ýòèì âåðøèíàì, îáðàçóåò ñâÿçíûé ïîäãðàô, íàçûâàå-
ìûé ïðîñòî êîìïîíåíòîé ñâÿçíîñòè ãðàôà G. Êîìïîíåíòà Gi ãðàôà G
ÿâëÿåòñÿ ìàêñèìàëüíî ñâÿçíûì ïîäãðàôîì â òîì ñìûñëå, ÷òî ãðàô Gi
íå èìååò ñâÿçíîãî ñîáñòâåííîãî íàäãðàôà. Îòñþäà ñëåäóåò åùå îäíî
îïðåäåëåíèå êîìïîíåíòû ñâÿçíîñòè:
      Ïîäãðàô G' ãðàôà G íàçûâàåòñÿ êîìïîíåíòîé ñâÿçíîñòè ãðàôà G, åñëè
      1) G' ñâÿçåí, 2) G' îáëàäàåò ñâîéñòâîì ìàêñèìàëüíîñòè, ò. å. åñëè G'' –
      íåêîòîðûé äðóãîé ñâÿçíûé ïîäãðàô G è G'⊂ G'', òî ãðàôû G' è G''
      ñîâïàäàþò.
                        1.3.7. Äåðåâüÿ è ëåñà â ãðàôå
   Äåðåâîì íàçûâàåòñÿ ñâÿçíûé ãðàô áåç öèêëîâ. Ãðàô ÿâëÿåòñÿ äåðå-
âîì òîãäà è òîëüêî òîãäà, êîãäà êàæäàÿ ïàðà ðàçëè÷íûõ âåðøèí ñîåäè-
íÿåòñÿ îäíîé è òîëüêî îäíîé öåïüþ. Ñâÿçíîñòü äåðåâà îçíà÷àåò ñóùå-
ñòâîâàíèå, ïî êðàéíåé ìåðå, îäíîé òàêîé öåïè, à èç îòñóòñòâèÿ öèêëîâ
ñëåäóåò ñóùåñòâîâàíèå åäèíñòâåííîé òàêîé öåïè.
   Ëåñîì èç K äåðåâüåâ íàçûâàåòñÿ ãðàô áåç öèêëîâ, ñîñòîÿùèé èç K
êîìïîíåíò.
   Èç ãðàôà íà ðèñ.1.7 ïóòåì óäàëåíèÿ ðåáåð, çàìûêàþùèõ öèêëû,
ìîæíî ïîëó÷èòü ðàçëè÷íûå âàðèàíòû äåðåâüåâ, íàïðèìåð òàêèå, êàê
íà ðèñ.1.8.
a                                         á
 v       u1   v            v$   u7   v%        v   u1        v         v$        v%

 u4                    u6                                           u6
                                                          u2                  u8

v!        u3    v"          v#                  v!   u3        v"        v#

        Ðèñ. 1.8. Ïðèìåðû íåñâÿçíîãî ãðàôà â âèäå ëåñà èç äâóõ äåðåâüåâ

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


îí íå ñîäåðæèò ïîäãðàôà, êîòîðûé ñîñòîèò èç âñåõ åãî âåðøèí è ÿâëÿåòñÿ
ñâÿçíûì.
   Åñëè äåðåâî D ÿâëÿåòñÿ ïîäãðàôîì ãðàôà G, òî ðåáðà G, êîòîðûå ïðè-
íàäëåæàò äåðåâó D, íàçûâàþòñÿ âåòâÿìè äåðåâà D, à ðåáðà, íå ïðèíàäëåæà-
ùèå äåðåâó D, – õîðäàìè îòíîñèòåëüíî äåðåâà D. Åñëè âñå âåðøèíû G
ïðèíàäëåæàò äåðåâó D, òî ãîâîðÿò, ÷òî äåðåâî ïîêðûâàåò ãðàô G. Ïðè ýòîì
òîëüêî ñâÿçíûå ãðàôû èìåþò ïîêðûâàþùèå äåðåâüÿ è òîëüêî äåðåâüÿ èìå-
þò åäèíñòâåííûå ïîêðûâàþùèå äåðåâüÿ.
   Ðèñ. 1.8 èëëþñòðèðóåò îáùåå ñâîéñòâî äåðåâüåâ: êàæäîå äåðåâî ñ n âåð-
øèíàìè èìååò â òî÷íîñòè n – 1 ðåáðî. Ïðèìåíèâ ýòîò ðåçóëüòàò ê êàæäîìó
äåðåâó ëåñà, ìîæíî ñêàçàòü: ëåñ èç K äåðåâüåâ, ñîäåðæàùèé n âåðøèí, èìå-
åò â òî÷íîñòè n – k ðåáåð.
        1.3.8. Ñïåöèàëüíûå êëàññû íåîðèåíòèðîâàííûõ ãðàôîâ
   Êëàññèôèêàöèÿ ãðàôîâ çàâèñèò îò ñòðóêòóðíûõ ïðèçíàêîâ, êîòîðûå èñ-
ïîëüçóþòñÿ â êà÷åñòâå îñíîâû äëÿ êëàññèôèêàöèè, íàïðèìåð, ãðàôû ìîæ-
íî ðàçáèòü íà ñâÿçíûå è íåñâÿçíûå. Âîçìîæíû è äðóãèå ðàçíîâèäíîñòè
ãðàôîâ.
   Îáûêíîâåííûì íàçûâàåòñÿ ãðàô, êîòîðûé íå ñîäåðæèò ïåòåëü è ïàðàë-
ëåëüíûõ ðåáåð. Âî ìíîãèõ ñëó÷àÿõ äîñòàòî÷íî ðàññìàòðèâàòü òîëüêî îáûê-
íîâåííûå ãðàôû. Íàïðèìåð, ñâÿçíîñòü ãðàôà (èëè îòñóòñòâèå åå) íå ìåíÿ-
åòñÿ, åñëè óäàëèòü âñå ïåòëè è ïàðàëëåëüíûå ðåáðà. Îáûêíîâåííûé ãðàô
ìîæíî òàêæå îïðåäåëèòü êàê ãðàô, íå èìåþùèé öèêëîâ, êîòîðûå ñîäåðæàò
ìåíåå òðåõ ðåáåð, òàê êàê öèêë èç äâóõ ðåáåð îáðàçóåòñÿ ïàðàëëåëüíûìè
ðåáðàìè.
   Ïîëíûì íàçûâàåòñÿ ãðàô, â êîòîðîì ëþáûå äâå ðàçëè÷íûå âåðøèíû
ÿâëÿþòñÿ ñìåæíûìè, ò. å. ñîåäèíÿþòñÿ ðåáðîì. Îáû÷íî ýòîò òåðìèí ïðè-
ìåíÿåòñÿ ê îáûêíîâåííûì ãðàôàì, äëÿ êîòîðûõ ñóùåñòâóåò òîëüêî îäèí
ïîëíûé ãðàô ñ ôèêñèðîâàííûì ÷èñëîì âåðøèí. Ñëåäîâàòåëüíî, âûðàæå-
íèå “ïîëíûé ãðàô ñ k âåðøèíàìè” îäíîçíà÷íî îïðåäåëÿåò ãðàô. Íà ðèñ.
1.9 èçîáðàæåí ïîëíûé ãðàô ñ ÷åòûðüìÿ âåðøèíàìè.
   Åñëè ñòåïåíü âåðøèíû δ(v)=k (÷èñëî ðåáåð, èíöèäåíòíûõ âåðøèíå,
âêëþ÷àÿ ïàðàëëåëüíûå ðåáðà è ïåòëè) äëÿ âñåõ âåðøèí ãðàôà, òî ãðàô íà-
çûâàåòñÿ îäíîðîäíûì ãðàôîì ñòåïåíè k èëè ïðîñòî k-îäíîðîäíûì. Çàìå-
òèì, ÷òî îáûêíîâåííûé ïîëíûé ãðàô, èìåþùèé k âåðøèí, ÿâëÿåòñÿ (k–1)-
îäíîðîäíûì. Íàïðèìåð, ãðàô íà ðèñ. 1.9 ÿâëÿåòñÿ 3-îäíîðîäíûì.
   Ãðàô íàçûâàåòñÿ k-ñâÿçíûì, åñëè ëþáàÿ ïàðà ðàçëè÷íûõ âåðøèí v è
w ñîåäèíåíà, ïî êðàéíåé ìåðå, k öåïÿìè, êîòîðûå íå èìåþò îáùèõ âåð-
18


   v                         v        V                       V




  v!                     v"
      Ðèñ. 1.9. Ïðèìåð
                                       Ðèñ. 1.10. Äâóäîëüíûé ãðàô
îáûêíîâåííîãî ïîëíîãî ãðàôà

øèí, èñêëþ÷àÿ, êîíå÷íî, v è w. Íàïðèìåð, ëþáîé ïðîñòîé öèêë (èñêëþ-
÷àÿ ïåòëè) îáðàçóþò 2-ñâÿçíûé ãðàô. Íà ðèñ.1.9 èçîáðàæåí 4-ñâÿçíûé
ãðàô. Ïðè k=1 ýòî ïîíÿòèå ñîâïàäàåò ñ ïîíÿòèåì îáû÷íîé ñâÿçíîñòè.
Íàïðèìåð, äåðåâî – ýòî îäíîñâÿçíûé ãðàô.
   Äâóäîëüíûì íàçûâàåòñÿ ãðàô, â êîòîðîì âåðøèíû ìîãóò áûòü ðàçáè-
òû íà äâà íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâà V1 è V2 òàê, ÷òî êàæäîå
ðåáðî èìååò îäíó ãðàíè÷íóþ òî÷êó â V1, à äðóãóþ â V2.  îáùåì ñëó-
÷àå ãðàô íàçûâàåòñÿ k-äîëüíûì, åñëè ìíîæåñòâî åãî âåðøèí ìîæíî
ðàçáèòü íà k íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâ {V1, V2, …, Vk} òàê, ÷òî
íå ñóùåñòâóåò ðåáåð, ñîåäèíÿþùèõ âåðøèíû îäíîãî è òîãî æå ïîäìíî-
æåñòâà. Äâóäîëüíûé ãðàô èçîáðàæàþò, ðàçìåùàÿ ìíîæåñòâà âåðøèí
V1 è V2 â ðàçíûõ ñòîëáöàõ (èëè ñòðîêàõ), êàê ïîêàçàíî íà ðèñ. 1.10.
              1.3.9. Ìàòðè÷íîå ïðåäñòàâëåíèå ãðàôîâ
                        Ìàòðèöà èíöèäåíöèé
   Äëÿ óäîáñòâà îáðàáîòêè ãðàôîâ ñ èñïîëüçîâàíèåì ÝÂÌ ëó÷øå âñå-
ãî ïîäõîäèò ìàòðè÷íàÿ ôîðìà ïðåäñòàâëåíèÿ ãðàôà. Ïóñòü G – ãðàô,
èìåþùèé n âåðøèí è m ðåáåð. Ãðàô G ìîæíî îïèñàòü ìàòðèöåé èí-
öèäåíöèé A ðàçìåðîì n×m, ñòðîêè è ñòîëáöû êîòîðîé ñîîòâåòñòâóþò
âåðøèíàì è ðåáðàì ãðàôà. Ýëåìåíò ìàòðèöû aij ïðèíèìàåò çíà÷åíèå
1 èëè 0 â çàâèñèìîñòè îò òîãî, èíöèäåíòíî j-å ðåáðî i-é âåðøèíå
èëè íåò. Äëÿ ïåòëè âñå ýëåìåíòû ñòîëáöà ñ÷èòàþòñÿ ðàâíûìè 0. Ìàò-
ðèöû, ñîäåðæàùèå òîëüêî ýëåìåíòû 1 èëè 0, íàçûâàþòñÿ áóëåâûìè
ìàòðèöàìè. Íà ðèñ. 1.11 ïðåäñòàâëåí äâóõêîìïîíåíòíûé ãðàô è åãî
ìàòðèöà èíöèäåíöèé.
   Íåêîòîðûå ñâîéñòâà ãðàôà ïðîÿâëÿþòñÿ â åãî ìàòðèöå èíöèäåíöèé. Íà-
ïðèìåð, òàê êàê ðåáðî ãðàôà èíöèäåíòíî òî÷íî äâóì âåðøèíàì, òî êàæäûé
                                                                    19


     à                                v"                   v$

                                                                         u9
                             u4
                                             u5    u6        u7
               v
          u1
                    u2   v    u3       v!               v#           u8       v%


     á)                      u1 u2 u3 u4 u5 u6 u7 u8 u9
                      L1      0    1    0     0   0     0        0   0    0
                      L2      0    1    1     1   0     0        0   0    0
                      L       0    0    1     0   1     0        0   0    0
                A7×9= 3
                      L4      0    0    0     1   1     0        0   0    0
                      L5      0    0    0     0   0     1        1   1    0
                      L6      0    0    0     0   0     1        1   0    1
                      L7      0    0    0     0   0     0        0   1    1

                     Ðèñ.1.11. Ìàòðè÷íîå ïðåäñòàâëåíèå ãðàôà
                         à – ãðàô; á – ìàòðèöà èíöèäåíöèé
ñòîëáåö ìàòðèöû èíöèäåíöèé ñîäåðæèò ðîâíî äâå 1, ïðè÷åì äëÿ êðàòíûõ
ðåáåð â îäèíàêîâûõ ñòðîêàõ. Èñêëþ÷åíèå ñîñòàâëÿåò ïåòëÿ, òàê êàê îíà
äâàæäû èíöèäåíòíà îäíîé è òîé æå âåðøèíå. Ñòîëáåö, ñîîòâåòñòâóþùèé
ïåòëå, ñîñòîèò èç íóëåé. Òàêèì îáðàçîì, ìàòðèöà èíöèäåíöèé íå óêàçûâà-
åò íà ñóùåñòâîâàíèå ïåòåëü äëÿ êîíêðåòíîé âåðøèíû, ïîýòîìó ïðè èçó÷å-
íèè ãðàôîâ ñ ïîìîùüþ òàêèõ ìàòðèö æåëàòåëüíî èñêëþ÷àòü ïåòëè.
   Ïðè ñîîòâåòñòâóþùåé íóìåðàöèè ðåáåð è âåðøèí ãðàôà êàæäàÿ åãî
êîìïîíåíòà ñîîòâåòñòâóåò ïîäìàòðèöå ìàòðèöû èíöèäåíöèé, êîòîðàÿ â ýòîì
ñëó÷àå èìååò áëî÷íóþ ñòðóêòóðó ñëåäóþùåãî âèäà:

                            A1         0     ... 0 
                                                     
                              0        A2     ... 0 
                         A=                            ,
                            ...       ...    ... ... 
                           
                            0                        
                                       0     ... A n 
                                                      
ãäå Ài – ìàòðèöà èíöèäåíöèé, ñîîòâåòñòâóþùàÿ i-é êîìïîíåíòå ãðàôà.
Áëî÷íî-äèàãîíàëüíîå ïðåäñòàâëåíèå ãðàôà ìîæíî ïîëó÷èòü ïîñëåäîâà-
20



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