ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 896
Скачиваний: 9
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
)
.
Äîêàçàòåëüñòâî. Äîêàçàòåëüñòâî ýòîé òåîðåìû çäåñü íå ïðèâîäèòñÿ.
 ðàäèîýëåêòðîíèêå è ìèêðîýëåêòðîíèêå, â çàäà÷àõ ïðîåêòèðîâàíèÿ
æåëåçíîäîðîæíûõ è äðóãèõ ïóòåé, ãäå íåæåëàòåëüíû ïðåñå÷åíèÿ è ïåðååç-
äû, âîçíèêàåò ïîíÿòèå ïëîñêîãî ãðàôà. Ïëîñêèì ãðàôîì íàçûâàåòñÿ ãðàô,
âåðøèíû êîòîðîãî ÿâëÿþòñÿ òî÷êàìè ïëîñêîñòè, à ðåáðà íåïðåðûâíûìè
ïëîñêèìè ëèíèÿìè áåç ñàìîïåðåñå÷åíèé, ñîåäèíÿþùèìè ñîîòâåòñòâóþùèå
âåðøèíû òàê, ÷òî íèêàêèå äâà ðåáðà íå èìåþò îáùèõ òî÷åê, êðîìå èíöè-
äåíòíîé èì îáîèì âåðøèíû. Ëþáîé ãðàô, èçîìîðôíûé ïëîñêîìó ãðàôó,
íàçûâàåòñÿ ïëàíàðíûì ãðàôîì.