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

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

111

Èç äâóõ äîêàçàííûõ óòâåðæäåíèé ñëåäóåò

Òåîðåìà 3.15. Â ñâÿçíîì ãðàôå ëèáî èìååòñÿ ãàìèëüòîíîâ öèêë, ëèáî

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

k

≥

ρ

(

a

0

) +

ρ

(

a

k

)

.

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

k

≥

min(

ρ

(

a

0

) +

ρ

(

a

k

))

äëÿ âñåõ

ïàð âåðøèí

a

0

è

a

k

, ïðè÷åì ìîæíî äàæå îãðàíè÷èòüñÿ òåìè ïàðàìè, äëÿ

êîòîðûõ íåò ðåáðà

(

a

0

, a

i

)

Îòñþäà ñëåäóåò

Òåîðåìà 3.16. Â ãðàôå áåç ãàìèëüòîíîâûõ öèêëîâ äëèíà åãî ìàêñèìàëü-

íûõ ïðîñòûõ ïóòåé

k

óäîâëåòâîðÿåò íåðàâåíñòâó

k

≥

ρ

1

+

ρ

2

, ãäå

ρ

1

è

ρ

2

 äâå íàèìåíüøèå ñòåïåíè âåðøèí.

 òåîðåìå 3.16 ìîæíî íå ïðåäïîëàãàòü, ÷òî ãðàô ñâÿçåí.

Îòìåòèì åùå, ÷òî â ãðàôå ñ

n

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

èìååò äëèíó, íå ïðåâûøàþùóþ

n

−

1

.

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

òåîðåìà.

Òåîðåìà 3.17. Åñëè â ãðàôå

G

ñ

n

âåðøèíàìè äëÿ ëþáîé ïàðû âåðøèí

a

0

è

a

k

èìååò ìåñòî ñîîòíîøåíèå

ρ

(

a

0

) +

ρ

(

a

k

)

≥

n

−

1

, òî ãðàô

G

èìååò

ãàìèëüòîíîâ ïóòü.

Åñëè

ρ

(

a

0

) +

ρ

(

a

k

)

≥

n

, òî

G

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

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

n

âåð-

øèíàìè èìååò ãàìèëüòîíîâ öèêë, åñëè äëÿ êàæäîé åãî âåðøèíû

ρ

(

a

)

≥

1

2

n.

Îïðåäåëåíèå. Áóäåì íàçûâàòü íåîðèåíòèðîâàííûé ïðîñòîé ãðàô

k

-

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

íåñâÿçíîìó èëè îäíîâåðøèííîìó ãðàôó, ðàâíî

k

.

Ñëó÷àè, êîãäà

k

= 2

èëè

k

= 3

â òåîðèè ãðàôîâ èìåþò îñîáóþ ðîëü. Òà-

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

â ÷àñòíîñòè ðÿä çàäà÷ äîñòàòî÷íî óìåòü ðåøàòü äëÿ 2-ñâÿçíûõ êîìïîíåíò;

êðîìå òîãî, ïðè

k

= 3

è, îñîáåííî ïðè

k

= 2

óäàåòñÿ äàòü äîñòàòî÷íî

îáîçðèìîå îïèñàíèå ñîîòâåòñòâóþùèõ ãðàôîâ.

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

âûòåêàþùèå íåïîñðåäñòâåííî èç îïðåäåëåíèÿ:

112

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

1. Ñòåïåíè âåðøèí äâóñâÿçíîãî ãðàôà áîëüøå åäèíèöû.

2. Åñëè ãðàôû

G

1

è

G

2

2-ñâÿçíû è èìåþò íå ìåíåå äâóõ îáùèõ âåðøèí,

òî ãðàô

G

1

∪

G

2

òàêæå 2-ñâÿçåí.

3. Íàçîâåì òî÷êîé ñî÷ëåíåíèÿ ãðàôà òàêóþ åãî âåðøèíó, óäàëåíèå êîòî-

