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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

u
+
−
v u,
u
¢
u
s e
u
e s
E
E
E
E
A
A
A
A
A
A
A
A
A
@
@
@
!
!
!
!
a
a
a
a
e s
3
2
e s
3
2
e s
3
2
H
H
H
H
H
H
A
A
A
A
A
A
H
H
H
H
H
H
H
H
H
H
H
H
A
A
A
A
A
A
H
H
H
H
H
H
k
k k>2
hV, Ei,
V
E
G
1
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
@
@
G
2
s
v
1
±°
²¯
s
v
2
±°
²¯
¹¸
º·
s
v
3
s
v
4
s
v
5
@
@
G
1
G
2
ìåòîê âñåõ âåðøèí ñâèäåòåëüñòâóåò î âîçìîæíîñòè "äâóäîëü-
íîãî ðàçáèåíèÿ" ìíîæåñòâà âåðøèí ãðàôà (ñîáñòâåííî ðàñïðå-
äåëåíèå çíàêîâ è îïðåäåëÿåò ýòî ðàçáèåíèå);
   á) âîçíèêíåò ñèòóàöèÿ, êîãäà íåêòîðàÿ âåðøèíà u îêàæåò-
ñÿ ïîìå÷åííîé çíàêîì " + " ñî ñòîðîíû îäíîé ñîñåäíåé âåðøè-
íû è çíàêîì " − " ñî ñòîðîíû äðóãîé. Ýòî çíà÷èò, ÷òî â ãðàôå
åñòü äâå ïðîñòûå öåïè, ñîåäèíÿþùèå v è u, îäíà èç êîòîðûõ
ñîñòîèò èç ÷åòíîãî ÷èñëà äóã, à äðóãàÿ  èç íå÷åòíîãî, â ñî-
âîêóïíîñòè îáðàçóþùèå öèêë íå÷åòíîé äëèíû. Âìåñòå ñ òåì,
ðàçíûå çíàêè ó âåðøèíû u íå ïîçâîëÿþò âûïîëíèòü "äâó-
äîëüíîå ðàçáèåíèå" ìíîæåñòâà âåðøèí ãðàôà. ¢
                   u                     e
                                         H     s      3 2
                AE                     A HHH A HH   
                EA                      A H  A    H
                E A                    
                                         e A   s AHH3 HH
              s Ee A
                                         H
                                           H
                                               H
                                            AH HAH      2
                                                     
             AAu@ A                         A H
                                             AH
        e!!
         !
               !aa@A
                       a
                       @As
                       a                  As HH
                                         e           A3 HH2

                             Ðèñ. 1.10
   Àíàëîãè÷íî äâóäîëüíûì îïðåäåëÿþòñÿ òðåõ-, ÷åòûðåõ- è,
âîîáùå, k -äîëüíûå ãðàôû. Íà ðèñ. 1.10 äàíû ïðèìåðû òðåõ- è
÷åòûðåõäîëüíîãî ãðàôîâ 3 . Ê ñîæàëåíèþ, ïðîñòûõ êðèòåðèåâ
âûÿâëåíèÿ k -äîëüíîñòè ãðàôà ïðè k>2 íå ñóùåñòâóåò.
   Ìóëüòè- è ïñåâäîãðàôû. Ñîãëàñíî îïðåäåëåíèþ, ñîâî-
êóïíîñòü ðåáåð ãðàôà ÿâëÿåòñÿ ìíîæåñòâîì. Ïîýòîìó ñìåæ-
íûå âåðøèíû ñîåäèíÿåò òîëüêî îäíî ðåáðî. Åñëè äîïóñòèòü
êðàòíûå     (ïàðàëëåëüíûå)                        ²¯G2 ²¯
                                                              º·
                                     G1
ðåáðà, òî ïîëó÷èì ìóëü-        v5 s
òèãðàô. Èíûìè ñëîâàìè,                     sv2     v5 s
                                                  ±°           sv2
                                                              ±°
                                                              ¹¸
ìóëüòèãðàô ýòî ïàðà hV, Ei,         v1 s                v1 s
ãäå V  ìíîæåñòâî âåðøèí,              @                   @
à E  ñåìåéñòâî ðåáåð. Íà-        s      @ s          s      @s
                                 v4       v3         v4       v3
êîíåö, åñëè íàðÿäó ñ êðàò-
íûìè ðàçðåøèòü ðåáðà, ñâÿ-                   Ðèñ. 1.11
çûâàþùèå âåðøèíó ñàìó ñ ñîáîé (ïåòëè), òî ïîëó÷èì ïñåâäî-
ãðàô. Ìóëüòèãðàô G1 è ïñåâäîãðàô G2 ïîêàçàíû íà ðèñ. 1.11.
  3 Âåðøèíû,   îòíîñÿùèåñÿ ê ðàçíûì äîëÿì, èçîáðàæåíû ïî-ðàçíîìó.


                                    17

Страницы