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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

G
G
1
s
v
1
s
v
2
s
v
3
s
v
4
-
?
6
G
s
v
1
s
v
2
s
v
3
s
v
4
-
?
6
H
H
HY
s
v
5
s
v
6
s
v
7
s
v
8
@
@R
?
@
@I
G
2
s
v
5
s
v
6
s
v
7
s
v
8
@
@R
?
@
@I
G
0
1
s
v
1
s
v
2
s
v
4
-
6
G
00
1
s
v
1
s
v
2
s
v
3
s
v
4
-
?
6
G
0
2
s
v
5
s
v
6
s
v
7
s
v
8
@
@R
@
@I
G
00
2
s
v
5
s
v
6
s
v
8
?
@
@I
G
G
1
, G
0
1
, G
00
1
, G
2
, G
0
2
, G
00
2
,
G
1
G
2
(v
4
, v
1
)
v
1
v
4
,
v
2
v
8
.
   2.2. Êîìïîíåíòû ñâÿçíîñòè
   Äëÿ îðãðàôà îïðåäåëåíû òðè òèïà êîìïîíåíò ñâÿçíîñòè:
ñèëüíàÿ êîìïîíåíòà  ìàêñèìàëüíûé ñèëüíûé ïîäãðàô, îäíî-
ñòîðîííÿÿ êîìïîíåíòà  ìàêñèìàëüíûé îäíîñòîðîííèé ïîä-
ãðàô è ñëàáàÿ êîìïîíåíòà  ìàêñèìàëüíûé ñëàáûé ïîäãðàô.
   Ïîíÿòèå ñèëüíîé êîìïîíåíòû èëëþñòðèðóåò ðèñ. 2.2. Ãðàô
               G1                          G                G2
         vs1 -vs2          vs1 -vs2         vs6            vs6
                                  HH
                                  Y          @
          6                 6         H s @   R sv7 v5 s @ @
                                                             Rsv7
                                      v
                                        @
                                         I
                                         5              @
                                                        I
       G vs          s?    s   ?
                                 s
                                          @?s            @?s
          4          v3    v4   v3          v8             v8
         vs1 -vs2          vs1 -vs2              vs6        vs6
          6                 6                   @ R
                                                   @      s
                                           v5 s     sv7 v5
          s                 s           ?
                                         s    @
                                              I @s         @
                                                           I
                                                           @? s
         v4                v4           v3       v8          v8
               G01               G001               G02      G002
                                         Ðèñ. 2.2
G , êîòîðûé ÿâëÿåòñÿ îäíîñòîðîííå ñâÿçíûì, ñîäåðæèò øåñòü
ñèëüíûõ ïîäãðàôîâ G1 , G01 , G001 , G2 , G02 , G002 , èç êîòîðûõ òîëüêî
äâà G1 è G2 ÿâëÿþòñÿ ñèëüíûìè êîìïîíåíòàìè.
   Àíàëîãè÷íî èëëþñòðèðóåòñÿ ïîíÿòèå îäíîñòîðîííåé êîì-
ïîíåíòû.  ðàññìàòðèâàåìîì ñëó÷àå îíîñòîðîííÿÿ êîìïîíåí-
òà ñîâïàäàåò ñ ñàìèì ãðàôîì. Åñëè æå ñìåíèòü, íàïðèìåð,
îðèåíòàöèþ äóãè (v4 , v1 ) íà ïðîòèâîïîëîæíóþ, òî ïîëó÷èì
ñëàáîñâÿçíûé ãðàô ñ äâóìÿ îäíîñòîðîííèìè êîìïîíåíòàìè,
îäíà èç êîòîðûõ îáðàçîâàíà âåðøèíàìè v1  v4 , à äðóãàÿ  âåð-
øèíàìè v2  v8 . Êàê ïîêàçûâàåò ýòîò ïðèìåð, îäíîñòîðîííèå
êîìïîíåíòû ãðàôà â îòëè÷èå îò ñèëüíûõ ìîãóò èìåòü îáùèå
âåðøèíû.
   Ñëàáàÿ êîìïîíåíòà ýêâèâàëåíòíà êîìïîíåíòå ñâÿçíîñòè.
Ïîäîáíî ñèëüíûì êîìïîíåíòàì ñëàáûå êîìïîíåíòû íå ìîãóò
èìåòü îáùèõ âåðøèí.



                                           32

Страницы