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

3.3. ÏÎÈÑʠ ÃÐÀÔÅ

91

Àëãîðèòì íà÷èíàåò ïîèñê ïîî÷åðåäíî îò êàæäîé åùå íå ïðîñìîòðåííîé

âåðøèíû, ñëåäîâàòåëüíî, ïðîñìàòðèâàþòñÿ âñå âåðøèíû ãðàôà (íåîáÿçà-

òåëüíî ñâÿçíîãî).

×òîáû îöåíèòü ñëîæíîñòü àëãîðèòìà, îòìåòèì ñíà÷àëà, ÷òî ÷èñëî øà-

ãîâ â îáîèõ öèêëàõ (ñòðîêè 2-5 àëãîðèòìà) ïîðÿäêà

n

, íå ñ÷èòàÿ øàãîâ, âû-

ïîëíåíèå êîòîðûõ èíèöèèðîâàíî âûçîâîì ïðîöåäóðû ÏÎÈÑÊ_Â_

ÃËÓÁÈÍÓ_Â_ÃÐÀÔÅ_

G

. Ýòà ïðîöåäóðà âûïîëíÿåòñÿ íå áîëåå

n

ðàç

âî âòîðîì öèêëå ñðàçó ïîñëå ïîñåùåíèÿ êàæäîé âåðøèíû äëÿ êàæäîãî

èç åå íîâûõ ñîñåäåé, èòîãî ñóììàðíî

O

(

n

+

m

)

ðàç. Ïîëíîå ÷èñëî øàãîâ,

âûïîëíÿåìîå öèêëîì â ñòðîêå 5 ïðîöåäóðû ÏÎÈÑÊ_Â_ÃËÓÁÈÍÓ_Â_

ÃÐÀÔÅ_

G

, äëÿ âñåõ âûçîâîâ ýòîé ïðîöåäóðû áóäåò ïîðÿäêà

m

, ãäå

m

÷èñëî ðåáåð. Ýòî äàåò îáùóþ ñëîæíîñòü àëãîðèòìà

O

(

n

+

m

)

.

Îòìåòèì, ÷òî àëãîðèòì ïîèñêà â ãëóáèíó â ãðàôå ëåãêî ìîäèôèöèðî-

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

 ñâÿçè ñ òåì, ÷òî ïîèñê â ãëóáèíó èãðàåò âàæíóþ ðîëü â ïðîåêòèðî-

âàíèè àëãîðèòìîâ íà ãðàôàõ, ïðåäñòàâëÿåò èíòåðåñ íåðåêóðñèâíàÿ âåðñèÿ

ïðîöåäóðû ÏÎÈÑÊ_Â_ÃËÓÁÈÍÓ_Â_ÃÐÀÔÅ_

G

. Ðåêóðñèÿ óñòðàíÿåò-

ñÿ ñòàíäàðòíûì ñïîñîáîì ïðè ïîìîùè ñòåêà. Êàæäàÿ ïðîñìîòðåííàÿ âåð-

øèíà ïîìåùàåòñÿ â ñòåê è óäàëÿåòñÿ èç ñòåêà ïîñëå åå èñïîëüçîâàíèÿ.

Ìåòîä ïîèñêà â ãëóáèíó î÷åâèäíûì îáðàçîì ïåðåíîñèòñÿ íà îðèåíòè-

ðîâàííûå ãðàôû.

3.3.2 Ïîèñê â øèðèíó â ãðàôå

Òåïåðü ðàññìîòðèì íåñêîëüêî èíîé ìåòîä ïîèñêà â ãðàôå, íàçûâàåìûé ïî-

èñêîì â øèðèíó. Ïðåæäå ÷åì îïèñàòü åãî, îòìåòèì, ÷òî ïðè ïîèñêå â ãëó-

áèíó ÷åì ïîçäíåå áóäåò ïîñåùåíà âåðøèíà, òåì ðàíüøå îíà áóäåò èñïîëü-

çîâàíà - òî÷íåå, òàê áóäåò ïðè äîïóùåíèè, ÷òî âòîðàÿ âåðøèíà ïîñåùàåòñÿ

ïåðåä èñïîëüçîâàíèåì ïåðâîé. Ýòî ïðÿìîå ñëåäñòâèå òîãî ôàêòà, ÷òî ïðî-

ñìîòðåííûå, íî åùå íå èñïîëüçîâàííûå âåðøèíû íàêàïëèâàþòñÿ â ñòåêå.