ðîé ïðèâîäèò ê ãðàôó ñ áîëüøèì ÷èñëîì êîìïîíåíò ñâÿçíîñòè; åñëè

âåðøèíà

v

ãðàôà íå ÿâëÿåòñÿ òî÷êîé ñî÷ëåíåíèÿ ãðàôà, òî ëþáûå

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

v

; â ÷àñòíîñòè, â

2-ñâÿçíîì ãðàôå äëÿ ëþáûõ òðåõ íåñîâïàäàþùèõ âåðøèí

a

,

b

,

v

èìå-

åòñÿ ïóòü èç âåðøèíû

a

â âåðøèíó

b

, íå ïðîõîäÿùèé ÷åðåç âåðøèíó

v

.

Áóäåì â äàëüíåéøåì ãðàôû, èìåþùèå ãàìèëüòîíîâ öèêë, íàçûâàòü ãà-

ìèëüòîíîâûìè. Ãàìèëüòîíîâ ãðàô äîëæåí áûòü äâóñâÿçíûì. Îäíàêî ïðè-

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

ãàìèëüòîíîâîñòè ãðàôà äâóñâÿçíîñòè íåäîñòàòî÷íî.

Ðèñ. 3.6

Îïðåäåëåíèå. Ëþáîé ãðàô, ñîäåðæàùèé äâå âåðøèíû ñòåïåíè 3, ñî-

åäèíåííûõ òðåìÿ ïðîñòûìè ïîïàðíî íåïåðåñåêàþùèìèñÿ ïóòÿìè äëèíû

íå ìåíåå äâóõ, íàçûâàåòñÿ òýòà-ãðàôîì. Ïðèìåð òýòà-ãðàôà ïðèâåäåí íà

ðèñ. 3.6.

Äàëåå áóäåò äîêàçàíà òåîðåìà î òîì, ÷òî êàæäûé íåãàìèëüòîíîâ äâó-

ñâÿçíûé ãðàô ñîäåðæèò òýòà-ïîäãðàô. Íî ïðåæäå ÷åì ïåðåõîäèòü ê äîêà-

çàòåëüñòâó ýòîãî ðåçóëüòàòà, îñòàíîâèìñÿ íà íåîáõîäèìîì äëÿ íåãî óòâåð-

æäåíèè îòíîñèòåëüíî äâóñâÿçíûõ ãðàôîâ, ïðåäñòàâëÿþùåì è ñàìîñòîÿ-

òåëüíûé èíòåðåñ.

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

G

=

< V, E >

 ñâÿçíûé ãðàô è êîëè÷åñòâî åãî

âåðøèí

|

V

|

>

2

. Òîãäà ñëåäóþùèå óòâåðæäåíèÿ ýêâèâàëåíòíû:

1. Ãðàô 2-ñâÿçåí.

2. Ëþáûå äâå âåðøèíû ãðàôà ïðèíàäëåæàò ïðîñòîìó öèêëó.

3. Ëþáàÿ âåðøèíà è ëþáîå ðåáðî ïðèíàäëåæàò ïðîñòîìó öèêëó.

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

113

4. Ëþáûå äâà ðåáðà ïðèíàäëåæàò ïðîñòîìó öèêëó.

5. Äëÿ ëþáûõ äâóõ âåðøèí

a

è

b

è ëþáîãî ðåáðà

e

ñóùåñòâóåò ïðîñòîé

(

a, b

)

-ïóòü (ïóòü ñ íà÷àëüíîé âåðøèíîé

a

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

b

),

ñîäåðæàùèé

e

;

6. Äëÿ ëþáûõ òðåõ âåðøèí

a

,

b

,

c

ñóùåñòâóåò ïðîñòîé

(

a, b

)

-ïóòü,

ïðîõîäÿùèé ÷åðåç .

Äîêàçàòåëüñòâî.

1

⇒

2

.

Ïóñòü

a

è

b

 äâå âåðøèíû ãðàôà

G

. Ðàññìîòðèì

