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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
sv
6
sv
7
s
v
8
s
v
9
s
v
10
s
v
11
s
v
12
?
?
@
@R
@
@I
@
@I
-
s
v
4
s
v
2
s
v
3
s
v
9
s
v
7
s
v
1
s
v
6
s
v
11
s
v
5
s
v
10
s
v
8
s
v
12
+
?
Q
Q
Qs
? ?
B
B
BN
B
B
BN
B
B
BN
s
v
4
s
v
2
s
v
3
s
v
9
s
v
7
s
v
1
s
v
6
s
v
11
s
v
5
s
v
10
s
v
8
s
v
12
@
@I
66
H
H
HY
6
*
@
@I
@
@I
v
2
, v
4
, v
9
.
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
@
@
@R
@
@R
?
6
-
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
@
@R
?
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
@
@
@R
@
@R
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
@
@R
6
-
G
1
G
2
r
v
1
r
v
2
r
v
3
r
v
4
r
v
5
@
@
@
@R
@
@R
?
6
-
r
v
1
r
v
2
r
v
3
r
v
4
r
v
5
rv
6
@
@R
66
-@
@I
@
@I
G
1
v
2
   Îðèåíòèðîâàííûå äåðåâüÿ. Îðèåíòèðîâàííîå äåðå
âî  ýòî ãðàô, â êîòîðîì ïîëóñòåïåíü çàõîäà ó îäíîé âåðøè-
íû, íàçûâàåìîé êîðíåì, ðàâíà íóëþ, à ó îñòàëüíûõ  åäèíèöå.
Íà ðèñ. 3.3,à,á,â èçáðàæåíû òðè îðèåíòèðîâàííûõ äåðåâà.
         vs1      vs2                  vs4                    vs5     vs10
                                     Q
   v3 s      sv4     sv5    v2 s
                                 + v ?
                                      3s
                                           QQ
                                            s sv9         sv1 @ I@sv
                                                                    7
                                              B         6       6
       v6 s    v7 s?                                      sv3     sv2      sv8   sv12
           @
           I       @         v7 ?s v1 ? s v6 s BN sv11   @
                                                          I
   v8 s     @s?v9 @ R sv10      B                B       v@
                                                            4 H
                                                               s      sv6 @
                                                                           I@sv
                                                                YH         * 11
                                                                            
       I
       @@s     -s             s BN s           s BN s             H 6
                                                                       s
         v11      v12        v5 v10            v8 v12                 v9
             a                         á                              â
                                    Ðèñ. 3.3
È õîòÿ ïî êîíôèãóðàöèè îíè èäåíòè÷íû (åñëè íå ó÷èòûâàòü
îðèåíòàöèþ äóã) ñîîòâåòñòâóþùèì èçîáðàæåíèÿì îäíîãî è
òîãî æå äåðåâà íà ðèñ. 3.1,à,á,â, ýòî ñîâåðøåííî ðàçëè÷íûå äå-
ðåâüÿ óæå ïîòîìó, ÷òî ó íèõ ðàçíûå êîðíè: v2 , v4 , v9 . Íåêîòî-
            vs2              vs2               vs2              vs2
             @R
              @               @@
                               R                @R
                                                 @               @@
                                                                  R
      v1 s     sv3 v1 s           sv3 v1 s     sv3 v1 s     sv3
         @
         6                                 @            6
           @                                 @
      v5 s    R
              @
              - s?
                 v4 v5 s           s?v4 v5 s   R sv4 v5 s
                                               @            - sv4
            à            á                   â            ã
                                    Ðèñ. 3.4
ðûå ñâÿçíûå îðãðàôû òàêæå èìååþò îñòîâû. Íà ðèñ. 3.4,à äàí
ïðèìåð òàêîãî ãðàôà è ïîêàçàíû òðè åãî îñòîâà (ðèñ. 3.4,á,â,ã ).
                             vr 2                vr 2
                              @ R
                                @                 @ @
                                                    R
                    v1 r    r v3 v1 r      r v3
                       @
                       6            6I
                                      @
                   G1    @             @rv6 6G2
                           @
                           R
                           @
                           - r?          I
                                         @
                    v5 r       v4 v5 r    -
                                          @r v4

                                    Ðèñ. 3.5
  Ãðàôû, èçîáðàæåííûå íà ðèñ. 3.5, îñòîâà íå èìåþò. Â ãðà-
ôå G1 åñòü äâå âåðøèíû ñ íóëåâîé ïîëóñòåïåíüþ çàõîäà v2


                                         45

Страницы