Ïîèñê â øèðèíó îñíîâûâàåòñÿ, ãðóáî ãîâîðÿ, íà çàìåíå ñòåêà î÷åðåäüþ.

Ïîñëå òàêîé ìîäèôèêàöèè ÷åì ðàíüøå ïîñåùàåòñÿ âåðøèíà (ïîìåùàåòñÿ

â î÷åðåäü), òåì ðàíüøå îíà èñïîëüçóåòñÿ (óäàëÿåòñÿ èç î÷åðåäè). Èñïîëü-

çîâàíèå âåðøèíû ïðîèñõîäèò ñ ïîìîùüþ ïðîñìîòðà âñåõ åùå íåïðîñìîò-

ðåííûõ ñîñåäåé ýòîé âåðøèíû. Âñÿ ïðîöåäóðà ïðåäñòàâëåíà íèæå:

92

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

1:

procedure ÏÎÈÑÊ_Â_ØÈÐÈÍÓ_Â_ÃÐÀÔÅ

(

v

)

; {ïîèñê â øèðèíó

â ãðàôå ñ íà÷àëîì â âåðøèíå

v

; ïåðåìåííûå ÍÎÂÛÉ, ÑÏÈÑÎÊ 

ãëîáàëüíûå}

2:

begin

3:

Î×ÅÐÅÄÜ: =

∅

;

4:

Î×ÅÐÅÄÜ

⇐

v

;

5:

ÍÎÂÛÉ

[

v

]

: = ëîæü;

6:

while Î×ÅÐÅÄÜ

6

=

∅

do

7:

begin

8:

p

⇐

Î×ÅÐÅÄÜ;

9:

ïîñåòèòü

p

;

10:

for

u

∈

ÇÀÏÈÑÜ

[

p

]

do

11:

if ÍÎÂÛÉ

[

u

]

then

12:

begin

13:

Î×ÅÐÅÄÜ

⇐

u

;

14:

ÍÎÂÛÉ

[

u

]

:=ëîæü;

15:

end

16:

end

17:

end {âåðøèíà

v

èñïîëüçîâàíà}

Ñïîñîáîì, àíàëîãè÷íûì òîìó, êîòîðûé áûë ïðèìåíåí äëÿ ïîèñêà â ãëó-

áèíó, ìîæíî ëåãêî ïîêàçàòü, ÷òî âûçîâ ïðîöåäóðû ÏÎÈÑÊ_Â_ØÈÐÈÍÓ_

Â_ÃÐÀÔÅ

(

v

)

ïðèâîäèò ê ïîñåùåíèþ âñåõ âåðøèí ñâÿçíîé êîìïîíåíòû

ãðàôà, ñîäåðæàùåé âåðøèíó

v

, ïðè÷åì êàæäàÿ âåðøèíà ïðîñìàòðèâàåòñÿ

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

ðèíó òàêæå èìååò ïîðÿäîê

m

+

n

, òàê êàê êàæäàÿ âåðøèíà ïîìåùàåòñÿ

â î÷åðåäü è óäàëÿåòñÿ èç î÷åðåäè â òî÷íîñòè îäèí ðàç, à ÷èñëî èòåðàöèé

öèêëà 10, î÷åâèäíî, áóäåò èìåòü ïîðÿäîê ÷èñëà ðåáåð ãðàôà.

Ðèñ. 3.4

3.4. ÏÓÒÈ È ÖÈÊËÛ

93

Íà ðèñ. 3.4 ïðåäñòàâëåí ãðàô, âåðøèíû êîòîðîãî çàíóìåðîâàíû (â ñêîá-

êàõ) ñîãëàñíî î÷åðåäíîñòè, â êîòîðîé îíè ïîñåùàþòñÿ â ïðîöåññå ïîèñêà â

øèðèíó.

Êàê è â ñëó÷àå ïîèñêà â ãëóáèíó, ïðîöåäóðó ÏÎÈÑÊ_Â_ØÈÐÈÍÓ_Â_

ÃÐÀÔÅ

(

v

)

ìîæíî èñïîëüçîâàòü áåç âñÿêèõ ìîäèôèêàöèé è òîãäà, êîãäà

ñïèñîê èíöèäåíòíîñòè ÑÏÈÑÎÊ

[

v

]

,

v

∈

V

, îïðåäåëÿåò íåêîòîðûé îðèåí-

òèðîâàííûé ãðàô. Î÷åâèäíî, ÷òî òîãäà ïîñåùàþòñÿ òîëüêî òå âåðøèíû,

