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

3.6. ÄÅÐÅÂÜß

101

1:

procedure ÊÀÐÊÀÑ_ÃËÓÁÈÍÀ(

v

) {ïîèñê â ãëóáèíó èç âåðøèíû

v

,

ñîåäèíåííûé ñ íàõîæäåíèåì ðåáðà äåðåâà; ïåðåìåííûå ÍÎÂÛÉ, ÇÀ-

ÏÈÑÜ,

T

 ãëîáàëüíûå}

2:

begin

3:

ÍÎÂÛÉ

[

v

]

: = ëîæü;

4:

for

u

∈

ÇÀÏÈÑÜ

[

v

]

do

5:

if ÍÎÂÛÉ

[

u

]

then

6:

(

u, v

)

 íîâàÿ âåòâü;

7:

begin

8:

T

:=

T

∪

(

v, u

)

;

9:

ÊÀÐÊÀÑ_ÃËÓÁÈÍÀ

(

u

)

;

10:

end

11:

end {âåðøèíà v èñïîëüçîâàíà};

12:

begin {ãëàâíàÿ ïðîãðàììà}

13:

for

u

∈

V

do

14:

ÍÎÂÛÉ

[

u

]

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

15:

T

:=

∅

; {

T

 ìíîæåñòâî íàéäåííûõ ê ýòîìó âðåìåíè ð¼áåð êàðêàñà}

16:

ÊÀÐÊÀÑ_ÃËÓÁÈÍÀ

(

r

)