ìíîæåñòâî âñåõ ïðîñòûõ öèêëîâ ãðàôà

G

, ñîäåðæàùèõ âåðøèíó

a

. Îáî-

çíà÷èì ÷åðåç

U

ìíîæåñòâî âñåõ âåðøèí, âõîäÿùèõ â ýòè öèêëû. ßñíî, ÷òî

U

6

=

∅

. Äåéñòâèòåëüíî, ïðîñòîé öèêë, ñîäåðæàùèé

a

, ìîæíî ïîëó÷èòü,

îáúåäèíèâ äâà ðåáðà

(

a, x

)

è

(

a, y

) (

x

6

=

y

)

è ïðîñòîé

(

x, y

)

-ïóòü, íå ïðî-

õîäÿùèé ÷åðåç

a

(ñóùåñòâóþùèé ñîãëàñíî ñâîéñòâó 3 äâóñâÿçíûõ ãðàôîâ).

Ïðåäïîëîæèì, ÷òî

b

6

=

U

, è ïîëîæèì

U

=

V

\

U

. Ïîñêîëüêó ãðàô

G

ñâÿçåí,

òî â íåì íàéäåòñÿ òàêîå ðåáðî

(

x, t

)

, ÷òî

x

∈

U, t

∈

U

(ðèñ. 3.7). Ïóñòü

S

 ïðîñòîé öèêë, ñîäåðæàùèé

a

è

x

. Òàê êàê

G

-äâóñâÿçíûé ãðàô, òî â

íåì èìååòñÿ ïðîñòîé

(

a, t

)

-ïóòü

P

, íå ñîäåðæàùèé

x

. Ïóñòü

v

 ïåðâàÿ,

ñ÷èòàÿ îò

t

, âåðøèíà, âõîäÿùàÿ â

S

, ò.å.

(

t, v

)

-ïîäïóòü ïóòè

P

íå èìååò

ñ

S

îáùèõ âåðøèí, îòëè÷íûõ îò

v

. Òåïåðü ëåãêî ïîñòðîèòü ïðîñòîé öèêë,

ñîäåðæàùèé

v

è

t

. Îí ïîëó÷àåòñÿ îáúåäèíåíèåì

(

v, z

)

- ïóòè, ïðîõîäÿùåãî

÷åðåç

a

è ÿâëÿþùåãîñÿ ÷àñòüþ

S

, ñ ðåáðîì

(

z, t

)

è

(

t, v

)

-÷àñòüþ ïóòè

P

(íà ðèñ. 3.7 ýòîò öèêë ïîêàçàí ïóíêòèðíîé ëèíèåé). Ñëåäîâàòåëüíî,

t

∈

U

,

íî ýòî ïðîòèâîðå÷èò âûáîðó ðåáðà

(

x, t

)

. Òàêèì îáðàçîì,

U

=

∅

, ò.å.

a

è

b

ïðèíàäëåæàò îäíîìó îáùåìó ïðîñòîìó öèêëó.

Ðèñ. 3.7

114

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

2

⇒

3

.

Ïóñòü

a

 âåðøèíà è

(

x, t

)

 ðåáðî ãðàôà. Ïî óñëîâèþ

G

cîäåð-

æèò öèêë

S

, ïðîõîäÿùèé ÷åðåç âåðøèíû

a

è

x

. Íå òåðÿÿ îáùíîñòè áóäåì

ñ÷èòàòü, ÷òî ðåáðî

(

x, t

)

/

∈

S

. Åñëè ïðè ýòîì îêàæåòñÿ, ÷òî

S

ïðîõîäèò

÷åðåç âåðøèíó

t

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

S

íå ïðîõîäèò ÷åðåç âåðøèíó

t

. Òîãäà ðàññìîòðèì ïðîñòîé öèêë, ïðîõî-

äÿùèé ÷åðåç âåðøèíû

t

è

a

. Òàêîé öèêë, ïî óñëîâèþ, ñóùåñòâóåò. ×àñòüþ

