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

86

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

Ïóñòü

G

 íåîðèåíòèðîâàííûé ãðàô. ×èñëî

ρ

(

x

)

ðåáåð, èíöèäåíòíûõ

âåðøèíå

x

, íàçûâàåòñÿ ëîêàëüíîé ñòåïåíüþ, èëè ïðîñòî ñòåïåíüþ âåðøè-

íû

x

ãðàôà

G

. Â êàæäîì ñëó÷àå äîëæíî áûòü óêàçàíî, ñ÷èòàåòñÿ ïåòëÿ

îäíîêðàòíîé èëè äâîéíîé.

Ïóñòü

ρ

(

a, b

) =

ρ

(

b, a

)

 ÷èñëî ðåáåð, ñîåäèíÿþùèõ âåðøèíû

a

è

b

.

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

âåðøèíå

a

:

ρ

(

a

) =

X

b

∈

V

ρ

(

a, b

)

Îáîçíà÷èì ÷åðåç

n

e

=

n

e

(

G

)

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

G

.

Òàê êàê êàæäîå ðåáðî ó÷èòûâàåòñÿ â äâóõ ñòåïåíÿõ â âåðøèíàõ

a

è

b

,

òî

2

n

e

=

P

a

∈

V

ρ

(

a

)

. Ôîðìóëà îñòàåòñÿ ñïðàâåäëèâîé è ïðè íàëè÷èè ïåòåëü,

åñëè òîëüêî â ëîêàëüíûõ ñòåïåíÿõ âåðøèí ñ÷èòàòü èõ äâàæäû. Ïîýòîìó

2

n

e

=

X

a, b

∈

V

ρ

(

a, b

)

Îòñþäà ñëåäóåò
Òåîðåìà 3.1. Â êîíå÷íîì ãðàôå ÷èñëî âåðøèí íå÷åòíîé ñòåïåíè ÷åòíî.

3.2 Î ìàøèííîì ïðåäñòàâëåíèè ãðàôà

Î÷åâèäíî, ÷òî íàèáîëåå ïîíÿòíûé è ïîëåçíûé äëÿ ÷åëîâåêà ñïîñîá ïðåä-

ñòàâëåíèÿ ãðàôà  èçîáðàæåíèå ãðàôà íà ïëîñêîñòè â âèäå òî÷åê è ñîåäè-

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

ñ ïîìîùüþ ÝÂÌ çàäà÷è, ñâÿçàííûå ñ ãðàôàìè. Âûáîð ñîîòâåòñòâóþùåé

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

âëèÿíèå íà ýôôåêòèâíîñòü àëãîðèòìîâ.

 òåîðèè ãðàôîâ êëàññè÷åñêèì ñïîñîáîì ïðåäñòàâëåíèÿ ãðàôà ñëóæèò

ìàòðèöà èíöèäåíöèé. Äëÿ ãðàôà

G

=

< V, E >

 ýòî ìàòðèöà

I

(

G

)

ñ

n

ñòðîêàìè, ñîîòâåòñòâóþùèìè âåðøèíàì,

|

V

|

=

n

, è ñ

m

ñòîëáöàìè,

|

E

|

=

m

, ñîîòâåòñòâóþùèìè ðåáðàì. Äëÿ îðèåíòèðîâàííîãî ãðàôà ñòîë-

áåö, ñîîòâåòñòâóþùèé ðåáðó

< x, y >

ñîäåðæèò

−

1

â ñòðîêå, ñîîòâåòñòâó-

þùåé âåðøèíå

x

, 1 â ñòðîêå, ñîîòâåòñòâóþùåé âåðøèíå

y

, è íóëè âî âñåõ

îñòàëüíûõ ñòðîêàõ (ïåòëþ

< x, x >

èíîãäà ïðåäñòàâëÿþò çíà÷åíèåì 2). Â

ñëó÷àå íåîðèåíòèðîâàííîãî ãðàôà ñòîëáåö, ñîîòâåòñòâóþùèé ðåáðó

{

x, y

}

,

ñîäåðæèò 1 â ñòðîêàõ, ñîîòâåòñòâóþùèõ

x

è

y

, è íóëè â îñòàëüíûõ ñòðîêàõ.

3.2. Î ÌÀØÈÍÍÎÌ ÏÐÅÄÑÒÀÂËÅÍÈÈ ÃÐÀÔÀ

87

Ïðèìåð.

Ðèñ. 3.2

