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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

D
(9)
D
(9)
1,3,7,9
,
D
(9)
D
(9)
1,3,7,9
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
D
(9)
=
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
0 5 12 6 4 9 10 7 8
5 0 7 3 1 6 7 4 5
12 7 0 10 8 3 9 5 8
6 3 10 0 2 7 8 5 6
4 1 8 2 0 5 6 3 4
9 6 3 7 5 0 6 2 5
10 7 9 8 6 6 0 4 7
7 4 5 5 3 2 4 0 3
8 5 8 6 4 5 7 3 0
,
v
1
v
3
v
7
v
9
D
(9)
1,3,7,9
=
v
1
v
3
v
7
v
9
0 12 10 8
12 0 9 8
10 9 0 7
8 8 7 0
.
D
(9)
1,3,7,9
v
1
− v
3
v
7
− v
9
v
1
− v
7
v
3
− v
9
v
1
− v
9
v
3
− v
7
v
1
v
9
v
3
v
7
.
(v
1
, v
5
, v
9
)
D
(n)
,
P
(n)
ðàçëè÷íûõ ïàð. Íàéäåì êðàò÷àéøóþ öåïü äëÿ êàæäîé ïàðû.
Ñ ýòîé öåëüþ ñîñòàâèì ìàòðèöó âåñîâ ãðàôà è, èñïîëüçóÿ àë-
ãîðèòì Ôëîéäà, ïîëó÷èì ìàòðèöó D(9) äëèí êðàò÷àéøèõ ïó-
òåé (öåïåé) ìåæäó âñåìè âåðøèíàìè19 . Âûäåëèì èç íåå ïîä-
           (9)
ìàòðèöó D1,3,7,9 , îáðàçîâàííóþ ñòðîêàìè è ñòîëáöàìè ñ íîìå-
ðàìè 1, 3, 7 è 9. Ýòî ìàòðèöà äëèí âñåõ êðàò÷àéøèõ öåïåé,
ñâÿçûâàþùèõ òîëüêî âåðøèíû íå÷åòíîé ñòåïåíè â ðàññìàòðè-
                                      (9)
âàåìîì ãðàôå. Îáå ìàòðèöû D(9) è D1,3,7,9 ïðèâåäåíû íèæå:
                 v1 v2 v3 v4   v5   v6 v7   v8    v9
          
       v1 0         5 12 6     4    9 10    7     8
                                                    
       v2  5       0 7 3      1    6 7     4     5                       v1 v3 v7   v9
       v3 12       7 0 10     8    3 9     5     8                                   
          
       v4  6       3 10 0     2    7 8     5     6
                                                                     v1 0 12 10      8
                                                                      v3 12 0 9      8
D(9) = v5 
           4       1 8 2      0    5 6     3     4 , D
                                                          (9)
                                                          1,3,7,9 =      
                                                                      v7 10 9 0       7
                                                                                        .
       v6  9       6 3 7      5    0 6     2     5                  v9 8 8 7        0
          
       v7 10       7 9 8      6    6 0     4     7
                                                    
        v8       7 4 5 5       3    2 4     0     3
        v9       8 5 8 6       4    5 7     3     0
                                                     (9)
   Òåïåðü, èñïîëüçóÿ ìàòðèöó D1,3,7,9 , ñëåäóåò âûáðàòü ïà-
ðó öåïåé, îòâå÷àþùèõ ïðèâåäåííûì ðàíåå óñëîâèÿì. Èìååòñÿ
âñåãî òðè âàðèàíòà îáðàçîâàíèÿ òàêèõ ïàð öåïåé, ïðåäñòàâ-
ëåííûå â òàáë. 5.3. Ïîýòîìó çàäà÷à ðåøàåòñÿ ïóòåì ïðîñòîãî
ïåðåáîðà.
                                                                      Òàáëèöà 5.3
        Ïàðà                                                             Îáùàÿ
                      Öåïü          Äëèíà         Öåïü     Äëèíà
        öåïåé                                                            äëèíà
             1       v1 − v3         12       v7 − v9         7        12+7=19
             2       v1 − v7         10       v3 − v9         8        10+8=18
             3       v1 − v9         8        v3 − v7         9        8+9=17
   Êàê ñëåäóåò èç òàáëèöû, íàèëó÷øèì ÿâëÿåòñÿ âàðèàíò 3.
Cëåäîâàòåëüíî, äóáëèðîâàíèþ ïîäëåæàò ðåáðà, îáðàçóþùèå
êðàò÷àéøèå öåïè èç v1 â v9 è èç v3 â v7 . Íåïîñðåäñòâåí-
íî ïî ðèñ. 5.12 ëåãêî óñòàíîâèòü, ÷òî ýòî öåïè (v1 , v5 , v9 ) è
 19 Âîáùåì ñëó÷àå, êðîìå D(n) , íåîáõîäèìî âû÷èñëÿòü è ìàòðèöó
âåðøèí-ïðåäøåñòâåííèö P(n) (ñì. ðàçä. 4).


                                            111

Страницы