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

G íàçûâàåòñÿ ãðàô G, èìåþùèé òî æå ìíîæåñòâî âåðøèí, â
êîòîðîì ëþáûå äâå âåðøèíû ñìåæíû, åñëè îíè íå ñìåæíû â
G, è íå ñìåæíû, åñëè îíè ñìåæíû â G. Èíûìè ñëîâàìè, â ãðà-
ôàõ G è G îòíîøåíèÿ ñìåæíîñòè ëþáîé ïàðû âåðøèí ïðî-
òèâîïîëîæíû. Îñîáîå ìåñòî ñðåäè ïðåäñòàâëåííûõ íà ðèñ. 1.7
ãðàôîâ çàíèìàåò G7 . Ýòî òàê íàçûâàåìûé ñàìîäîïîëíèòåëü-
íûé ãðàô, ÿâëÿþùèéñÿ ñâîèì ñîáñòâåííûì äîïîëíåíèåì,
                                            r r        â ÷åì
íåòðóäíî óáåäèòüñÿ, åñëè èçîáðàçèòü åãî êàê @
                                            r r. Äëÿ ñàìîäî-
ïîëíèòåëüíûõ ãðàôîâ ñïðàâåäëèâî ðàâåíñòâî G=G, òîãäà
êàê â îáùåì ñëó÷àå G=G.
   Ðåãóëÿðíûå ãðàôû. Äëÿ ãðàôîâ G1 , G3 , G8 , G11 õàðàê-
òåðíûì ÿâëÿåòñÿ òî, ÷òî â êàæäîì èç íèõ âñå âåðøèíû èìåþò
îäèíàêîâûå ñòåïåíè. Òàêèå ãðàôû íàçûâàþò ðåãóëÿðíûìè èëè
îäíîðîäíûìè. Íà ðèñ. 1.8 ïðèâåäåíû ïðèìåðû ðåãóëÿðíûõ âî-
ñìèâåðøèííûõ ãðàôîâ òðåòüåé, ÷åòâåðòîé è ïÿòîé ñòåïåíåé.

   G1                 G2                G3
    s    sd=3 s   s    s   sd=4 s   s    s   sd=5 s  s
                       @        @        @ @ @
     s   s    s   s      @
                       s @s     s @
                                  @s     s @
                                           @s @@s @ @s


                           Ðèñ. 1.8
   Îòìåòèì, ÷òî ãðàôû òðåòüåé ñòåïåíè íàçûâàþò êóáè÷åñêè-
ìè. Ýòî ãðàôû G11 íà ðèñ. 1.7 è G1 íà ðèñ. 1.8. Î÷åâèäíî,
÷òî ÷èñëî ðåáåð â ðåãóëÿðíîì ãðàôå ñòåïåíè d ðàâíî m= 12 nd .
Èç ýòîãî ñëåäóåò, ÷òî ïðè íå÷åòíîì ÷èñëå âåðøèí ðåãóëÿðíûé
ãðàô ìîæåò èìåòü òîëüêî ÷åòíóþ ñòåïåíü, à ïðè íå÷åòíîé ñòå-
ïåíè òîëüêî ÷åòíîå ÷èñëî âåðøèí. Ïýòîìó ëþáîé êóáè÷åñêèé
ãðàô èìååò ÷åòíîå ÷èñëî âåðøèí.
   Äâóäîëüíûå ãðàôû. Çàâåðøàÿ îáçîð ãðàôîâ, ïðåäñòàâ-
ëåííûõ íà ðèñ. 1.7, îõàðàêòåðèçóåì êëàññ äâóäîëüíûõ ãðàôîâ.
   Ãðàô íàçûâàåòñÿ äâóäîëüíûì, åñëè ñóùåñòâóåò òàêîå ðàç-
áèåíèå ìíîæåñòâà åãî âåðøèí V íà äâà ïîäìíîæåñòâà (äâå
äîëè) V1 è V2 , ÷òî êîíöû ëþáîãî ðåáðà ïðèíàäëåæàò ðàçíûì
ïîäìíîæåñòâàì. Ñðåäè ãðàôîâ íà ðèñ. 1.7 ïîä îïðåäåëåíèå
äâóäîëüíîãî ïîäïàäàþò ãðàôû G1  G4 , G6 è G7 , ïðè÷åì
îäíîçíà÷íîå ðàçáèåíèå ìíîæåñòâà âåðøèí íà äîëè âîçìîæ-

                             15