Äëÿ îðèåíòèðîâàííîãî ãðàôà, èçîáðàæåííîãî íà ðèñ. 3.2, ìàòðèöà èí-

öèäåíöèé èìååò âèä:

<

1

,

2

>

<

1

,

3

>

<

3

,

2

>

<

3

,

4

>

<

4

,

3

>

Ñ àëãîðèòìè÷åñêîé òî÷êè çðåíèÿ ìàòðèöà èíöèäåíöèé ÿâëÿåòñÿ, âåðî-

ÿòíî, ñàìûì õóäøèì ñïîñîáîì ïðåäñòàâëåíèÿ ãðàôà, êîòîðûé òîëüêî ìîæ-

íî ïðåäñòàâèòü. Âî-ïåðâûõ, îí òðåáóåò m n ÿ÷ååê ïàìÿòè. Äîñòóï íåóäîáåí.

Îòâåò íà ýëåìåíòàðíûå âîïðîñû òèïà ¾ñóùåñòâóåò ëè ðåáðî

< x, y >

?¿,

¾ê êàêèì âåðøèíàì âåäóò ðåáðà èç

x

?¿, òðåáóåò ïåðåáîðà âñåõ ñòîëáöîâ

ìàòðèöû.

Áîëåå óäîáíûì ñïîñîáîì ïðåäñòàâëåíèå ãðàôà ÿâëÿåòñÿ ìàòðèöà ñìåæ-

íîñòè (âåðøèí), îïðåäåëÿåìàÿ êàê ìàòðèöà

B

=

||

b

ij

||

ðàçìåðà

n

×

n

, ãäå

b

ij

= 1

, åñëè ñóùåñòâóåò ðåáðî, âåäóùåå èç âåðøèíû

x

â âåðøèíó

y

,

b

ij

= 0

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

{

x, y

}

íåîðèåí-

òèðîâàííîãî ãðàôà èäåò êàê îò

x

ê

y

, òàê è îò

y

ê

x

, òàê ÷òî ìàòðèöà

ñìåæíîñòè òàêîãî ãðàôà âñåãäà ÿâëÿåòñÿ ñèììåòðè÷íîé. Îòâåò íà âîïðîñ

òèïà ¾

{

x, y

} ∈

E

?¿ ìîæåò áûòü ïîëó÷åí çà îäèí øàã.

88

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

Íåäîñòàòîê òàêîãî ñïîñîáà ïðåäñòàâëåíèÿ ãðàôà 

n

×

n

ÿ÷ååê çàíÿòîé

ïàìÿòè íåçàâèñèìî îò ÷èñëà ðåáåð.

Áîëåå ýêîíîìíûì â îòíîøåíèè òðåáóåìîãî îáúåìà ïàìÿòè (îñîáåííî

äëÿ íåïëîòíûõ ãðàôîâ

m

n

×

n

) ÿâëÿåòñÿ ìåòîä ïðåäñòàâëåíèÿ ãðàôà ñ

ïîìîùüþ ñïèñêà ïàð. Ïàðà

(

x, y

)

ñîîòâåòñòâóåò ðåáðó

< x, y >

, åñëè ãðàô

îðèåíòèðîâàííûé, è ðåáðó

{

x, y

}

, åñëè ãðàô íåîðèåíòèðîâàííûé. Î÷åâèä-

íî, ÷òî îáúåì ïàìÿòè â ýòîì ñëó÷àå ñîñòàâëÿåò

2

m

ÿ÷ååê. Íåóäîáñòâî 

áîëüøîå ÷èñëî øàãîâ, ïîðÿäêà m â õóäøåì ñëó÷àå, íåîáõîäèìîå äëÿ ïîëó-

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

Äëÿ ïðèâåäåííîãî íà ðèñ. 3.2. ãðàôà ñïèñîê ïàð èìååò ñëåäóþùèé âèä:

(1

,

2)

,

(3

,

2)

,

(4

,

3)

,

(1

,

3)

,

(3

,

4)

.

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

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

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

èíöèäåíòíîñòè.

Îíà ñîäåðæèò äëÿ êàæäîé âåðøèíû

v

∈

V

ñïèñîê âåðøèí

u

, òàêèõ ÷òî

< v, u >

∈

E

(èëè

{

v, u

} ∈

E

â ñëó÷àå íåîðèåíòèðîâàííîãî ãðàôà). Äëÿ