äî êîòîðûõ ñóùåñòâóåò ïóòü îò âåðøèíû, ñ êîòîðîé ìû íà÷èíàåì ïîèñê.

3.4 Ïóòè è öèêëû

Îïðåäåëåíèå. Ïóòåì â îðèåíòèðîâàííîì èëè íåîðèåíòèðîâàííîì ãðà-

ôå

G

=

< V, E >

íàçûâàþò ïîñëåäîâàòåëüíîñòü ðåáåð âèäà

<

(

v

1

, v

2

)

,

(

v

2

, v

3

)

, . . . ,

(

v

n

−

1

, v

n

)

>

=

S

=

< E

1

, . . . , E

n

−

1

>

, ãäå

E

i

= (

v

i

, v

i

+1

)

∈

E

,

E

i

è

E

i

+1

èíöèäåíòíû îäíîé âåðøèíå. Ãîâîðÿò, ÷òî ýòîò ïóòü èäåò èç

v

1

â

v

n

è èìååò äëèíó

n

−

1

. ×àñòî òàêîé ïóòü ïðåäñòàâëÿþò ïîñëåäîâàòåëü-

íîñòüþ âåðøèí

< v

1

, . . . , v

n

>, < v

i

, v

i

+1

>

∈

E

, ëåæàùèõ íà íåì. Â

âûðîæäåííîì ñëó÷àå îäíà âåðøèíà îáîçíà÷àåò ïóòü äëèíû 0, èäóùèé èç

ýòîé âåðøèíû â íåå æå.

Ïóòü íàçûâàåòñÿ ïðîñòûì, åñëè âñå ðåáðà è âñå âåðøèíû íà íåì, êðîìå

áûòü ìîæåò ïåðâîé è ïîñëåäíåé, ðàçëè÷íû.

Îïðåäåëåíèå. Öèêë  ýòî ïðîñòîé ïóòü äëèíû íå ìåíåå 1, êîòîðûé

íà÷èíàåòñÿ è çàêàí÷èâàåòñÿ â îäíîé è òîé æå âåðøèíå. Çàìåòèì, ÷òî â

íåîðèåíòèðîâàííîì ïðîñòîì ãðàôå äëèíà öèêëà äîëæíà áûòü íå ìåíåå 3.

Îáà âèäà ïîèñêà â ãðàôå  â ãëóáèíó è â øèðèíó  ìîãóò áûòü èñ-

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

v

è

u

. Äîñòàòî÷íî íà÷àòü ïîèñê â ãðàôå ñ âåðøèíû

v

è âåñòè åãî äî ìîìåí-

òà ïîñåùåíèÿ âåðøèíû

u

. Ïðåèìóùåñòâîì ïîèñêà â ãëóáèíó ÿâëÿåòñÿ òîò

ôàêò, ÷òî â ìîìåíò ïîñåùåíèÿ âåðøèíû

u

ñòåê ñîäåðæèò ïîñëåäîâàòåëü-

íîñòü âåðøèí, îïðåäåëÿþùèõ ïóòü èç

v

â

u

. Ýòî ñòàíîâèòñÿ î÷åâèäíûì,

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

íîé ñ âåðõíèì ýëåìåíòîì ñòåêà. Îäíàêî íåäîñòàòêîì ïîèñêà â ãëóáèíó ÿâ-

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

êðàò÷àéøèì ïóòåì èç

v

â

u

.

Îò ýòîãî íåäîñòàòêà ñâîáîäåí ìåòîä íàõîæäåíèÿ ïóòè, îñíîâàííûé íà

ïîèñêå â øèðèíó. Ìîäèôèöèðóåì ïðîöåäóðó ÏÎÈÑÊ_Â_ØÈÐÈÍÓ_Â_

ÃÐÀÔÅ

(

v

)

, çàìåíÿÿ ñòðîêè 1115 íà

94

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

if ÍÎÂÛÉ

[

u

]

then

begin

Î×ÅÐÅÄÜ

⇐

u

;

ÍÎÂÛÉ

[

u

] :=

ëîæü;

ÏÐÅÄÛÄÓÙÈÉ

[

u

] :=

p

;

end

Ïî îêîí÷àíèè ðàáîòû ìîäèôèöèðîâàííîé òàêèì îáðàçîì ïðîöåäóðû

ìàññèâ ÏÐÅÄÛÄÓÙÈÉ ñîäåðæèò äëÿ êàæäîé ïðîñìîòðåííîé âåðøèíû

