Файл: Журавлев Флеров Дискретный анализ МФТИ 1991.pdf

106

ÃËÀÂÀ 3. ÝËÅÌÅÍÒÛ ÒÅÎÐÈÈ ÃÐÀÔÎÂ

Òàê êàê ãðàô

G

ñâÿçåí, â äîëæíà íàéòèñü âåðøèíà

b

, èíöèäåíòíàÿ òàê-

æå ðåáðàì èç

P

. Èç

b

ïîñòðîèì íîâûé ïóòü

P

0

, ñîäåðæàùèé ðåáðà òîëüêî

èç

P

. Ñíîâà òàêîé ïóòü ìîæåò çàêîí÷èòñÿ òîëüêî ïðè âîçâðàùåíèè â

b

. Íî

òîãäà èç è

P

0

ñîñòàâèì íîâûé ïóòü

P

1

P

1

=

P

(

a, b

)

∪

P

0

∪

P

(

b, a

)

,

êîòîðûé âîçâðàùàåòñÿ â è ñîäåðæèò áîëüøå ðåáåð, ÷åì .

Åñëè

P

1

íå ÿâëÿåòñÿ ýéëåðîâûì öèêëîì, òî ýòî ïîñòðîåíèå ïîâòîðÿåòñÿ.

Êîãäà ïðîöåññ çàêîí÷èòñÿ, ýéëåðîâ öèêë áóäåò ïîñòðîåí.

Ïðåäñòàâèì èçëîæåííûé ïðîöåññ ïîñòðîåíèÿ ýéëåðîâà öèêëà â âèäå ñõå-

ìû àëãîðèòìà íà ¾ïñåâäîàëãîðèòìè÷åñêîì¿ ÿçûêå.

3.7.1 Àëãîðèòì ïîñòðîåíèÿ ýéëåðîâà öèêëà

Ãðàô õðàíèòñÿ â âèäå ñïèñêà èíöèäåíöèé.

ÑÏÈÑÎÊ

[

v

]

 ñïèñîê âåðøèí ãðàôà, ñìåæíûõ ñ âåðøèíîé

v

.

Ìåòîä

Íà÷èíàåì ñòðîèòü ïóòü ñ íà÷àëîì â

v

, ïðè÷åì âåðøèíû ýòîãî ïóòè

ïîìåùàþòñÿ â ñòåê ÏÓÒÜ, à ð¼áðà óäàëÿþòñÿ èç ãðàôà.

Ýòî ïðîäîëæàåòñÿ äî òåõ ïîð, ïîêà ïóòü ìîæíî óäëèíèòü, âêëþ÷èâ

â íåãî íîâóþ âåðøèíó, ò.å. ÑÏÈÑÎÊ

[

v

]

6

=

∅

. Ýòî ñëó÷èòñÿ òîëüêî ïî

äîñòèæåíèþ âåðøèíû

v

. Òåì ñàìûì èç ãðàôà óäàëåí öèêë, à âåðøèíû

ýòîãî öèêëà íàõîäÿòñÿ â ñòåêå ÏÓÒÜ. Âåðøèíà

v

ïåðåíîñèòñÿ òåïåðü èç

ñïèñêà ÏÓÒÜ â ñòåê ÖÈÊË. Ïðîöåññ ïîâòîðÿåòñÿ.

Àëãîðèòì

1:

begin

2:

CTEK: ÏÓÒÜ

:=

∅

;

3:

ÑÒÅÊ: ÖÈÊË

:=

∅

;

4:

v

:=

ïðîèçâîëüíàÿ âåðøèíà â ãðàôå;

5:

ÏÓÒÜ

:=

v

; {Èíèöèàëèçàöèÿ}

6:

while ÏÓÒÜ

6

=

∅

do

7:

begin

8:

v

:=

ÏÓÒÜ;

9:

if ÑÏÈÑÎÊ

[

v

]

6

=