ãðàôà. ïðåäñòàâëåííîãî íà ðèñ. 3.2, ñïèñîê èíöèäåíòíîñòè èìååò ñëåäóþ-

ùèé âèä:

Âåðøèíà

Ñïèñîê èíöèäåíöèé

1

1

• →

2

• →

3

∅

2

2

∅

3

3

• →

2

• →

4

∅

4

4

• →

3

∅

Êàæäûé ýëåìåíò ñïèñêà èíöèäåíòíîñòè èìååò âèä

1

• →

ãäå

1

|{z}

Âåðøèíà

|

• →

|{z}

Ññûëêà íà ñëåäóþùèé ýëåìåíò ñïèñêà

|

3.3 Ïîèñê â ãðàôå

Áóäåì äàëåå ðàññìàòðèâàòü îðèåíòèðîâàííûå è íåîðèåíòèðîâàííûå ãðàôû

áåç ïåòåëü è êðàòíûõ ðåáåð, êîòîðûå áóäåì íàçûâàòü ïðîñòûìè. Ñóùåñòâó-

åò ìíîãî àëãîðèòìîâ íà ãðàôàõ, â îñíîâå êîòîðûõ ëåæèò ñèñòåìàòè÷åñêèé

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

89

ïåðåáîð âåðøèí ãðàôà, òàêîé, ÷òî êàæäàÿ âåðøèíà ïðîñìàòðèâàåòñÿ â òî÷-

íîñòè îäèí ðàç. Ïîýòîìó âàæíîé çàäà÷åé ÿâëÿåòñÿ íàõîæäåíèå õîðîøèõ

ìåòîäîâ ïîèñêà â ãðàôå. Âîîáùå ãîâîðÿ, ìåòîä ïîèñêà ¾õîðîøèé¿, åñëè:

1) îí ïîçâîëÿåò ëåãêî ïðèìåíèòü ýòîò ìåòîä â àëãîðèòìå ðåøåíèÿ çà-

äà÷è (¾ïîãðóçèòü¿ àëãîðèòì ðåøåíèÿ íàøåé çàäà÷è â ýòîò ìåòîä);

2) êàæäîå ðåáðî ãðàôà àíàëèçèðóåòñÿ íå áîëåå îäíîãî ðàçà (èëè, ÷òî

ñóùåñòâåííî íå ìåíÿåò ñèòóàöèè, ÷èñëî ðàç, îãðàíè÷åííîå êîíñòàíòîé).

Îïèøåì òåïåðü òàêîé ìåòîä ïîèñêà â íåîðèåíòèðîâàííîì ïðîñòîì ãðà-

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

íà ãðàôàõ. Ýòîò ìåòîä íàçûâàåòñÿ ìåòîäîì ïîèñêà â ãëóáèíó, ïî ïðè÷è-

íàì, êîòîðûå âñêîðå ñòàíóò ÿñíûìè.

3.3.1 Ïîèñê â ãëóáèíó â ãðàôå

Îáùàÿ èäåÿ ýòîãî ìåòîäà ñîñòîèò â ñëåäóþùåì. Ìû íà÷èíàåì ïîèñê ñ íåêî-

òîðîé ôèêñèðîâàííîé âåðøèíû

v

0

. Çàòåì âûáèðàåì ïðîèçâîëüíóþ âåðøè-

íó

u

, ñìåæíóþ ñ

v

0

((

v

0

, u

)

∈

E

)

, è ïîâòîðÿåì ïðîöåññ îò

u

. Â îáùåì ñëó÷àå

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

v

. Åñëè ñóùåñòâóåò íîâàÿ (åùå

íåïðîñìîòðåííàÿ) âåðøèíà

u

,

(

v, u

)

∈

E

, òî ìû ðàññìàòðèâàåì ýòó âåðøè-

íó (îíà ïåðåñòàåò áûòü íîâîé) è, íà÷èíàÿ ñ íåå, ïðîäîëæàåì ïîèñê. Åñëè

æå íå ñóùåñòâóåò íè îäíîé íîâîé âåðøèíû, ñìåæíîé ñ

v

, òî ìû ãîâîðèì.

÷òî âåðøèíà

v

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

ïàëè â

v

, è ïðîäîëæàåì ïðîöåññ (åñëè

v

=

v

0

, òî ïîèñê çàêîí÷åí). Òàêèì

îáðàçîì, ïîèñê â ãëóáèíó èç âåðøèíû

v

îñíîâûâàåòñÿ íà ïîèñêå â ãëóáèíó