u

âåðøèíó ÏÐÅÄÛÄÓÙÈÉ

[

u

]

, èç êîòîðîé ìû ïîïàëè â

u

. Îòìåòèì, ÷òî

êðàò÷àéøèé ïóòü èç âåðøèíû

u

â âåðøèíó

v

îáîçíà÷àåòñÿ ïîñëåäîâàòåëü-

íîñòüþ âåðøèí

u

=

u

1

, u

2

, . . . , u

k

=

v

, ãäå

u

i

+1

= ÏÐÅÄÛÄÓÙÈÉ

[

u

i

]

äëÿ

1

≤

i < k

è

k

ÿâëÿåòñÿ ïåðâûì èíäåêñîì

i

äëÿ êîòîðîãî

u

i

=

v

.

Äåéñòâèòåëüíî, â î÷åðåäè ïîìåùåíû ñíà÷àëà âåðøèíû, íàõîäÿùèåñÿ íà

ðàññòîÿíèè 0 îò

v

(ò.å. ñàìà âåðøèíà

v

), çàòåì ïîî÷åðåäíî âñå íîâûå âåð-

øèíû, íàõîäÿùèåñÿ íà ðàññòîÿíèè 1 îò

v

, è ò.ä. Ïîä ðàññòîÿíèåì çäåñü ìû

ïîíèìàåì äëèíó êðàò÷àéøåãî ïóòè. Ïðåäïîëîæèì òåïåðü, ÷òî ìû óæå ðàñ-

ñìîòðåëè âñå âåðøèíû, íàõîäÿùèåñÿ íà ðàññòîÿíèè, íå ïðåâîñõîäÿùåì

r

îò

v

, ÷òî î÷åðåäü ñîäåðæèò âñå âåðøèíû, íàõîäÿùèåñÿ íà ðàññòîÿíèè

r

îò

v

, è

òîëüêî ýòè âåðøèíû è ÷òî ìàññèâ ÏÐÅÄÛÄÓÙÈÉ ïðàâèëüíî îïðåäåëÿåò

êðàò÷àéøèé ïóòü îò êàæäîé, óæå ïðîñìîòðåííîé âåðøèíû äî âåðøèíû

v

ñïîñîáîì, îïèñàííûì âûøå. Èñïîëüçîâàâ êàæäóþ âåðøèíó

p

, íàõîäÿùóþ-

ñÿ â î÷åðåäè, íàøà ïðîöåäóðà ïðîñìàòðèâàåò íåêîòîðûå íîâûå âåðøèíû, è

êàæäàÿ òàêàÿ íîâàÿ âåðøèíà

u

íàõîäèòñÿ íà ðàññòîÿíèè

r

+ 1

îò

v

, ïðè÷åì,

îïðåäåëÿÿ ÏÐÅÄÛÄÓÙÈÉ

[

u

] :=

p

, ìû ïðîäëåâàåì êðàò÷àéøèé ïóòü îò

p

äî

v

äî êðàò÷àéøåãî ïóòè îò

u

äî

v

. Ïîñëå èñïîëüçîâàíèÿ âñåõ âåðøèí èç

î÷åðåäè, íàõîäÿùèõñÿ íà ðàññòîÿíèè

r

îò

v

, îíà (î÷åðåäü), î÷åâèäíî, ñî-

äåðæèò ìíîæåñòâî âåðøèí, íàõîäÿùèõñÿ íà ðàññòîÿíèè

r

+ 1

îò

v

, è ëåãêî

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

r

+ 1

.

3.5 Ñâÿçíîñòü

Îïðåäåëåíèå. Ïóñòü ãðàô

G

 íåîðèåíòèðîâàííûé. Äâå âåðøèíû

a

è

b

íàçûâàþòñÿ ñâÿçàííûìè, åñëè ñóùåñòâóåò ïóòü

S

ñ íà÷àëüíîé âåðøèíîé

a

è êîíå÷íîé âåðøèíîé

b

,

S

=

< a, a

1

, . . . , a

n

, b > .

Åñëè

S

ïðîõîäèò ÷åðåç

êàêóþ-íèáóäü âåðøèíó

a

i

áîëåå îäíîãî ðàçà, òî ìîæíî, î÷åâèäíî, óäàëèòü

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

ïóòü

S

èç

a

â

b

. Îòñþäà ñëåäóåò, ÷òî ñâÿçàííûå ïóòåì âåðøèíû ñâÿçàíû