∅

then

10:

begin

11:

u

:=

ÏÅÐÂÀß ÂÅÐØÈÍÀ ÑÏÈÑÊÀ ÑÏÈÑÎÊ

[

v

]

;

12:

ÏÓÒÜ

:=

u

;

13:

ÑÏÈÑÎÊ

[

v

] :=

ÑÏÈÑÎÊ

[

v

]

\ {

u

}

;

3.7. ÝÉËÅÐÎÂÛ ÏÓÒÈ È ÖÈÊËÛ

107

14:

ÑÏÈÑÎÊ

[

u

] :=

ÑÏÈÑÎÊ

[

u

]

\ {

v

}

;

15:

v

:=

u

16:

end

17:

else

18:

begin

19:

v

:=

ÏÓÒÜ;

20:

ÖÈÊË

:=

v

21:

end

22:

end

23:

end

Îöåíèì âû÷èñëèòåëüíóþ ñëîæíîñòü àëãîðèòìà. Äëÿ ýòîãî îòìåòèì, ÷òî

êàæäîå ïîâòîðåíèå ãëàâíîãî öèêëà ëèáî ïîìåùàåò âåðøèíó â ñòåê ÏÓÒÜ

è óäàëÿåò ðåáðî èç ãðàôà, ëèáî ïåðåíîñèò âåðøèíó èç ñòåêà ÏÓÒÜ â ñòåê

ÖÈÊË. Òàêèì îáðàçîì, ÷èñëî èòåðàöèé ýòîãî öèêëà 

O

(

m

)

, ãäå

m

÷èñëî ðåáåð. Â ñâîþ î÷åðåäü ÷èñëî øàãîâ â êàæäîì ïîâòîðå îãðàíè÷åíî

êîíñòàíòîé. Îáùàÿ ñëîæíîñòü àëãîðèòìà åñòü

O

(

m

)

.

Ïðèâåäåì ïðèìåð ïîñòðîåíèÿ ýéëåðîâà öèêëà ñ ïîìîùüþ îïèñàííîãî

àëãîðèòìà.

Ïðèìåð

Ïóñòü ãðàô èìååò ñëåäóþùèé âèä:

Ïîñòðîèì ñïèñêè ñìåæíîñòè âåðøèí äëÿ óêàçàííîãî ãðàôà:

ÑÏÈÑÎÊ [1]: 2, 3;

ÑÏÈÑÎÊ [2]: 1, 3, 7, 8;

ÑÏÈÑÎÊ [3]: 1, 2, 4, 5;

ÑÏÈÑÎÊ [4]: 3, 5;

ÑÏÈÑÎÊ [5]: 3, 4, 6, 8;

ÑÏÈÑÎÊ [6]: 5, 7, 8, 9;

ÑÏÈÑÎÊ [7]: 2, 6, 8, 9;

ÑÏÈÑÎÊ [8]: 2, 5, 6, 7;

ÑÏÈÑÎÊ [9]: 6,7.

108

ÃËÀÂÀ 3. ÝËÅÌÅÍÒÛ ÒÅÎÐÈÈ ÃÐÀÔÎÂ

Âî âðåìÿ ðàáîòû àëãîðèòìà ñòåêè ÏÓÒÜ è ÖÈÊË èìåþò ñëåäóþùèé

âèä:

Ïðÿìîóãîëüíèêàìè â ñòåêå ÏÓÒÜ îáðàìëåíû âåðøèíû

v

, ïðè äîñòèæå-

íèè êîòîðûõ ÑÏÈÑÎÊ

[

v

] =

∅

. Òàêèå âåðøèíû íåìåäëåííî ïîìåùàþòñÿ â

ñòåê ÖÈÊË. Ïî èñ÷åðïàíèè ñïèñêà âñåõ âåðøèí (â íàøåì ïðèìåðå ïðè äî-

ñòèæåíèè ïîñëåäíåé âåðøèíû 8) âåðøèíû èç ñòåêà ÏÓÒÜ ïîñëåäîâàòåëüíî