èç âñåõ íîâûõ âåðøèí, ñìåæíûõ ñ

v

.

Ýòîò ïðîöåññ ïîèñêà èç âåðøèíû

v

äëÿ íåîðèåíòèðîâàííîãî ïðîñòîãî

ãðàôà, çàäàííîãî ñïèñêîì èíöèäåíòíîñòè ÑÏÈÑÎÊ (ÑÏÈÑÎÊ[

v

]  ñïèñîê

âåðøèí, ñìåæíûõ (èíöèäåíòíûõ) ñ âåðøèíîé

v

) ëåãêî îïèñàòü ñ ïîìîùüþ

ñëåäóþùåé ðåêóðñèâíîé ïðîöåäóðû:

1:

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

G

(

v

)

{ïîèñê â ãëóáè-

íó èç âåðøèíû

v

; ïåðåìåííûå ÍÎÂÛÉ, ÇÀÏÈÑÜ  ãëîáàëüíûå}

2:

begin

3:

ðàññìîòðåòü

v

;

4:

ÍÎÂÛÉ

[

v

] :=

ëîæü;

5:

for

u

∈

ÇÀÏÈÑÜ

[

v

]

do

6:

if ÍÎÂÛÉ

[

u

]

then

7:

ÏÎÈÑÊ_Â_ÃËÓÁÈÍÓ_Â_ÃÐÀÔÅ_

G

(

u

)

;

8:

end {âåðøèíà

v

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

90

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

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

âàííîì ïðîñòîì ãðàôå ïðîâîäèòñÿ ïî ñëåäóþùåìó àëãîðèòìó:

1:

begin

2:

for

v

∈

V

do

3:

ÍÎÂÛÉ

[

v

] :=

èñòèíà; {èíèöèàëèçàöèÿ}

4:

for

v

∈

V

do

5:

if ÍÎÂÛÉ

[

v

]

then

6:

ÏÎÈÑÊ_Â_ÃËÓÁÈÍÓ_Â_ÃÐÀÔÅ_

G

(

v

)

;

7:

end

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

â òî÷íîñòè îäèí ðàç è åãî ñëîæíîñòü ïîðÿäêà

O

(

n

+

m

)

. Îòìåòèì ñíà÷à-

ëà, ÷òî âûçîâ ÏÎÈÑÊ_Â_ÃËÓÁÈÍÓ_Â_ÃÐÀÔÅ_

G

(

v

)

âëå÷åò çà ñîáîé

ïðîñìîòð âñåõ âåðøèí ñâÿçíîé êîìïîíåíòû ãðàôà, ñîäåðæàùåé

v

(åñëè

ÍÎÂÛÉ

[

u

] =

èñòèíà äëÿ êàæäîé âåðøèíû

u

ýòîé êîìïîíåíòû). Ýòî íåïî-

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

ÃÐÀÔÅ_

G

(

v

)

: ïîñëå ïîñåùåíèÿ âåðøèíû (ñòðîêà 3) ñëåäóåò âûçîâ ïðî-

öåäóðû äëÿ âñåõ åå íîâûõ ñîñåäåé. Îòìåòèì òàêæå, ÷òî êàæäàÿ âåðøèíà

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

æåò òîëüêî âåðøèíà

v

, äëÿ êîòîðîé ÍÎÂÛÉ

[

v

] =

èñòèíà, ñðàçó æå ïîñëå

ïîñåùåíèÿ ýòîé âåðøèíû èñïîëíÿåòñÿ ïðèñâàèâàíèå ÍÎÂÛÉ

[

v

] :=

ëîæü

(ñòðîêà 4 ïðîöåäóðû).

Ðèñ. 3.3

Íà ðèñ. 3.3. ïîêàçàí ãðàô, âåðøèíû êîòîðîãî ïåðåíóìåðîâàíû (íîìåðà

â ñêîáêàõ) â ñîîòâåòñòâèè ñ òåì ïîðÿäêîì, â êîòîðîì îíè ïðîñìàòðèâàþòñÿ

â ïðîöåññå ïîèñêà â ãëóáèíó (ìû îòîæäåñòâëÿåì âåðøèíû ãðàôà ñ ÷èñëàìè

1

, . . . ,

13

è ïîëàãàåì, ÷òî â ñïèñêå ÑÏÈÑÎÊ

[

v

]

âåðøèíû óïîðÿäî÷åíû ïî

âîçðàñòàíèþ).