è ïðîñòûì ïóòåì. Ãðàô íàçûâàåòñÿ ñâÿçíûì, åñëè ëþáàÿ åãî ïàðà âåðøèí

3.5. ÑÂßÇÍÎÑÒÜ

95

ñâÿçàíà. Äëÿ âñÿêîãî ãðàôà ñóùåñòâóåò òàêîå ðàçáèåíèå ìíîæåñòâà åãî

âåðøèí

V

=

[

i

V

i

íà ïîïàðíî íåïåðåñåêàþùèåñÿ ïîäìíîæåñòâà âåðøèí

V

i

, ÷òî âåðøèíû â

êàæäîì

V

i

ñâÿçàíû, à âåðøèíû èç ðàçëè÷íûõ

V

i

íå ñâÿçàíû.

Ãðàô

H

íàçûâàåòñÿ ÷àñòüþ ãðàôà

G

, åñëè ìíîæåñòâî åãî âåðøèí

V

(

H

)

ñîäåðæèòñÿ âî ìíîæåñòâå âåðøèí

V

(

G

)

ãðàôà

G

è âñå ðåáðà

H

ÿâëÿþòñÿ

ðåáðàìè

G

. Äëÿ ëþáîé ÷àñòè

H

ãðàôà

G

ñóùåñòâóåò åäèíñòâåííàÿ äîïîë-

íèòåëüíàÿ ÷àñòü (äîïîëíåíèå)

H

, ñîñòîÿùåå èç âñåõ ðåáåð ãðàôà

G

, êîòî-

ðûå íå âîøëè â

H

, è èíöèäåíòíûõ èì âåðøèí. Îñîáåííî âàæíûì òèïîì

÷àñòåé ÿâëÿþòñÿ ïîäãðàôû.

Ïóñòü

V

0

 ïîäìíîæåñòâî âåðøèí ãðàôà

G

=

< V, E >, V

0

∈

V

. Ïîä-

ãðàô

G

(

V

0

, E

0

)

, îïðåäåëÿåìûé ìíîæåñòâîì

V

0

, åñòü òàêàÿ ÷àñòü ãðàôà

G

,

ìíîæåñòâîì âåðøèí êîòîðîé ÿâëÿåòñÿ

V

0

, à ðåáðàìè  âñå ðåáðà èç

G

, îáà

êîíöà êîòîðûõ ëåæàò â

V

0

:

G

(

V

0

, E

0

) =

G

(

V

0

, E

0

=

{

(

u, v

)

|

((

u, v

)

∈

E

)

∧

(

u, v

∈

V

0

)

}

)

.

Òîãäà â ñîîòâåòñòâèè ñ ðàçáèåíèåì

V

=

S

i

V

i

ìû ïîëó÷àåì ïðÿìîå ðàçëî-

æåíèå

G

=

[

i

G

(

V

i

, E

i

)

ãðàôà

G

íà íåïåðåñåêàþùèåñÿ ñâÿçíûå ïîäãðàôû

G

(

V

i

)

. Ýòè ïîäãðàôû íà-

çûâàþòñÿ ñâÿçíûìè êîìïîíåíòàìè (èëè êîìïîíåíòàìè ñâÿçíîñòè) ãðà-

ôà

G

.

Òåîðåìà 3.2. Åñëè â êîíå÷íîì íåîðèåíòèðîâàííîì ïðîñòîì ãðàôå

G

ðîâ-

íî äâå âåðøèíû

a

0

è

b

0

èìåþò íå÷åòíóþ ëîêàëüíóþ ñòåïåíü, òî îíè ñâÿ-

çàíû.
Äîêàçàòåëüñòâî. Ïî òåîðåìå 3.1, êàæäûé êîíå÷íûé ãðàô èìååò ÷åòíîå

÷èñëî âåðøèí íå÷åòíîé ñòåïåíè. Òàê êàê ýòî óñëîâèå âûïîëíÿåòñÿ è äëÿ

òîé êîìïîíåíòû

G

, êîòîðîé ïðèíàäëåæèò

a

0

, òî

b

0

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

êîìïîíåíòå ñâÿçíîñòè.

Òåîðåìà 3.3. Åñëè íåîðèåíòèðîâàííûé ïðîñòîé ãðàô

G

èìååò

n

âåðøèí

è

k

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

G

ðàâíî

N

(

n, k

) =

1

2

(

n

−

k

)(

n

−

k

+ 1)

.