Дискретная математика: Основы теории графов и алгоритмизация задач. Прокушев Л.А. - 40 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

40
2.3. Ïóòü ñ íàèìåíüøèì ÷èñëîì äóã.
Ïîèñê òðàíçèòèâíîãî çàìûêàíèÿ âåðøèí
Ïîñòàíîâêà çàäà÷è. Ïóñòü çàäàí ïðîèçâîëüíûé ãðàô G=(V,U). Òðåáó-
åòñÿ ïîñòðîèòü òàêîé ïóòü, ñîåäèíÿþùèé äâå çàäàííûå âåðøèíû v è w,
êîòîðûé ñîäåðæèò íàèìåíüøåå ÷èñëî äóã (ýòî ïóòü ìèíèìàëüíîé äëè-
íû, åñëè ñ÷èòàòü, ÷òî äëèíû âñåõ äóã îäèíàêîâû, ò. å. ýëåìåíòàðíûé
ïóòü).
2.3.1. Ìåòîä ðåøåíèÿ çàäà÷è ïîèñêà ïóòè
ñ íàèìåíüøèì ÷èñëîì äóã
Ðàññìîòðèì àëãîðèòì ýòîé çàäà÷è, êîòîðûé ïðîèëëþñòðèðîâàí íà
ðèñ. 2.4. Àëãîðèòì ìîæíî ðàçäåëèòü íà äâà ýòàïà: ïðÿìîé õîä  ïðèñâà-
èâàíèå âåðøèíàì ãðàôà ìåòîê; îáðàòíûé õîä  îïðåäåëåíèå ìèíèìàëü-
íîãî ïóòè îò êîíå÷íîé âåðøèíû äî èñõîäíîé.
Ïðÿìîé õîä:
1. Ïðèñâîèòü âåðøèíå v ìåòêó 0.
2. Åñëè x
i
∈ Ãv è x
i
≠ v, òî ïðèñâîèòü êàæäîé òàêîé âåðøèíå ìåòêó 1,
(ò. å. ýòî âåðøèíû-êîíöû äóã, èñõîäÿùèõ èç âåðøèíû v, êðîìå ñàìîé
âåðøèíû v, ïðè ýòîì èñêëþ÷àþòñÿ ïåòëè).
3. Ïóñòü X(m) (m=0,1,2,...) ìíîæåñòâî âåðøèí, èìåþùèõ ìåòêó m.
Âåðøèíàì
X( 1) {
ÃX( ), X( ) ïðè }
mxmxkkm
+=∈ ∉ ≤
(ò. å. âåðøèíàì
êîíöàì äóã, èñõîäÿùèõ èç âåðøèí ìíîæåñòâà Õ(m), êðîìå âåðøèí, óæå
ïîëó÷èâøèõ ìåòêè ðàíåå, òåì ñàìûì èñêëþ÷àþòñÿ êîíòóðû) ïðèñâî-
èòü ìåòêè m+1.
4. Ïðîöåññ ïðèñâîåíèÿ âåðøèíàì ìåòîê ïðåêðàòèòü, êàê òîëüêî âåð-
øèíà w ïîëó÷èò ìåòêó n (w∈X(n)).
Îáðàòíûé õîä:
5. Ðàññìîòðåòü âåðøèíû
12
, ,...,
n
ii i
xx x
òàêèå, ÷òî
1
i
x
∈ X(n1), w ∈ Ã
1
i
x
,
2
i
x
∈ X(n2),
1
i
x
∈ Ã
2
i
x
,
.....................................
n
i
x
∈ X(0),
1
n
i
x
−
∈ Ã
n
i
x
.
Ïóòü µ = ( v =
n
i
x
,
1
n
i
x
−
, . ..,
2
i
x
,
1
i
x
, w ) äàåò ðåøåíèå çàäà÷è.
Çàìå÷àíèå. Åñëè íà íåêîòîðîì øàãå íåâîçìîæíî ïðèñâîåíèå ìåòêè
m+1 âåðøèíàì, ïîñêîëüêó ìíîæåñòâî ÃX(m) ïóñòî è âåðøèíà w íå ïî-
ëó÷èëà ìåòêè, òî ýòî îçíà÷àåò, ÷òî â ãðàôå G íå ñóùåñòâóåò ïóòè, ñî-
åäèíÿþùåãî âåðøèíó v ñ âåðøèíîé w.

Страницы