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

     1.3. Âèäû ãðàôîâ
   Îáðàòèìñÿ ê ðèñ. 1.7, çàèìñòâîâàííîìó (ñ íåáîëüøèìè èç-
ìåíåíèÿìè è äîïîëíåíèÿìè) èç êíèãè [1]. Çäåñü ïðåäñòàâëåíû
âñå âîçìîæíûå àáñòðàêòíûå ãðàôû ÷åòâåðòîãî ïîðÿäêà.

 s G1 s       s G2 s   sG3 s    s G5 s    s G8 s   s G10 s   s G11 s
              @        @                    C4               @
 s        s   s @@s    s @
                         @s     s    s    s    s   s    s    s @@s
     O4                                                        K4
                       sG4 s    s G6 s    s G9 s
                                @         @
                       s   s    s @@s     s @@s

                                s G7 s
                                  P4
                                s    s

                               Ðèñ. 1.7

     Íåñâÿçíûå è ñâÿçíûå ãðàôû. Î÷åâèäíî, ÷òî èçîáðà-
æåííûå íà ðèñ. 1.7 ãðàôû ìîæíî ïîäåëèòü íà äâå ãðóïïû
(ðàçãðàíè÷åíû øòðèõîâîé ëèíèåé): íåñâÿçíûå ( G1  G5 ) è
ñâÿçíûå ( G6  G11 ).
   Ãðàô íåñâÿçåí, åñëè ìíîæåñòâî åãî âåðøèí ðàñïàäàåòñÿ íà
äâà (èëè áîëåå) íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâà, òàêèõ, ÷òî
íåò íè îäíîãî ðåáðà, êîíöû êîòîðîãî ïðèíàäëåæàò ðàçíûì
ïîäìíîæåñòâàì.Èíûìè ñëîâàìè, íåñâÿçíûé ãðàô ñîñòîèò èç
äâóõ è áîëåå ÷àñòåé, íå ñîåäèíåííûõ ðåáðàìè. Ýòè ÷àñòè íà-
çûâàþòñÿ êîìïîíåíòàìè ñâÿçíîñòè. Òàê, íà ðèñ. 1.7 ãðàô G1
èìååò ÷åòûðå êîìïîíåíòû, G2  òðè êîìïîíåíòû, G3 , G4 è
G5 äâå, à îñòàëüíûå ãðàôû îäíó êîìïîíåíòó.
   Ñðåäè íåñâÿçíûõ ãðàôîâ, èçîáðàæåííûõ íà ðèñ. 1.7, îñîáîå
ïîëîæåíèå çàíèìàåò G1 , âîîáùå íå èìåþùèé ðåáåð è íàçûâà-
åìûé ïóñòûì. Äëÿ òàêèõ ãðàôîâ ÷àñòî èñïîëüçóåòñÿ îáîçíà-
÷åíèå On , ãäå n  ÷èñëî âåðøèí.
   Ñðåäè ñâÿçíûõ ãðàôîâ G6  G11 òàêæå ìîæíî âûäåëèòü
ãðàô G11 , èìååþùèé ìàêñèìàëüíîå äëÿ ãðàôà ÷åòâåðòîãî ïî-



                                    13