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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

l. A
3
a
(3)
bb
=3.
b.
(b, d, c, b) (b, e, c, b) (b, e, a, b).
n−1, A
P
(l)
l
l+1
p
(l)
ij
=
P
q
k=1
v
k
1
v
k
2
. . . v
k
l
, v
k
l
l
v
i
v
j
,
q l+1
v
i
v
j
p
(l)
ij
=0. v
k
1
v
k
2
. . . v
k
l
v
i
v
j
.
n
l
p
(3)
cd
=bea+eab+ecb
v
i
v
j
(c, b, e, a, d) (c, e, a, b, d)
(c, e, c, b, d),
a
(4)
cd
A
4
.
P
(l)
, P
0
,
p
0
ij
v
j
, (v
i
, v
j
),
ñÿ ôðàãìåíòû, ò. å. íåîáõîäèìî ðåøàòü çàäà÷ó ïåðå÷èñëåíèÿ
ìàðøðóòîâ. Ïðåæäå ÷åì ïåðåéòè ê ýòîé çàäà÷å, îòìåòèì äâà
ôàêòà, êàñàþùèõñÿ çàäà÷è ïåðåñ÷åòà:
    1. Îòëè÷íûå îò íóëÿ äèàãîíàëüíûå ýëåìåíòû ìàòðèö óêà-
çûâàþò íà ïðèñóòñòâèå â ãðàôå ñîîòâåòñòâóþùåãî êîëè÷åñòâà
öèêëîâ äëèíû l. Íàïðèìåð, â ìàòðèöå A3 äèàãîíàëüíûé ýëå-
        (3)
ìåíò abb =3. Ýòî çíà÷èò, ÷òî â ãðàôå åñòü òðè öèêëà äëèíû
3, âêëþ÷àþùèå âåðøèíó b. Íåïîñðåäñòâåííî ïî ðèñ. 4.1 íàõî-
äèì: (b, d, c, b) , (b, e, c, b) è (b, e, a, b).
    2. Ïîñêîëüêó äëèíà ïóòè â ãðàôå íå ìîæåò ïðåâûøàòü
n−1, íå èìååò ñìûñëà âîçâîäèòü A â áîëåå âûñîêóþ ñòåïåíü.

   4.3. Ïåðå÷èñëåíèå ìàðøðóòîâ è ïóòåé
    Ìàòðè÷íûé ïîäõîä, èñïîëüçîâàííûé â ïðåäûäóùèõ ðàçäå-
ëàõ, ëåãêî àäàïòèðóåòñÿ ê çàäà÷å î ïåðå÷èñëåíèè ìàðøðóòîâ.
     Ïóñòü P(l)  ìàòðèöà âñåõ ìàðøðóòîâ c l ïðîìåæóòî÷-
íûìè âåðøèíàìè (äëèíû l+1 ), ýëåìåíòû êîòîðîé îïðåäåëÿ-
                (l) P
þòñÿ êàê pij = qk=1 vk1 vk2 . . . vkl , ãäå vkl ýòî l-ÿ ïî ïîðÿäêó
ïðîìåæóòî÷íàÿ âåðøèíà ìàðøðóòà, ñâÿçûâàþùåãî vi è vj , à
q  êîëè÷åñòâî òàêèõ ìàðøðóòîâ. Åñëè ìàðøðóòîâ äëèíû l+1
                             (l)
ìåæäó vi è vj íåò, òî pij =0. Ñëàãàåìûå vk1 vk2 . . . vkl ïðåä-
ñòàâëÿþò ñîáîé "ïðîèçâåäåíèÿ" âåðøèí, ëåæàùèõ íà íåêîòî-
ðîì ìàðøðóòå ìåæäó vi è vj . Èõ ìîæíî ðàññìàòðèâàòü êàê
ðàçìåùåíèÿ áåç ïîâòîðåíèé èëè ñ ïîâòîðåíèÿìè èç n ýëåìåí-
òîâ ïî l â çàâèñèìîñòè îò òîãî, ÿâëÿåòñÿ ìàðøðóò ïóòåì èëè
                                             (3)
íåò. Íàïðèìåð, äëÿ ãðàôà íà ðèñ. 4.1 pcd =bea+eab+ecb è, çíà-
÷èò, èç vi â vj åñòü òðè ìàðøðóòà: (c, b, e, a, d) , (c, e, a, b, d) è
(c, e, c, b, d), äâà èç êîòîðûõ ÿâëÿþòñÿ ïóòÿìè, òàê êàê íå ñî-
äåðæàò ïîâòîðÿþùèõñÿ âåðøèí.  íàëè÷èè óêàçàííûõ ìàðø-
ðóòîâ ëåãêî óáåäèòüñÿ íåïîñðåäñòâåííî ïî ãðàôó, à èõ êîëè-
                                         (4)
÷åñòâî ðàâíî çíà÷åíèþ ýëåìåíòà acd â ìàòðèöå A4 . Êðîìå
P(l) , èñïîëüçóåì âñïîìîãàòåëüíóþ ìàòðèöó P0 , â êîòîðîé ýëå-
ìåíò p0ij ðàâåí vj , åñëè â ãðàôå åñòü äóãà (vi , vj ), è 0, åñëè



                                 73

Страницы