âûòàëêèâàþòñÿ â ñòåê ÖÈÊË.

3.8 Ãàìèëüòîíîâû ïóòè è öèêëû

Ðàññìîòðèì òåïåðü çàäà÷ó ïðåäûäóùåãî ðàçäåëà ñ òîé ëèøü ðàçíèöåé, ÷òî

íà ýòîò ðàç íàñ áóäóò èíòåðåñîâàòü ïóòè, ïðîõîäÿùèå â òî÷íîñòè îäèí ðàç

÷åðåç êàæäóþ âåðøèíó (à íå êàæäîå ðåáðî) äàííîãî ãðàôà. Ýòà íåáîëü-

øàÿ, êàê ìîæåò ïîêàçàòüñÿ, ìîäèôèêàöèÿ ïðèâîäèò ê çíà÷èòåëüíîìó èç-

ìåíåíèþ õàðàêòåðà ïðîáëåìû.

Îïðåäåëåíèå. Ïðîñòîé ïóòü (öèêë) íàçûâàåòñÿ ãàìèëüòîíîâûì ïó-

òåì (öèêëîì), åñëè îí ïðîõîäèò ÷åðåç êàæäóþ âåðøèíó ãðàôà.

Ñëîâî ¾ãàìèëüòîíîâ¿ â ýòèõ îïðåäåëåíèÿõ ñâÿçàíî ñ èìåíåì èçâåñòíî-

ãî èðëàíäñêîãî ìàòåìàòèêà Ó. Ãàìèëüòîíà, êîòîðûé â 1859 ã. ïðåäëîæèë

èãðó ¾Êðóãîñâåòíîå ïóòåøåñòâèå¿. Â ýòîé èãðå ìèð ïðåäñòàâëåí äîäåêàýä-

ðîì, êàæäîé âåðøèíå êîòîðîãî ïðèïèñàíî íàçâàíèå îäíîãî èç ãîðîäîâ ìè-

ðà. Òðåáóåòñÿ, ïåðåõîäÿ èç îäíîãî ãîðîäà â äðóãîé ïî ðåáðàì äîäåêàýäðà,

ïîñåòèòü êàæäûé ãîðîä â òî÷íîñòè îäèí ðàç è âåðíóòüñÿ â èñõîäíûé ãîðîä.

Áîëåå òîëñòûìè ëèíèÿìè íà ãðàôå äîäåêàýäðà âûäåëåí ãàìèëüòîíîâ ïóòü.

3.8. ÃÀÌÈËÜÒÎÍÎÂÛ ÏÓÒÈ È ÖÈÊËÛ

109

Óêàæåì àíàëîãè÷íûì âûäåëåíèåì ãàìèëüòîíîâ ïóòü äëÿ ñëåäóþùåãî

ãðàôà:

Ñ äðóãîé ñòîðîíû, ëåãêî âèäåòü, ÷òî â ñëåäóþùåì ãðàôå íå ñóùåñòâóåò

ãàìèëüòîíîâûõ ïóòåé:

 îòëè÷èå îò ýéëåðîâûõ ïóòåé íå èçâåñòíî íè îäíîãî ïðîñòîãî íåîáõî-

äèìîãî è äîñòàòî÷íîãî óñëîâèÿ äëÿ ñóùåñòâîâàíèÿ ãàìèëüòîíîâûõ ïóòåé è

öèêëîâ, è ýòî íåñìîòðÿ íà òî, ÷òî çàäà÷à  îäíà èç öåíòðàëüíûõ â òåîðèè

ãðàôîâ. Íå èçâåñòåí òàê æå àëãîðèòì, êîòîðûé ïðîâåðÿë áû ñóùåñòâî-

