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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Γ(v
i
)
v
i
, Γ
−1
(v
j
)
v
j
.
Γ(v
i
)∩Γ
−1
(v
j
)
v
i
v
j
, |Γ(v
i
)∩Γ
−1
(v
j
)|
i
Γ(v
i
)
j Γ
−1
(v
j
),
|Γ(v
i
)∩Γ
−1
(v
j
)|=
P
n
k=1
a
ik
a
kj
.
a
ik
a
kj
=0
v
i
v
k
v
j
s s s
a
ik
=0 a
kj
=0
v
i
v
k
v
j
s s - s
a
ik
=0
a
kj
=1
v
i
v
k
v
j
s - s s
a
ik
=1 a
kj
=0
a
ik
a
kj
=1
v
i
v
k
v
j
s - s - s
a
ik
=1 a
kj
=1
-
v
i
v
j
v
k
,
a
ik
a
kj
P
n
k=1
a
ik
a
kj
a
ik
a
kj
=1
A
3
l v
i
v
j
a
(l)
ij
A
l
. p
   4.2. Ïåðåñ÷åò ìàðøðóòîâ è ïóòåé
     Ïóñòü Γ(vi )  ìíîæåñòâî âåðøèí, ÿâëÿþùèõñÿ êîíöàìè
äóã, âûõîäÿùèõ èç vi , à Γ−1 (vj )  ìíîæåñòâî âåðøèí, ÿâ-
ëÿþùèõñÿ íà÷àëàìè äóã, âõîäÿùèõ â vj . Òîãäà ïåðåñå÷åíèå
Γ(vi )∩Γ−1 (vj ) ïðåäñòàâëÿåò ñîáîé ìíîæåñòâî ïðîìåæóòî÷íûõ
âåðøèí, ïðèíàäëåæàùèõ öåïÿì äëèíîé â äâå äóãè ìåæäó vi
è vj , à |Γ(vi )∩Γ−1 (vj )|  ÷èñëî òàêèõ öåïåé. Ïîñêîëüêó åäè-
íè÷íûå ýëåìåíòû i - ñòðîêè ìàòðèöû ñìåæíîñòè ñîîòâåòñòâó-
þò ýëåìåíòàì ìíîæåñòâà Γ(vi ) , à åäèíè÷íûå ýëåìåíòû
j - ñòîëáöà ýòîé ìàòðèöû
                   P           ýëåìåíòàì ìíîæåñòâà Γ−1 (vj ), òî
|Γ(vi )∩Γ−1 (vj )|= nk=1 aik akj . Òî æå ñàìîå ñëåäóåò èç àíàëèçà
ñõåì íà ðèñ. 4.2, ãäå ïðåäñòàâëåíû âñå âîçìîæíûå êîìáèíàöèè

           vi   aik =0  vk    akj =0  vj                 äóãè íåò
       a   s             s             s
           vi   aik =0 vsk    akj =1 -vsj
       á   s                                aik akj =0
           vi   aik =1 -vsk   akj =0 vsj                 äóãà åñòü
       â   s                                                    -
           vi   aik =1 -vsk   akj =1 -vsj
       ã   s                                aik akj =1
                         Ðèñ 4.2

ñóùåñòâîâàíèÿ äóã, îáðàçóþùèõ öåïü äëèíû 2 èç vi â vj ñ
ïðîìåæóòî÷íîé âåðøèíîé vk , à òàêæå çíà÷åíèÿ ñîîòâåòñòâó-
þùèõ ýëåìåíòîâ aik è akj ìàòðèöû ñìåæíîñòè. Åñëè èìåþò
ìåñòî ñëó÷àè à, á èëè
                   Pn â, öåïü îòñóòñòâóåò è ñîîòâåòñòâóþùåå
ñëàãàåìîå ñóììû     k=1 aik akj ðàâíî íóëþ.  ñëó÷àå ã öåïü
ñóùåñòâóåò, à ïðîèçâåäåíèå aik akj =1 è, ñëåäîâàòåëüíî, äàåò
ñâîé âêëàä â óêàçàííóþ ñóììó.
   Òàêèì îáðàçîì, çàäà÷à îïðåäåëåíèÿ ÷èñëà öåïåé (ìàðøðó-
òîâ) äëèíû 2 ìåæäó âñåìè ïàðàìè âåðøèí ãðàôà ìîæåò áûòü
ðåøåíà ïðîñòûì âîçâåäåíèåì â êâàäðàò åãî ìàòðèöû ñìåæíî-
ñòè. Àíàëîãè÷íî, êîëè÷åñòâî ìàðøðóòîâ äëèíû 3 ìîæåò áûòü
ïîëó÷åíî èç ìàòðèöû A3 è âîîáùå êîëè÷åñòâî ìàðøðóòîâ
                                                     (l)
äëèíû l ìåæäó âåðøèíàìè vi è vj ðàâíî ýëåìåíòó aij ìàò-
ðèöû Al . Íàêîíåö, êîëè÷åñòâî ìàðøðóòîâ äëèíû íå áîëåå p


                                   71

Страницы