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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

G.
G(V, E
0
)
G
s
v
1
s
v
2
s
v
3
s
v
4
@
@
s
v
1
s
v
2
s
v
3
s
v
4
@
@
s
v
1
s
v
2
s
v
3
s
v
4
s
v
1
s
v
2
s
v
3
s
v
4
@
@
s
v
1
s
v
2
s
v
3
s
v
4
s
v
1
s
v
2
s
v
3
s
v
4
s
v
1
s
v
2
s
v
3
s
v
4
@
@
s
v
1
s
v
2
s
v
3
s
v
4
G(V, E) E\E
0
(n, m)
P
m
k=0
C
k
m
= 2
m
, C
k
m
k
V
0
V
0
.
G.
G
s
v
1
s
v
2
s
v
3
s
v
4
@
@
s
v
1
s
v
2
s
v
3
s
v
4
s
v
1
s
v
2
s
v
1
s
v
3
@
@
s
v
1
s
v
4
s
v
2
s
v
3
s
v
2
s
v
4
s
v
3
s
v
4
s
v
1
s
v
2
s
v
3
@
@
s
v
1
s
v
2
s
v
4
s
v
1
s
v
3
s
v
4
@
@
s
v
2
s
v
3
s
v
4
G(V
0
, E
0
)
G(V, E) V \V
0
P
n
k=1
C
k
n
= 2
n
− 1.
C
k
n
k
G(V
0
, E
0
),
ðèñ. 1.4 ïîêàçàíû âñå îñòîâíûå ïîäãðàôû ãðàôà G. Êàê ñëå-
äóåò èç ðèñ. 1.4, ëþáîé îñòîâíûé ïîäãðàô G(V, E 0 ) ãðàôà
 v1 v2    v1 v2     v1 v2     v1 v2       v1 v2    v1 v2    v1 v2   v1 v2
  s s      s s       s s       s s         s s      s s      s s     s s
G @        @                   @                             @
  s @s     s @s      s s       s @s        s s      s s      s @s    s s
 v4 v3    v4 v3     v4 v3     v4 v3       v4 v3    v4 v3    v4 v3   v4 v3
                                 Ðèñ. 1.4

G(V, E) ïîëó÷àåòñÿ ïîñëå óäàëåíèÿ ïîäìíîæåñòâà E\E 0 ðå-
áåð íàäãðàôà. Êîëè÷åñòâî
                    Pm     îñòîâíûõ ïîäãðàôîâ ïîìå÷åííîãî
(n, m)-ãðàôà ðàâíî         k    m                 k
                      k=0 Cm = 2 , ãäå ñëàãàåìûå Cm îïðå-
äåëÿþò ÷èñëî ðàçëè÷íûõ îñòîâíûõ ïîäãðàôîâ, èìåþùèõ k
ðåáåð êàæäûé.
    Ïîäãðàôû äðóãîãî òèïà ïîëó÷àþòñÿ, åñëè âûáðàòü íåêîòî-
ðîå ïîäìíîæåñòâî V 0 âåðøèí íàäãðàôà è ïðèñîåäèíèòü ê íèì
âñå ðåáðà, îáå êîíå÷íûå âåðøèíû êîòîðûõ ïðèíàäëåæàò V 0 .
Ýòî âåðøèííî-ïîðîæäåííûå ïîäãðàôû. Íà ðèñ. 1.5 èçîáðàæå-
íû âñå ïîäãðàôû ýòîãî òèïà äëÿ ãðàôà G. Ëåãêî óáåäèòüñÿ,
         v1             v2                        v1 v2     v1     v1
          s              s                         s s       s      s
                                                             @
 v1 v2                            s     s                      @s   s
  s s                            v3                             v3 v4
                                       v4
G @           v2        v2            v1 v2       v1 v2    v1           v2
  s @s         s         s             s s         s s      s            s
 v4 v3                                 @                    @
               s    s         s s         @s       s        s @s   s     s
              v3   v4        v4 v3         v3     v4       v4 v3 v4     v3

                                 Ðèñ. 1.5

÷òî ëþáîé âåðøèííî-ïîðîæäåííûé ïîäãðàô G(V 0 , E 0 ) ãðàôà
G(V, E) ìîæíî ïîëó÷èòü ïóòåì óäàëåíèÿ ïîäìíîæåñòâà V \V 0
âåðøèí è âñåõ èíöèäåíòíûõ èì ðåáåð íàäãðàôà. Pn      Êîëè÷åñòâî
âåðøèííî-ïîðîæäåííûõ ïîäãðàôîâ ðàâíî                 k    n
                                                k=1 Cn = 2 − 1.
Ñëàãàåìîå Cnk ýòîé ñóììû óêàçûâàåò ÷èñëî âåðøèííî-ïîðîæ-
äåííûõ ïîäãðàôîâ, êàæäûé èç êîòîðûõ èìååò k âåðøèí.
   Íàêîíåö, ðåáåðíî-ïîðîæäåííûì áóäåì íàçûâàòü ïîäãðàô
G(V 0 , E 0 ), ïîëó÷åííûé íà îñíîâå ïðîèçâîëüíî âûáðàííîãî ïîä-


                                     11

Страницы