ýòîãî öèêëà ÿâëÿåòñÿ ïðîñòîé ïóòü

P

, ñîåäèíÿþùèé

t

ñ íåêîòîðîé âåðøè-

íîé

v

∈

S

. Ïóòü

P

ìîæíî âûáðàòü òàê, ÷òîáû ïóòè

P

è

S

ïåðåñåêàëèñü

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

v

. Èñêîìûé öèêë ñòðîèòñÿ òî÷íî òàê æå, êàê â ïðåäû-

äóùåì ïóíêòå.

3

⇒

4

.

Ïóñòü

(

a, b

)

è

(

t, z

)

 äâà ðåáðà ãðàôà

G

. Ïî óñëîâèþ

G

èìååò

ïðîñòûå öèêëû

S

è

S

0

, ïåðâûé èç êîòîðûõ ñîäåðæèò ðåáðî

(

a, b

)

è âåðøèíó

z

, à âòîðîé 

(

a, b

)

è

t

. Äàëåå èñêîìûé öèêë ñòðîèòñÿ òî÷íî òàê æå, êàê

â ïðåäûäóùèõ ïóíêòàõ.

4

⇒

5

.

Ïóñòü

a

è

b

 âåðøèíû ãðàôà

G

, è

(

t, z

)

 åãî ðåáðî. Áóäó÷è

ñâÿçíûì, ãðàô

G

ñîäåðæèò ïðîñòîé ïóòü

P

= (

a, x, . . . , b

)

. Ñîãëàñíî

óòâåðæäåíèþ 4, â ãðàôå

G

åñòü ïðîñòîé öèêë

S

, ñîäåðæàùèé ðåáðà

(

a, x

)

è

(

t, z

)

. Ëåãêî âèäåòü, ÷òî â îáúåäèíåíèè

S

∪

P

èìååòñÿ òðåáóåìûé ïóòü.

5

⇒

6

.

Ïóñòü

a

,

b

,

c

 âåðøèíû ãðàôà

G

,

(

c, d

)

 åãî ðåáðî. Ïî óñëî-

âèþ â ãðàôå èìååòñÿ ïðîñòîé

(

a, b

)

 ïóòü, ïðîõîäÿùèé ÷åðåç

(

c, d

)

, è

ñëåäîâàòåëüíî, ñîäåðæàùèé

c

.

6

⇒

1

.

Ïóñòü

v

 âåðøèíà ãðàôà

G

. Ïîêàæåì, ÷òî ãðàô

G

ñ óäàëåííîé

âåðøèíîé

v

(ãðàô

G

\ {

v

}

)  ñâÿçåí, ò.å. ëþáàÿ ïàðà

a

,

b

åãî âåðøèí ñîåäè-

íåíà ïóòåì. Äåéñòâèòåëüíî, ñîãëàñíî óòâåðæäåíèþ 6 â ãðàôå

G

èìååòñÿ

ïðîñòîé

(

v, b

)

-ïóòü, ïðîõîäÿùèé ÷åðåç âåðøèíó

a

. Ýòîò ïóòü ñîäåðæèò

(

a, b

)

-ïîäïóòü, êîòîðûé, î÷åâèäíî, íå ïðîõîäèò ÷åðåç

v

è, ñëåäîâàòåëüíî,

ÿâëÿåòñÿ

(

a, b

)

-ïóòåì è â ãðàôå

G

\ {

v

}

.

Òåîðåìà 3.19. Êàæäûé íåãàìèëüòîíîâ äâóñâÿçíûé ãðàô ñîäåðæèò òýòà-

ïîäãðàô.

Äîêàçàòåëüñòâî. Ïóñòü

G

=

< V, E >

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

è

C

 ïðîñòîé öèêë ìàêñèìàëüíîé äëèíû â ýòîì ãðàôå. Ïî óñëîâèþ òåî-

ðåìû ìíîæåñòâî

S

âåðøèí ãðàôà

