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

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

hV, Γi hV, Γ
−
i
k
T
1
s s
ss
s
6
-@
@
@I
?
-
T
2
s s
t
ss
s
6
-@
@
@I
6
-
T
3
s s
t
ss
6
6
-
@
@
@R
T
4
s s
ss
6
6
@
@
@R
s
t
   Ñâîéñòâà ìàòðèö èíöèäåíòíîñòè îðãðàôà è íåîðãðàôà
ïðàêòè÷åñêè îäèíàêîâû, õîòÿ åñòü è îòëè÷èÿ. Òàê, â ñëó÷àå
îðãðàôà õàðàêòåð çàâèñèìîñòè ñòðîê ìàòðèöû èíöèäåíòíîñòè
ñòðîãî ëèíåéíûé: âåêòîð èíöèäåííîñòè ëþáîé âåðøèíû ðàâåí
ñóììå âåêòîðîâ èíöèäåíòíîñòè îñòàëüíûõ âåðøèí, âçÿòîé c
ïðîòèâîïîëîæíûì çíàêîì.
   Íàðÿäó ñ ìàòðèöàìè äëÿ îïèñàíèÿ îðãðàôîâ èñïîëüçóþòñÿ
è ñïèñêè. Ôàêòè÷åñêè ïàðû hV, Γi , hV, Γ− i è ÿâëÿþòñÿ ñîîò-
âåòñòâåííî ïðÿìûì è èíâåðòèðîâàííûì ñïèñêàìè âåðøèí. Â
ñïèñêå äóã äîëæíà áûòü îòðàæåíà èõ îðèåíòàöèÿ.
   Âèäû îðãðàôîâ. Êàê è ïðîñòûå ãðàôû, îðèåíòèðîâàí-
íûå ìîãóò áûòü ñâÿçíûìè è íåñâÿçíûìè, ïîëíûìè, k -äîëüíû-
ìè, ðåãóëÿðíûìè è ò. ï. Ñóùåñòâóþò îðèåíòèðîâàííûå àíà-
ëîãè öåïåé, öèêëîâ, äåðåâüåâ. Òèïè÷íûì ïðèìåðîì ïîäîáíîé
àíàëîãèè ÿâëÿþòñÿ òàê íàçûâàåìûå òóðíèðû  îðèåíòèðîâàí-
íûå ãðàôû, â êîòîðûõ êàæäàÿ ïàðà âåðøèí ñîåäèíåíà òîëüêî
îäíîé äóãîé. Ëþáîé òóðíèð ïîëó÷àåòñÿ èç ïðîñòîãî ïîëíîãî
ãðàôà, åñëè êàæäîìó åãî ðåáðó äàòü íåêîòîðóþ îðèåíòàöèþ.
Íàçâàíèå ýòîãî âèäà ãðàôîâ îáúÿñíÿåòñÿ òåì, ÷òî îíè ïîçâî-
ëÿþò íàãëÿäíî îòîáðàçèòü ðåçóëüòàòû ëþáîãî ñîðåâíîâàíèÿ,
êîãäà êàæäûé ó÷àñòíèê äîëæåí âñòðåòèòüñÿ ñî âñåìè îñòàëü-
íûìè è çàïðåùåíû íè÷üè, íàïðèìåð, êàê â áîëüøîì òåííèñå
èëè â âîëåéáîëå. Ïðè ýòîì ó÷àñòíèêàì ñîîòâåòñòâóþò âåðøè-
íû, à ðåçóëüòàòàì âñòðå÷  äóãè, íàïðàâëåííûå îò ïîáåäèòåëÿ
ê ïîáåæäåííîìó. Íà ðèñ. 1.17 èçîáðàæåíû âñå íåïîìå÷åí-
íûå                        t          t
           s -s          s -s           s -s    s   s
           I 
           @
           6             I 6
                         @
                         6              @
                                        6 6    @
                                                6 6
             @             @              @       @
           s - @s?       s - @s         s @
                                           Rs   s @
                                                   Rs
       s             s
            T1            T2               T3    T4
                               Ðèñ. 1.17
òóðíèðû ÷åòâåðòîãî ïîðÿäêà. Îïèøåì íåêîòîðûå ñâîéñòâà òóð-
íèðîâ. Â ëþáîì òóðíèðå ìîæåò áûòü íå áîëåå îäíîé âåðøèíû
s ñ íóëåâîé ïîëóñòåïåíüþ çàõîäà è íå áîëåå îäíîé âåðøèíû
t ñ íóëåâîé ïîëóñòåïåíþ èñõîäà, íàçûâàåìûõ ñîîòâåòñòâåííî
èñòîêîì è ñòîêîì. Äåéñòâèòåëüíî, íàëè÷èå, íàïðèìåð, äâóõ


                                   26

Страницы