âàíèå ãàìèëüòîíîâà ïóòè â ïðîèçâîëüíîì ãðàôå, èñïîëüçóÿ ÷èñëî øàãîâ,

îãðàíè÷åííîå ìíîãî÷ëåíîì îò ïåðåìåííîé

n

(÷èñëà âåðøèí â ãðàôå). Èìå-

þòñÿ âåñêèå îñíîâàíèÿ, íî íåò ìàòåìàòè÷åñêèõ äîêàçàòåëüñòâ òîãî, ÷òîáû

ïðåäïîëàãàòü, ÷òî òàêîå ïîëîæåíèå âûçâàíî íå íàøèì íåçíàíèåì, à ñêîðåå

òåì ôàêòîì, ÷òî òàêîãî àëãîðèòìà íå ñóùåñòâóåò. Ïðîáëåìà ñóùåñòâîâà-

íèÿ ãàìèëüòîíîâà ïóòè ïðèíàäëåæèò ê êëàññó òàê íàçûâàåìûõ NP-ïîëíûõ

çàäà÷. Ýòî øèðîêèé êëàññ çàäà÷, âêëþ÷àþùèé çàäà÷è èç òåîðèè ãðàôîâ,

ëîãèêè, òåîðèè ÷èñåë, äèñêðåòíîé îïòèìèçàöèè, íè äëÿ îäíîé èç êîòîðûõ

íå èçâåñòåí ïîëèíîìèàëüíûé àëãîðèòì (òî åñòü àëãîðèòì ñ ÷èñëîì øàãîâ,

îãðàíè÷åííûì ïîëèíîìîì îò ðàçìåðíîñòè çàäà÷è).

 ïðèìåíåíèÿõ ãðàôîâ ê èãðàì âåðøèíû ñîîòâåòñòâóþò ðàçëè÷íûì ïî-

çèöèÿì. Ñóùåñòâîâàíèå ãàìèëüòîíîâà öèêëà ðàâíîñèëüíî ñóùåñòâîâàíèþ

öèêëè÷åñêîé ïîñëåäîâàòåëüíîñòè õîäîâ, ñîäåðæàùåé êàæäóþ ïîçèöèþ ïî

îäíîìó ðàçó. (Ïðèìåð  çàäà÷à î øàõìàòíîì êîíå: ìîæíî ëè, íà÷èíàÿ ñ

ïðîèçâîëüíîãî ïîëÿ äîñêè, õîäèòü êîíåì òàê, ÷òîáû ïðîéòè ÷åðåç âñå ïîëÿ

è âåðíóòüñÿ â èñõîäíîå.)

Âûâåäåì íåêîòîðûå óñëîâèÿ, ïðè êîòîðûõ ìîæíî óòâåðæäàòü, ÷òî ãà-

ìèëüòîíîâ öèêë ñóùåñòâóåò. Ýòè ðàññìîòðåíèÿ òåñíî ñâÿçàíû ñî ñâîéñòâà-

ìè ìàêñèìàëüíûõ ïðîñòûõ ïóòåé.

Ïóñòü

S

=

< a

0

, a

1

, . . . , a

k

>

 íåêîòîðûé ïðîñòîé ïóòü äëèíû

k

â

ãðàôå

G

=

< V, E >

.

110

ÃËÀÂÀ 3. ÝËÅÌÅÍÒÛ ÒÅÎÐÈÈ ÃÐÀÔÎÂ

Îïðåäåëèì ïîäãðàô

G

0

=

<

{

a

0

, . . . , a

k

}

, E

0

>

=

< S, E

0

> .

Áóäåì ãîâîðèòü, ÷òî

S

èìååò òèï öèêëà, åñëè ïîäãðàô

G

0

=

< S, E

0

> ,

E

0

⊆

E

: (

{

u, v

} ∈

E

0

⇔

u, v

∈

S,

{

u, v

} ∈

E

)

èìååò ãàìèëüòîíîâ öèêë.

