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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

l
P
(l)
P
(l)
=P
0
×P
(l−1)
,
l=1, 2, . . . , P
(0)
P
0
P
(n−2)
P
(n−2)
n−1
P
(n−1)
n
P
(n−1)
v.
v
P
(l)
v
= P
0
× P
(l−1)
v
,
l=1, 2, . . . , (n−1), P
(l)
v
P
(l)
,
v. P
(0)
v
v
îêàçûâàåòñÿ ïðîäåëàííîé âïóñòóþ. Íà ïðàêòèêå ïðèìåíÿþò
ìåòîäû ÷àñòè÷íîãî ïåðåáîðà, â îñíîâå êîòîðûõ ëåæàò ðàçëè÷-
íûå êðèòåðèè, ïîçâîëÿþùèå èñêëþ÷èòü ðàñìîòðåíèå âàðèàí-
òîâ öåïåé, îòñóòñòâóþùèõ â çàäàííîì ãðàôå. Ðàññìîòðèì äâà
òàêèõ ìåòîäà, äåìîíñòðèðóþùèõ ðàçíûå ïîäõîäû ê ïîèñêó ãà-
ìèëüòîíîâûõ öèêëîâ.
   Àëãåáðàè÷åñêèé ìåòîä.  ðàçä. 4.3 áûëà ââåäåíà ìàò-
ðèöà âñåõ ìàðøðóòîâ ñ l ïðîìåæóòî÷íûìè âåðøèíàìè äëÿ
âñåõ óïîðÿäî÷åííûõ ïàð âåðøèí ãðàôà, îáîçíà÷åííàÿ êàê
P(l) è îïðåäåëÿåìàÿ ñ ïîìîùüþ ðåêóððåíòíîãî ñîîòíîøåíèÿ
                       P(l) =P0 ×P(l−1) ,
ãäå l=1, 2, . . . , â êà÷åñòâå P(0) áåðåòñÿ ìàòðèöà ñìåæíîñòè
ãðàôà, à P0 ïîëó÷àåòñÿ èç òîé æå ìàòðèöû ñìåæíîñòè, åñ-
ëè â êàæäîì åå ñòîëáöå åäèíèöû çàìåíèòü ìåòêîé âåðøèíû,
ñîîòâåòñòâóþùåé ñòîëáöó.
   Î÷åâèäíî, ÷òî ìàòðèöó âñåõ ãàìèëüòîíîâûõ öåïåé ãðàôà
ìîæíî ïîëó÷èòü, èñêëþ÷èâ èç ìàòðèöû P(n−2) ïðîèçâåäåíèÿ
ñ ïîâòîðÿþùèìèñÿ ñîìíîæèòåëÿìè (ñ÷èòàÿ è êîíå÷íûå âåð-
øèíû öåïåé). Äèàãîíàëüíûå ýëåìåíòû îáðàáîòàííîé òàêèì
îáðàçîì ìàòðèöû P(n−2) â ñîâîêóïíîñòè îïèñûâàþò âñå ïðî-
ñòûå öèêëû ãðàôà, ñîäåðæàùèå n−1 âåðøèí, à äèàãîíàëü-
íûå ýëåìåíòû ìàòðèöû P(n−1) ïîñëå àíàëîãè÷íîé îáðàáîòêè
äàþò âñå ïðîñòûå öèêëû ãðàôà, âêëþ÷àþùèå n âåðøèí, ò. å.
ãàìèëüòîíîâû öèêëû, ïðè÷åì ëþáîé äèàãîíàëüíûé ýëåìåíò
îòðàæàåò âñå öèêëû. Ýòî çíà÷èò, ÷òî âìåñòî ìàòðèöû P(n−1)
äîñòàòî÷íî ñôîðìèðîâàòü òîëüêî îäèí èç åå ñòîëáöîâ, ñîîò-
âåòñòâóþùèé ïðîèçâîëüíî âûáðàííîé âåðøèíå v. Èñêîìûé
ðåçóëüòàò ñîäåðæèòñÿ â ñòðîêå v íàéäåííîãî ñòîëáöà.
   Äëÿ âû÷èñëåíèé ìîæíî èñïîëüçîâàòü ñîîòíîøåíèå
                      P(l)  0   (l−1)
                       v = P × Pv     ,
                           (l)
ãäå l=1, 2, . . . , (n−1), à Pv  ñòîëáåö ìàòðèöû P(l) , ñîîò-
                                          (0)
âåòñòâóþùèé âåðøèíå v.  êà÷åñòâå Pv ñëåäóåò ïðèíÿòü
ñòîëáåö v ìàòðèöû ñìåæíîñòè ãðàôà.


                                 117

Страницы