{

r

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

17:

end

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

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

òðè ôàêòà. Âî-ïåðâûõ, â ìîìåíò äîáàâëåíèÿ ê ìíîæåñòâó

T

íîâîãî ðåáðà

(

v, u

)

â ñòðîêå 8 â

< V, T >

ñóùåñòâóåò ïóòü èç

r

â

v

(ýòîò ôàêò ëåã-

êî äîêàçûâàåòñÿ ïî èíäóêöèè). Òàêèì îáðàçîì, àëãîðèòì ñòðîèò ñâÿçíûé

ãðàô. Âî-âòîðûõ, êàæäîå íîâîå ðåáðî

(

v, u

)

, äîáàâëÿåìîå êî ìíîæåñòâó

T

, ñîåäèíÿåò óæå ðàññìîòðåííóþ âåðøèíó

v

(ò.å. ÍÎÂÛÉ

[

v

]

= ëîæü) ñ

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

u

. Îòñþäà ñëåäóåò, ÷òî ïîñòðîåííûé ãðàô

< V, T >

íå

ñîäåðæèò öèêëîâ. Äåéñòâèòåëüíî, ïîñëåäíåå ðåáðî, ¾çàìûêàþùåå¿ öèêë,

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

íåö, â-òðåòüèõ, èç ñâîéñòâà ïîèñêà â ãëóáèíó ñëåäóåò, ÷òî ïðîöåäóðà ÊÀÐ-

ÊÀÑ_ÃËÓÁÈÍÀ ïðîñìàòðèâàåò âñå âåðøèíû ñâÿçíîãî ãðàôà. Ñëåäîâà-

òåëüíî, ãðàô

< V, T >

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

äåðåâî ãðàôà

G

. Âû÷èñëèòåëüíàÿ ñëîæíîñòü àëãîðèòìà åñòü, î÷åâèäíî,

O

(

n

+

m

)

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

Àíàëîãè÷íî âûãëÿäèò ïðîöåäóðà ïîñòðîåíèÿ îñòîâíîãî äåðåâà ìåòîäîì

ïîèñêà â øèðèíó.

102

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

Àëãîðèòì ïîñòðîåíèÿ îñòîâíîãî äåðåâà ìåòîäîì ïîèñêà â øè-

ðèíó.
Âõîäíûå äàííûå: ñâÿçíûé ãðàô

G

=

< V, E >

, çàäàííûé ñïèñêàìè èí-

öèäåíòíîñòè ÇÀÏÈÑÜ

[

v

]

,

v

∈

V

.

Ðåçóëüòàò: êàðêàñ

< V, T >

ãðàôà

G

.

1:

begin

2:

for

u

∈

V

do

3:

ÍÎÂÛÉ

[

u

] :=

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

4:

T

:=

∅

;

{

T

 ìíîæåñòâî íàéäåííûõ ê ýòîìó âðåìåíè ðåáåð êàðêàñà}

5:

Î×ÅÐÅÄÜ

:=

∅

;

6:

Î×ÅÐÅÄÜ

⇐

r

;

7:

ÍÎÂÛÉ

[

r

] :=

ëîæü; {

r

 êîðåíü êàðêàñà}

8:

while Î×ÅÐÅÄÜ

6

=

∅

do

9:

begin

10:

p

⇐

Î×ÅÐÅÄÜ;

11:

for

u

∈

ÇÀÏÈÑÜ

[

v

]

do

12:

if ÍÎÂÛÉ

[

u

]

then

13:

begin

14:

Î×ÅÐÅÄÜ

⇐

u

;

15:

ÍÎÂÛÉ

[

u

] :=

ëîæü;

16:

T

:=

T

∪

(

v, u

)

;

17:

end

18:

end

19:

end

Ðàññóæäåíèÿìè, àíàëîãè÷íûìè ïðîâåäåííûì äëÿ àëãîðèòìà

ÊÀÐÊÀÑ_ÃËÓÁÈÍÀ, ìîæíî ïîêàçàòü, ÷òî äàííûé àëãîðèòì êîððåêòíî

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

O

(

n

+

m

)

øàãîâ.

Íà ñëåäóþùåì ðèñóíêå äàí ïðèìåð îñòîâíîãî äåðåâà äëÿ ãðàôà, ïî-

ñòðîåííîãî ìåòîäîì ïîèñêà â øèðèíó (ñëåâà) è â ãëóáèíó (ñïðàâà).

3.6. ÄÅÐÅÂÜß

103

Êàæäîå îñòîâíîå äåðåâî, ïîñòðîåííîå ñ ïîìîùüþ ìåòîäà ïîèñêà â ãëóáèíó,

èìååò ëþáîïûòíîå ñâîéñòâî, êîòîðîå ñåé÷àñ áóäåò îïèñàíî.

Âåðøèíó

r

, èç êîòîðîé íà÷èíàåòñÿ ïîèñê, íàçîâåì êîðíåì îñòîâíîãî

äåðåâà. Äëÿ äâóõ ðàçëè÷íûõ âåðøèí

v

è

u

äåðåâà

< V, T >

áóäåì ãîâî-

ðèòü, ÷òî

u

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

v

, åñëè

v

ëåæèò íà ïóòè (â äåðåâå

< V, T >

) èç âåðøèíû

u

â âåðøèíó

v

.

Òåîðåìà 3.9. Ïóñòü

< V, T >

 îñòîâíîå äåðåâî ñâÿçíîãî íåîðèåí-

òèðîâàííîãî ãðàôà

G

=

< V, E >

, ïîñòðîåííîå ñ ïîìîùüþ àëãîðèòìà

ÊÀÐÊÀÑ_ÃËÓÁÈÍÀ, è ïóñòü

(

u, v

)

∈

E

. Òîãäà ëèáî

u

 ïîòîìîê

v

,

ëèáî

v

 ïîòîìîê

u

.

Äîêàçàòåëüñòâî. Ïðåäïîëîæèì áåç îãðàíè÷åíèÿ îáùíîñòè, ÷òî âåðøèíà

v

áóäåò ïðîñìîòðåíà ðàíüøå, ÷åì

u

. Ðàññìîòðèì ïðîöåññ ïîèñêà â ãëóáè-

íó, íà÷èíàÿ ñ âåðøèíû

v

. Î÷åâèäíî, ÷òî ïî îêîí÷àíèè åãî äîëæíî áûòü

ÍÎÂÛÉ

[

u

] =

ëîæü, èáî

(

v, u

)

 ðåáðî. Íî ýòî îçíà÷àåò, ÷òî ðåáðà, äî-

áàâëåííûå âî ìíîæåñòâî

T

â òå÷åíèå ýòîãî ïðîöåññà, ñîäåðæàò ïóòü èç

v

â

u

, îòêóäà ñëåäóåò, ÷òî

v

ëåæèò íà ïóòè èç

u

â êîðåíü, ïîñêîëüêó â äåðåâå

ñóùåñòâóåò â òî÷íîñòè îäèí ïóòü èç ïðîèçâîëüíîé âåðøèíû ê êîðíþ.

Ðàññóæäåíèÿ, ïðîâåäåííûå â ïðåäûäóùåì ðàçäåëå, íåïîñðåäñòâåííî ïðè-

âîäÿò ê ñëåäóþùåé òåîðåìå.

Òåîðåìà 3.10. Ïóñòü

< V, T >

 îñòîâíîå äåðåâî ñâÿçíîãî íåîðèåíòè-

ðîâàííîãî ãðàôà

G

=

< V, E >

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

â øèðèíó. Òîãäà ïóòü â

< V, T >

èç ïðîèçâîëüíîé âåðøèíû

v

äî êîðíÿ

r

ÿâëÿåòñÿ êðàò÷àéøèì ïóòåì èç

v

â

r

â ãðàôå

G

.

Äàëåå îñîáî îáñóæäàåòñÿ áîëåå îáùàÿ çàäà÷à îòûñêàíèÿ êðàò÷àéøèõ

ïóòåé â ãðàôå, ðåáðàì êîòîðîãî ïðèïèñàíû ¾äëèíû¿ (âåñà), íå îáÿçàòåëüíî

ðàâíûå åäèíèöå.

104

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

3.7 Ýéëåðîâû ïóòè è öèêëû

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

ðàñïîëîæåíèÿ ñåìè ìîñòîâ â Ê¼íèãñáåðãå (íûíå ã. Êàëèíèíãðàä) ïðèâåäåí

íà ðèñ. 3.5.

Ðèñ. 3.5

Çàäà÷à ñîñòîèò â òîì, ÷òîáû ïðîéòè êàæäûé ìîñò ïî îäíîìó ðàçó è âåð-

íóòüñÿ â èñõîäíóþ òî÷êó Ñ. Òàê êàê ñóùåñòâåííû òîëüêî ïåðåõîäû ÷åðåç

ìîñòû, ïëàí ãîðîäà ìîæíî ñâåñòè ê èçîáðàæåíèþ ãðàôà, â êîòîðîì ðåáðà

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

Î÷åâèäíî, íå ñóùåñòâóåò öèêëè÷åñêèõ îáõîäîâ, ïðîõîäÿùèõ ïî âñåì

ðåáðàì ïî îäíîìó ðàçó.

Ðàçâëå÷åíèÿ, â êîòîðûõ òðåáóåòñÿ îáðèñîâàòü íåêîòîðóþ ôèãóðó, íå

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

Ñ÷èòàåòñÿ, ÷òî ôèãóðà, íàçûâàåìàÿ ñàáëÿìè Ìàãîìåòà, èìååò àðàáñêîå

ïðîèñõîæäåíèå.

Ýéëåð îáðàòèëñÿ ê îáùåé çàäà÷å, êàñàþùåéñÿ ãðàôîâ: â êàêèõ ñëó÷àÿõ â

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

âîâàëî áû îäèí ðàç?

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

105

Îïðåäåëåíèå. Ýéëåðîâûì ïóòåì â ãðàôå

G

=

< V, E >

íàçûâàåòñÿ

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

îäèí ðàç, ò.å. ïóòü

S

=

< v

1

, . . . , v

m

+1

òàêîé, ÷òî êàæäîå ðåáðî

e

∈

E

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

v

1

, . . . , v

m

+1

â òî÷íîñòè îäèí ðàç êàê

e

=

{

v

i

, v

i

+1

}

äëÿ íåêîòîðîãî

i

. Åñëè

v

1

=

v

m

+1

, òî òàêîé ïóòü íàçûâàåòñÿ

ýéëåðîâûì öèêëîì.

Òåîðåìà 3.11. Ýéëåðîâ ïóòü â íåîðèåíòèðîâàííîì ïðîñòîì ãðàôå ñóùå-

ñòâóåò òîãäà è òîëüêî òîãäà, êîãäà ãðàô ñâÿçíûé è ñîäåðæèò íå áîëåå,

÷åì äâå âåðøèíû íå÷åòíîé ñòåïåíè.

Åñëè â ñâÿçíîì ãðàôå íåò âåðøèí íå÷åòíîé ñòåïåíè, òî êàæäûé ýéëå-

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

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

u

è

v

åäèíñòâåííûå âåðøèíû íå÷åòíîé ñòåïåíè â ñâÿçíîì ãðàôå

G

=

< V, T >

è

îáðàçóåì ãðàô

G

0

äîáàâëåíèåì äîïîëíèòåëüíîé âåðøèíû

t

è ðåáåð

{

u, v

}

è

{

v, t

}

(èëè ïðîñòî äîáàâëåíèåì ðåáðà

{

u, v

}

, åñëè

{

u, v

}

/

∈

E

). Òîãäà

G

0

 ñâÿçíûé ãðàô áåç âåðøèí íå÷åòíîé ñòåïåíè, à ýéëåðîâû ïóòè â

G

áóäóò â î÷åâèäíîì âçàèìíî îäíîçíà÷íîì ñîîòâåòñòâèè ñ ýéëåðîâûìè öèê-

ëàìè â

G

0

. Â ñèëó ýòîãî ìû áóäåì çàíèìàòüñÿ òîëüêî ýéëåðîâûìè öèêëàìè

è ïåðåôîðìóëèðóåì òåîðåìó.

Òåîðåìà 3.12. Êîíå÷íûé ãðàô

G

=

< V, E >

ñîäåðæèò ýéëåðîâ öèêë

òîãäà è òîëüêî òîãäà, êîãäà

1.

G

 ñâÿçåí.

2. Âñå ñòåïåíè åãî âåðøèí ÷åòíûå.

Äîêàçàòåëüñòâî. Óñëîâèå 1, î÷åâèäíî, íåîáõîäèìî. Äàëåå, êàæäûé ðàç,

êîãäà ýéëåðîâ öèêë ïðîõîäèò ÷åðåç êàêóþ-òî âåðøèíó, îí äîëæåí âîéòè â

íåå ïî îäíîìó ðåáðó è âûéòè ïî äðóãîìó; ïîýòîìó óñëîâèå 2 òàêæå íåîá-

õîäèìî.

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

ïðîèçâîëüíîé âåðøèíå

a

ãðàôà

G

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

ìîæíî, âñ¼ âðåìÿ ÷åðåç íîâûå ð¼áðà. Òàê êàê ñòåïåíè âñåõ âåðøèí ÷åòíû,

ýòîò ïðîöåññ ìîæåò çàêîí÷èòñÿ òîëüêî â âåðøèíå

a

.

Åñëè ñîäåðæèò íå âñå ð¼áðà ãðàôà

G

, òî óäàëèì èç

G

÷àñòü , ñîñòîÿùóþ

èç ðåáåð ýòîãî öèêëà.

Ãðàôû è

G

èìåþò ÷åòíûå ñòåïåíè âåðøèí, òî æå áóäåò ñïðàâåäëèâî è

äëÿ îñòàþùåãîñÿ ãðàôà

P

.