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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

T (n), T
1
T
3
T (n−1), T (n)
T
1
T
3
,
T
2
, s
t,
s t.
T
2
.
V
0
V
1
V
2
V
3
V
4
V
5
G
1
s
v
3
s
v
6
s
v
4
s
v
7
s
v
8
s
v
5
s
v
10
s
v
9
s
v
2
s
v
1
*
H
H
H
Hj
J
J
J
J
J
J^
J
J
J
J
J
J
*
H
H
H
H
H
H
H
Hj
R
-
A
A
A
A
A
A
A
AU
-
6
-
1
@
@
@
@R
R
- -
G
2
s
v
1
s
v
2
s
v
4
s
v
5
s
v
3
s
v
7
s
v
6
s
v
8
s
v
9
-
@
@
@
@R
? ?
-
-
?
?
?
-
?
-
(v
i
, v
j
)
i<j,
G
2
G
1
G
1
èñòîêîâ îçíà÷àåò, ÷òî â íåêîòîðîì ðåàëüíîì òóðíèðå åñòü äâà
àáñîëþòíûõ ïîáåäèòåëÿ. Ïðèñóòñòâèå ñòîêà èëè èñòîêà ñóùå-
ñòâåííî ñîêðàùàåò êîëè÷åñòâî öèêëîâ â ãðàôå, òàê êàê òàêèå
âåðøèíû íå ìîãóò ïðèíàäëåæàòü íè îäíîìó öèêëó. Ïîýòîìó
÷èñëî öèêëîâ â òóðíèðå T (n), èìåþùåì, êàê ãðàôû T1 è T3
íà ðèñ. 1.17, ñòîê èëè èñòîê, ðàâíî ÷èñëó öèêëîâ â òóðíèðå
T (n−1), ïîëó÷àþùåìñÿ ïðè óäàëåíèè èç T (n) ñòîêà (èñòîêà)
è âñåõ èíöèäåíòíûõ åìó äóã. Ïðîäåëàâ ïîäîáíóþ îïåðàöèþ
ñ ãðàôàìè T1 è T3 , óáåæäàåìñÿ, ÷òî "îñòàòîê" èìååò îäèí
öèêë. Íàêîíåö, â òóðíèðå, èìåþùåì, êàê ãðàô T2 , è èñòîê s
è ñòîê t, ÷èñëî öèêëîâ òî æå, ÷òî è â òóðíèðå, ïîëó÷åííîì
ïîñëå óäàëåíèÿ s è t.
     ïðèëîæåíèÿõ ÷àñòî âñòðå÷àþòñÿ àöèêëè÷åñêèå îðãðàôû,
ò. å. îðãðàôû, íå ñîäåðæàøèå öèêëîâ. Îäèí òàêîé ãðàô åñòü
è íà ðèñ. 1.17  ýòî T2 . Áîëåå íàãëÿäíûå ïðèìåðû äàíû íà
ðèñ. 1.18. Ïîíÿòíî, ÷òî ëþáîé ãðàô ýòîãî âèäà äîëæåí èìåòü
          v4
           s      -vs5          G1                G2 v1    v      v
       
        * A
                     @                               s   - s2   - s4
  v3            6
   s
            A          @                             @
   H
   JH                                                   @
               A          @
     J HH
        js A
        *
        
                           @
                           Rs
                           -
                                 1
                                 
                                  -
                                  
                                   Rs
                                   v
                                          R
                                          - sv1       s @
                                                   v5 ?   R?
                                                           s   -?
                                                                sv7
           v
      J 7 A                v9      2                     v3
                                       
   
   sH J           A     
  v6 H J                                            ?
       H J
         ^       A                                 s    -?s    -?s
        j
        HJ
        H s      -AU s                             v6     v8     v9
          v8        v10     V3      V4     V5
  V0      V1       V2
                             Ðèñ. 1.18

ïî êðàéíåé ìåðå îäèí ñòîê è îäèí èñòîê. Åñëè ê òîìó æå
ðàçìåòêà âåðøèí ãðàôà òàêîâà, ÷òî äëÿ ëþáîé äóãè (vi , vj )
ñïðàâåäëèâî ñîîòíîøåíèå i

Страницы