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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

E
0
V
0
G
G
s
v
1
s
v
2
s
v
3
s
v
4
@
@
s
v
1
s
v
3
s
v
4
@
@
s
v
2
s
v
3
s
v
4
s
v
1
s
v
2
s
v
3
@
@
s
v
3
s
v
4
s
v
2
s
v
3
s
v
1
s
v
3
@
@
G(V
0
, E
0
) G(V, E)
E\E
0
,
P
m
k=1
C
k
m
= 2
m
− 1
(n, m)
r r
rr
@
@
r r
r
@
@
r r
rr
@
@
r r
rr
@
@
r
rr
r r
rr
@
@
ìíîæåñòâà E 0 ðåáåð íàäãðàôà, ïðè÷åì ìíîæåñòâî V 0 âåðøèí
ïîäãðàôà ñîñòàâëÿþò êîíöû òîëüêî ýòèõ ðåáåð. Âñå ðåáåðíî-
ïîðîæäåííûå ïîäãðàôû ãðàôà G èçîáðàæåíû íà ðèñ. 1.6.

    v1 v2    v1            v     v1 v2               v2   v1
     s  s     s            s2     s   s               s    s
   G @        @                   @                        @
     s @s     s @s     s   s        @s      s    s    s      @s
    v4 v3    v4 v3    v4   v3        v3    v4   v3   v3       v3
                                Ðèñ. 1.6

    Î÷åâèäíî, ÷òî ëþáîé ðåáåðíî-ïîðîæäåííûé ïîäãðàô
G(V 0 , E 0 ) ãðàôà G(V, E) ìîæíî ñôîðìèðîâàòü, åñëè â íàä-
ãðàôå ñíà÷àëà óäàëèòü ïîäìíîæåñòâî ðåáåð E\E 0 , à ïîòîì
â ïîëó÷èâøåìñÿ îñòîâíîì ïîäãðàôå   Pm óäàëèòü   âñå èçîëèðîâàí-
íûå âåðøèíû. Âñåãî èìååòñÿ                k
                                     k=1 Cm = 2
                                                m
                                                  − 1 ðåáåðíî-
ïîðîæäåííûõ ïîäãðàôîâ (n, m)-ãðàôà.
 r rÑðàâíèâ ðèñ. 1.5 è ðèñ. 1.6, ëåãêî çàìåòèòü, ÷òî äëÿ ãðàôà
 r r ìíîæåñòâî ðåáåðíî-ïîðîæäåííûõ ÿâëÿåòñÿ ïîäìíîæå-
 @
ñòâîì âåðøèííî-ïîðîæäåííûõ ïîäãðàôîâ, íî ýòî ñêîðåå èñ-
êëþ÷åíèå, ÷åì ïðàâèëî. Áîëåå òèïè÷íûì ÿâëÿåòñÿ ñëó÷àé,
êîãäà ýòè ìíîæåñòâà ïîäãðàôîâ ëèøü ïåðåñåêàþòñÿ. Â ýòîì
ëåãêî óáåäèòüñÿ, ïîñòðîèâ ìíîæåñòâà ðåáåðíî- èr âåðøèííî-
                                                      r r r r r
ïîðîæäåííûõ ïîäãðàôîâ, íàïðèìåð äëÿ ãðàôîâ: @ r, @      r r, @
                                                             r r.
    Îáúåäèíåíèå ìíîæåñòâ îñòîâíûõ, âåðøèííî- è ðåáåðíî-
ïîðîæäåííûõ ïîäãðàôîâ â îáùåì ñëó÷àå íå        r ïîêðûâàåò âñå
ìíîæåñòâî ïîäãðàôîâ ãðàôà. Òàê ãðàô r r , ñîñòîÿùèé èç
îäíîãî ðåáðà
           r r    è èçîëèðîâàííîé âåðøèíû, ÿâëÿÿñü ïîäãðàôîì
ãðàôà @    r r , íå îòíîñèòñÿ íè ê îäíîìó èç óêàçàííûõ òèïîâ.
    Ïðèâåäåííàÿ â äàííîì ðàçäåëå òåðìèíîëîãèÿ â îñíîâíîì
ñîîòâåòñòâóåò ïðèíÿòîé â [1, 8, 12].  äðóãèõ èñòî÷íèêàõ [6, 11]
èñïîëüçóþòñÿ òåðìèíû ÷àñòü ãðàôà, ñóãðàô è ïîäãðàô, ïðè÷åì
÷àñòüþ ãðàôà íàçûâàþò ïîäãðàô, ñóãðàôîì  îñòîâíûé ïîä-
ãðàô, à ïîäãðàôîì  âåðøèííî-ïîðîæäåííûé ïîäãðàô.




                                 12

Страницы