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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Γ.
P Γ(v
i
)
s
a
s
b
s
c
s
d
s
e
s
f
- -
?
?
6
-
6
*
Γ =
Γ(a) = {b},
Γ(b) = {c, e},
Γ(c) = {a, d},
Γ(d) = {c, f},
Γ(e) = {c, d},
Γ(f) = {a, b, c}.
a.
P ={a}.
1 a 8 a, b 15 a, b, e 22 a, b, e, d
2 a, b 9 a, b, e 16 a, b, e, d 23 a, b, e
3 a, b, c 10 a, b, e, c 17 a, b, e, d, c 24 a, b
4 a, b, c, d 11 a, b, e, c, d 18 a, b, e, d 25 a
5 a, b, c, d, f 12 a, b, e, c, d, f 19 a, b, e, d, f
6 a, b, c, d 13 a, b, e, c, d 20 a, b, e, d, f, c
7 a, b, c 14 a, b, e, c 21 a, b, e, d, f
a. b.
P
{a, b}. b.
(b, c) (b, e),
c e P.
c P,
(a, b, c). Γ(c)={a, d},
P
ïðîäóáëèðîâàâ åãî íà ðèñ. 5.15, è äîïîëíèâ (âìåñòî ìàòðèöû
ñìåæíîñòè) ñïèñêîì ñìåæíîñòè Γ. Äëÿ ïðîñòîòû èçëîæåíèÿ
áóäåì ðàññìàòðèâàòü ìíîæåñòâà P è Γ(vi ) êàê óïîðÿäî÷åí-
                                                          
          as                                                 Γ(a) = {b},
               -bs   -cs                                   
                                                           
                                                           
           6    *                                       Γ(b) = {c, e},
                                                           
                                                           Γ(c) = {a, d},
    G                   6
                                                        Γ=   Γ(d) = {c, f },
                                                          
                                                           
                                                          
                                                           
          
          s      ?
                 s   -?s                                    Γ(e) = {c, d},
          f      e     d                                     Γ(f ) = {a, b, c}.
                 
                                          Ðèñ. 5.15
íûå, à ðåçóëüòàòû ïðåîáðàçîâàíèÿ öåïè ïî øàãàì çàíîñèòü â
òàáëèöó.  êà÷åñòâå èñõîäíîé îïÿòü áåðåì âåðøèíó a. Ïîýòî-
ìó âíà÷àëå ìíîæåñòâî P ={a}. Ôèêñèðóåì ýòî â ïåðâîé ñòðîêå
òàáë. 5.4. Èìååòñÿ åäèíñòâåííàÿ âåðøèíà, íåïîñðåäñòâåííî
                                                                              Òàáëèöà 5.4
  Èòå-                   Èòå-                      Èòå-                       Èòå-
  ðà-       Öåïü         ðà-         Öåïü          ðà-         Öåïü           ðà-      Öåïü
  öèÿ                    öèÿ                       öèÿ                        öèÿ
   1     a                8     a, b               15     a, b, e              22    a, b, e, d
   2     a, b             9     a, b, e            16     a, b, e, d           23    a, b, e
   3     a, b, c         10     a, b, e, c         17     a, b, e, d, c        24    a, b
   4     a, b, c, d      11     a, b, e, c, d      18     a, b, e, d           25    a
   5     a, b, c, d, f   12     a, b, e, c, d, f   19     a, b, e, d, f
   6     a, b, c, d      13     a, b, e, c, d      20     a, b, e, d, f , c
   7     a, b, c         14     a, b, e, c         21     a, b, e, d, f

äîñòóïíàÿ èç a. Ýòî  âåðøèíà b. Ïîýòîìó âêëþ÷àåì åå â
ôîðìèðóåìóþ öåïü. Ñîîòâåòñòâåííî ìíîæåñòâî P ïðèíèìàåò
âèä {a, b}.23 Òåïåðü ïûòàåìñÿ íàðàñòèòü öåïü îò âåðøèíû b.
Èç íåå, êàê ïîêàçûâàåò ñïèñîê ñìåæíîñòè, âûõîäÿò äâå äóãè
(b, c) è (b, e), è îáå ìîãóò áûòü èñïîëüçîâàíû, òàê êàê íè îä-
íà èç âåðøèí c è e íå ïðèíàäëåæèò ìíîæåñòâó P. Âûáèðàåì
ïåðâóþ èç íèõ c è âêëþ÷àåì â P, ïîëó÷àÿ ïîñëå ýòîãî öåïü
(a, b, c). Íà òðåòüåì øàãå èìååì Γ(c)={a, d}, íî ïåðâàÿ â ýòîì
 23 Çäåñü   è äàëåå P îòîæäåñòâëÿåì ñ ôîðìèðóåìîé öåïüþ.



                                            121

Страницы