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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

k(k−1)/2
k/2
(v
1
, . . . , v
2
) e
(v
3
, . . . , v
4
),
v
1
v
3
v
2
v
4
,
s
v
1
s
s s
s
s
v
2
s
v
3
s s
s
s
v
4
@
@
e
H
H
H
H
H
H
e.
G.
G
0
,
G
0
G.
G
0
.
G
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
s
v
6
s
v
7
s
v
8
s
v
9
@
@
@
@
@
@
@
@
G
0
s
v
1
s
v
2
s
v
3
s
v
4
s
v
5
s
v
6
s
v
7
s
v
8
s
v
9
@
@
@
@
@
@
@
@
G,
v
1
, v
3
, v
7
v
9
, C
2
4
=6
     Ïîêàæåì, êàê ìîæíî ðåøèòü ðàññìàòðèâàåìóþ çàäà÷ó. ßñ-
íî, ÷òî â ãðàôå ñóùåñòâóþò k(k−1)/2 êðàò÷àéøèõ ïðîñòûõ
öåïåé, ñâÿçûâàþùèõ âñå ïàðû âåðøèí íå÷åòíîé ñòåïåíè. Âû-
áåðåì èç íèõ k/2 öåïåé, òàêèõ, ÷òî
     à) íèêàêèå äâå íå èìåþò îäèíàêîâûõ êîíå÷íûõ âåðøèí;
     á) ñóììàðíàÿ äëèíà âñåõ ýòèõ öåïåé ìèíèìàëüíà.
     Çàìåòèì, ÷òî âûáðàííûå öåïè íå ìîãóò èìåòü îáùèõ ðåáåð,
êàê íà ðèñ. 5.11, ÷òî ïðîòèâîðå÷èëî áû ïóíêòó á. Äåéñòâè-
òåëüíî, åñëè öåïü (v1 , . . . , v2 ) èìååò îáùåå ðåáðî e ñ öåïüþ
(v3 , . . . , v4 ), òî, óäàëèâ ýòî ðåáðî, ïîëó÷èì äâå öåïè, ñâÿçûâà-
þùèõ v1 ñ v3 è v2 ñ v4 , ñóììàðíàÿ äëèíà êîòîðûõ ìåíüøå,
                                      ÷åì ó äâóõ ïåðâûõ, íà âåëè÷èíó,
   v1 s        s            s
                            H
               @              Hsv2    ðàâíóþ óäâîåííîìó âåñó ðåáðà
                  @s  e s             e. Ïðîäóáëèðóåì ðåáðà âñåõ âû-
   v3 H s                   s         áðàííûõ öåïåé â ãðàôå G. Â ðå-
            Hs          s HHsv4
                        
                                      çóëüòàòå ïîëó÷èì ýéëåðîâ ìóëü-
                Ðèñ. 5.11             òèãðàô G0 , â êîòîðîì íåòðóäíî
                                      íàéòè ýéëåðîâ öèêë. Ýòîò öèêë
è îïðåäåëÿåò èñêîìûé ìàðøðóò, îòëè÷àÿñü îò íåãî òåì, ÷òî
âìåñòî îáõîäà äâóõ ïàðàëëåëüíûõ ðåáåð â ãðàôå G0 äâàæäû
ïðîõîäèò ïî ñîîòâåòñòâóþùåìó ðåáðó â ãðàôå G. Î÷åâèäíî,
÷òî äëèíà ìàðøðóòà ðàâíà ñóììå äëèí ðåáåð G0 .
          vs1 7 vs2 7 vs3                vs1      vs2     vs3
           @4                             @
         6 @      1     9 3                   @
              @                                @
             3 @ s v5 5                         @ s v5
        v4 s               sv6         v4 s               sv6
              2  @ 2                              @
         9 6    3 @        6                         @
                      @ 4@ s                            @
           s     s                       s        s      @s
          v7 4 v8 3 v9                   v7       v8      v9
                 G                                G0
                            Ðèñ. 5.12

   Ðàññìîòðèì ïðèìåð. Ïóñòü òðåáóåòñÿ íàéòè "ìàðøðóò ïî-
÷òàëüîíà" â ãðàôå G, èçîáðàæåííîì íà ðèñ. 5.12 (âåñà ðåáåð
ïðîñòàâëåíû íà ðèñóíêå). Èìåþòñÿ ÷åòûðå âåðøèíû íå÷åòíîé
ñòåïåíè v1 , v3 , v7 è v9 , èç êîòîðûõ ìîæíî ñîñòàâèòü C42 =6


                                 110

Страницы