Îòñþäà, â ÷àñòíîñòè, ñëåäóåò, ÷òî

S

ÿâëÿåòñÿ ãàìèëüòîíîâûì ïóòåì

â

G

0

.

Ïóñòü

(

a

0

, a

i

)

∈

E

0

 íåêîòîðîå ðåáðî â ãðàôå

G

0

. Åñëè ñóùåñòâóåò

òàêæå ðåáðî

(

a

k

, a

i

−

1

)

, òî â

G

0

áóäåò ãàìèëüòîíîâ öèêë, à èìåííî

(

a

0

, a

i

)

∪

S

(

a

i

, a

k

)

∪

(

a

k

, a

i

−

1

)

∪

S

(

a

i

−

1

, a

0

)

.

Åñëè, îäíàêî,

ρ

0

(

a

k

)

> k

−

ρ

0

(

a

0

)

, ãäå

ρ

0

(

a

0

)

è

ρ

0

(

a

k

)

ñòåïåíè âåðøèí

a

0

è

a

k

â ãðàôå

G

0

, òî ÿñíî, ÷òî õîòÿ áû äëÿ îäíîãî ðåáðà

(

a

0

, a

i

)

äîëæíî

ñóùåñòâîâàòü ñîîòâåòñòâóþùåå ðåáðî

(

a

k

, a

i

−

1

)

. Ïîýòîìó åñëè

ρ

0

(

a

0

) +

ρ

0

(

a

k

)

≥

k

+ 1

, òî ïðîñòîé ïóòü

S

áóäåò èìåòü òèï öèêëà.

Áóäåì ãîâîðèòü, ÷òî ïðîñòîé ïóòü  ïîëíûé, åñëè åãî íåëüçÿ ïðîäîë-

æèòü ïðè ïîìîùè äîáàâëåíèÿ ðåáåð ê êàêîìó-íèáóäü èç êîíöîâ. Òîãäà

âñå ðåáðà îò

a

0

è îò

a

k

äîëæíû èäòè ê âåðøèíàì ãðàôà

G

0

, òàê ÷òî

ρ

(

a

0

) =

ρ

0

(

a

0

)

, ρ

(

a

k

) =

ρ

0

(

a

k

)

.

Ýòî äàåò ñëåäóþùóþ òåîðåìó.

Òåîðåìà 3.13. Ïîëíûé ïðîñòîé ïóòü äëèíû

k

èìååò òèï öèêëà, åñëè

ρ

(

a

0

) +

ρ

(

a

k

)

≥

k

+ 1

.

Òåîðåìà 3.14. Ìàêñèìàëüíûé ïðîñòîé ïóòü â ñâÿçíîì ãðàôå ìîæåò

èìåòü òèï öèêëà òîëüêî òîãäà, êîãäà ãðàô èìååò ãàìèëüòîíîâ öèêë.

Äîêàçàòåëüñòâî. 1). Åñëè

G

èìååò ãàìèëüòîíîâ öèêë, òî ìàêñèìàëüíûé

ïðîñòîé ïóòü äëèíû

n

−

1

èìååò òèï öèêëà.

2). Åñëè ïîäãðàô

G

0

, ñîîòâåòñòâóþùèé ìàêñèìàëüíîìó ïðîñòîìó ïóòè

èìååò ãàìèëüòîíîâ öèêë, íî

G

0

íå ñîñòàâëÿåò âñåãî ãðàôà, òî èç-çà ñâÿçíî-

ñòè

G

ñóùåñòâóåò íåêîòîðîå ðåáðî

(

a

i

, b

)

, â êîòîðîì

b

íå ïðèíàäëåæèò

G

0

.

Ýòî, îäíàêî, íåâîçìîæíî òàê êàê òîãäà íàøåëñÿ áû ïðîñòîé ïóòü, êîòîðûé

áûë áû äëèííåå äàííîãî ïðîñòîãî ïóòè

S

.