G

, íå ïðèíàäëåæàùèõ öèêëó

S

, íåïóñòî.

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

êîòîðûõ ìåíüøå ïÿòè, íåò íåãàìèëüòîíîâûõ, ïîýòîìó

|

V

| ≥

5

. Èç äâóñâÿç-

íîñòè ãðàôà è òåîðåìû 3.18 ñëåäóåò, ÷òî êîëè÷åñòâî âåðøèí â öèêëå

C

íå

ìåíåå ÷åòûðåõ.

Ïóñòü

(

x, v

)

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

G

, ÷òî

x

∈

C

,

v

∈

S

,

a

è

b

 âåðøèíû

öèêëà

C

, ñìåæíûå ñ

x

(ñì. ðèñ. 3.8). Ïîñêîëüêó  ìàêñèìàëüíûé öèêë, òî

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

115

âåðøèíà

v

íå ñìåæíà íè ñ

a

, íè ñ

b

(èíà÷å ìîæíî áûëî áû ïîñòðîèòü áîëü-

øèé öèêë). Ðàññìîòðèì òåïåðü ãðàô

G

\ {

x

}

, êîòîðûé, î÷åâèäíî, ñâÿçåí. Â

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

y

∈

C

, èìååòñÿ

(

v, y

)

-ïóòü. Âûáåðåì èõ

ýòèõ ïóòåé êðàò÷àéøèé

(

v, y

∗

)

-ïóòü

P

∗

. Ó÷èòûâàÿ, ÷òî

C

 ìàêñèìàëüíûé

öèêë, èìååì

y

∗

6

=

a

,

y

∗

6

=

b

. Êðîìå òîãî,

P

∗

íå ñîäåðæèò âåðøèí öèêëà

C

,

îòëè÷íûõ îò

y

∗

, òàê êàê èíà÷å ìîæíî áûëî áû ïîñòðîèòü áîëåå êîðîòêóþ

öåïü. Îáúåäèíèâ öèêë è ïóòü

P

∗

, ïîëó÷èì èñêîìûé òýòà-ïîäãðàô.

Ðèñ. 3.8

Îïðåäåëåíèå. Ñòåïåííîé ïîñëåäîâàòåëüíîñòüþ ãðàôà áóäåì íàçû-

âàòü ïîñëåäîâàòåëüíîñòü ñòåïåíåé åãî âåðøèí.

Òåîðåìà 3.20. Ãðàô ñî ñòåïåííîé ïîñëåäîâàòåëüíîñòüþ

d

1

≤

d

2

≤

. . .

≤

d

n

ÿâëÿåòñÿ ãàìèëüòîíîâûì, åñëè äëÿ âñÿêîãî

k

, óäîâëåòâîðÿþùåãî íåðà-

âåíñòâàì

1

≤

k <

n

2

, èñòèííà èìïëèêàöèÿ

(

d

k

≤

k

)

⇒

(

d

n

−

k

≥

n

−

k

)

.

Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ýòîé òåîðåìû çäåñü íå ïðèâîäèòñÿ.

 ðàäèîýëåêòðîíèêå è ìèêðîýëåêòðîíèêå, â çàäà÷àõ ïðîåêòèðîâàíèÿ

æåëåçíîäîðîæíûõ è äðóãèõ ïóòåé, ãäå íåæåëàòåëüíû ïðåñå÷åíèÿ è ïåðååç-

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

âåðøèíû êîòîðîãî ÿâëÿþòñÿ òî÷êàìè ïëîñêîñòè, à ðåáðà  íåïðåðûâíûìè

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

âåðøèíû òàê, ÷òî íèêàêèå äâà ðåáðà íå èìåþò îáùèõ òî÷åê, êðîìå èíöè-

äåíòíîé èì îáîèì âåðøèíû. Ëþáîé ãðàô, èçîìîðôíûé ïëîñêîìó ãðàôó,

íàçûâàåòñÿ ïëàíàðíûì ãðàôîì.