ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 864
Скачиваний: 9
116
ÃËÀÂÀ 3. ÝËÅÌÅÍÒÛ ÒÅÎÐÈÈ ÃÐÀÔÎÂ
Ñëåäóþùàÿ òåîðåìà îäèí èç íàèáîëåå ñèëüíûõ ðåçóëüòàòîâ, êàñàþ-
ùèõñÿ ãàìèëüòîíîâûõ ãðàôîâ.
Òåîðåìà 3.21. Âñÿêèé 4-ñâÿçíûé ïëàíàðíûé ãðàô ÿâëÿåòñÿ ãàìèëüòîíî-
âûì.
Äîêàçàòåëüñòâî. Âåñüìà ñëîæíîå äîêàçàòåëüñòâî ýòîé òåîðåìû çäåñü íå
ïðèâîäèòñÿ.
Ïóñòü
G
=
< V, E >
ñâÿçíûé ãðàô,
u
,
v
äâå åãî íåñîâïàäàþùèå âåð-
øèíû. Äëèíà êðàò÷àéøåãî
(
u, v
)
-ïóòè (îí, åñòåñòâåííî, ÿâëÿåòñÿ ïðîñòûì
ïóòåì) íàçûâàåòñÿ ðàññòîÿíèåì ìåæäó âåðøèíàìè
u
è
v
è îáîçíà÷àåò-
ñÿ ÷åðåç
d
(
u, v
)
. Ïîíÿòèå ðàññòîÿíèÿ ìåæäó âåðøèíàìè â ñâÿçíîì ãðàôå
ïîçâîëÿåò îïðåäåëèòü
k
-óþ ñòåïåíü ãðàôà. Ïóñòü
G
ñâÿçíûé ãðàô,
k
íàòóðàëüíîå ÷èñëî. Ãðàô
G
k
èìååò òî æå ìíîæåñòâî âåðøèí, ÷òî è
G
,
íåñîâïàäàþùèå âåðøèíû
u
è
v
ñìåæíû â ãðàôå
G
k
òîãäà è òîëüêî òîãäà,
êîãäà äëÿ ãðàôà
G
âåðíî íåðàâåíñòâî
d
(
u, v
)
≤
k
. Î÷åâèäíî, ÷òî åñëè
k
≥ |
V
| −
1
, òî
G
k
ïîëíûé ãðàô.
Èíòóèòèâíî ÿñíî, ÷òî åñëè ãðàô ïîðÿäêà
n
=
|
V
| ≥
3
ñâÿçåí, òî ïðè
äîñòàòî÷íî áîëüøèõ
k
ãðàô
G
k
ãàìèëüòîíîâ. Ïðèâåäåì áåç äîêàçàòåëüñòâà
äâå òåîðåìû, êàñàþùèåñÿ ãàìèëüòîíîâîñòè ñòåïåíåé ãðàôà.
Òåîðåìà 3.22. Åñëè ãðàô
G
ïîðÿäêà
n
=
|
V
| ≥
3
ñâÿçåí, òî
G
3
ãàìèëü-
òîíîâ ãðàô.
Òåîðåìà 3.23. Åñëè
G
äâóñâÿçíûé ãðàô ïîðÿäêà
n
=
|
V
| ≥
3
, òî
G
2
ãàìèëüòîíîâ ãðàô.
3.9 Íàõîæäåíèå êðàò÷àéøèõ ïóòåé â ãðàôå
 ýòîì ðàçäåëå ìû áóäåì ðàññìàòðèâàòü îðèåíòèðîâàííûå ãðàôû
G
=
< V, E >
, ðåáðàì êîòîðûõ ïðèïèñàíû âåñà. Ýòî îçíà÷àåò, ÷òî êàæ-
äîìó ðåáðó
< u, v >
∈
E
ïîñòàâëåíî â ñîîòâåòñòâèå âåùåñòâåííîå ÷èñëî
c
(
u, v
)
, íàçûâàåìîå âåñîì äàííîãî ðåáðà. Ïîëàãàåì, ÷òî
(
u, v
) =
∞
, åñëè
< u, v > /
∈
E
.
Åñëè
S
=
< v
0
, v
1
, . . . , v
p
>
ïóòü â
G
, òî åãî äëèíà îïðåäåëÿåòñÿ êàê
ñóììà
p
X
i
=1
c
(
v
i
−
1
, v
i
)
.
3.9. ÍÀÕÎÆÄÅÍÈÅ ÊÐÀÒ×ÀÉØÈÕ ÏÓÒÅÉ Â ÃÐÀÔÅ
117
(Îòìåòèì, ÷òî åñëè â ïðîèçâîëüíîì ãðàôå ìû ïðèìåì âåñ êàæäîãî ðåáðà
ðàâíûì åäèíèöå, òî ïîëó÷èì îáû÷íîå îïðåäåëåíèå äëèíû ïóòè êàê ÷èñëà
ðåáåð).
Íàñ áóäåò èíòåðåñîâàòü íàõîæäåíèå êðàò÷àéøåãî ïóòè ìåæäó ôèêñè-
ðîâàííûìè âåðøèíàìè
v, t
∈
V
. Äëèíó òàêîãî êðàò÷àéøåãî ïóòè
d
(
v, t
)
è
áóäåì íàçûâàòü ðàññòîÿíèåì îò
v
äî
t
. Îòìåòèì, ÷òî åñëè êàæäûé öèêë íà-
øåãî ãðàôà èìååò ïîëîæèòåëüíóþ äëèíó, òî êðàò÷àéøèé ïóòü áóäåò âñåãäà
ïðîñòûì.
Âî ìíîãèõ ïðèëîæåíèÿõ äîñòàòî÷íî íàõîäèòü êðàò÷àéøèå ïóòè ìåæ-
äó äâóìÿ êîíêðåòíûìè âåðøèíàìè, îäíàêî, íåèçâåñòåí àëãîðèòì, êîòîðûé
ðåøàë áû ýòó çàäà÷ó ýôôåêòèâíåå (â õóäøåì ñëó÷àå), ÷åì ëó÷øèé èç èç-
âåñòíûõ àëãîðèòìîâ äëÿ íàõîæäåíèÿ êðàò÷àéøèõ ðàññòîÿíèé îò îäíîé âåð-
øèíû
v
0
, íàçûâàåìîé èñòî÷íèêîì, äî âñåõ îñòàëüíûõ âåðøèí.
Çàäà÷à íàõîæäåíèÿ êðàò÷àéøèõ ïóòåé îò îäíîãî èñòî÷íèêà ðåøàåòñÿ
äëÿ òðåõ ñëó÷àåâ.
1. Îðèåíòèðîâàííûé ãðàô áåç öèêëîâ ñ îòðèöàòåëüíîé äëèíîé (ñëîæ-
íîñòü àëãîðèòìà
O
(
n
3
)
, ãäå
n
÷èñëî âåðøèí).
2. Âåñà âñåõ ðåáåð íåîòðèöàòåëüíû (ñëîæíîñòü àëãîðèòìà
O
(
n
2
)
).
3. Ãðàô áåç öèêëîâ (ñëîæíîñòü àëãîðèòìà
O
(
n
2
)
).
3.9.1 Àëãîðèòì íàõîæäåíèÿ ðàññòîÿíèÿ îò èñòî÷íèêà
äî âñåõ îñòàëüíûõ âåðøèí â îðèåíòèðîâàííîì
ãðàôå ñ íåîòðèöàòåëüíûìè âåñàìè ð¼áåð
Èñõîäíûå äàííûå:
G
=
< V, E >
îðèåíòèðîâàííûé, ñâÿçíûé, êîíå÷íûé
ãðàô c íåîòðèöàòåëüíûìè âåñàìè ðåáåð.
v
0
èñòî÷íèê,
v
0
∈
V
.
C
=
||
c
(
u, v
)
||
;
u,
;
v
∈
V
;
c
(
u, v
)
≥
0
ìàòðèöà âåñîâ ðåáåð.
Ðåçóëüòàò: ðàññòîÿíèÿ îò èñòî÷íèêà äî âñåõ âåðøèí ãðàôà
D
[
v
] =
d
(
v
0
, v
)
,
v
∈
V
.
Ìåòîä. Ñòðîèì òàêîå ïîäìíîæåñòâî
S
ìíîæåñòâà âåðøèí ãðàôà,
S
⊆
V
,
÷òî êðàò÷àéøèé ïóòü èç èñòî÷íèêà â êàæäóþ âåðøèíó
v
∈
S
öåëèêîì
ëåæèò â
S
.
S
:=
{
v
0
}
;
D
[
v
] :=
c
(
v
0
, v
)
;
D
[
v
0
] := 0
;
while
V
6
=
S
do
118
ÃËÀÂÀ 3. ÝËÅÌÅÍÒÛ ÒÅÎÐÈÈ ÃÐÀÔÎÂ
begin
âûáðàòü âåðøèíó
u
∈
V
\
S
, äëÿ êîòîðîé
D
(
u
) = min
v
∈
V
D
(
v
)
;
S
:=
S
∪ {
u
}
;
äëÿ âñåõ
v
∈
V
\
S D
[
v
] := min(
D
[
v
]
, D
[
v
] +
C
[
u, v
])
end
×òîáû ïîêàçàòü êîððåêòíîñòü àëãîðèòìà, íàäî äîêàçàòü èíäóêöèåé ïî
ðàçìåðó ìíîæåñòâà
S
, ÷òî äëÿ êàæäîé âåðøèíû
v
∈
S
÷èñëî
D
[
v
]
ðàâíî
äëèíå êðàò÷àéøåãî ïóòè èç
v
0
â
v
. Áîëåå òîãî, äëÿ âñåõ
v
∈
V
\
S
÷èñëî
D
[
v
]
ðàâíî äëèíå êðàò÷àéøåãî ïóòè èç
v
0
â
v
, ëåæàùåãî öåëèêîì (åñëè íå
ñ÷èòàòü ñàìó âåðøèíó
v
) â
S
.
Áàçèñ èíäóêöèè. Ïóñòü
|
S
|
= 1
. Êðàò÷àéøèé ïóòü èç
v
0
â ñåáÿ èìååò
äëèíó 0, à ïóòü èç
v
0
â
v
, ëåæàùèé öåëèêîì (èñêëþ÷àÿ
v
) â
S
, ñîñòîèò èç
åäèíñòâåííîãî ðåáðà
< v
0
, v >
.
Øàã èíäóêöèè. Ïóñòü
u
óçåë äëÿ êîòîðîãî
D
(
u
) = min
v
∈
V
D
(
v
)
.
Åñëè ÷èñëî
D
[
u
]
íå ðàâíî äëèíå êðàò÷àéøåãî ïóòè èç
v
0
â
u
, òî äîë-
æåí áûòü áîëåå êîðîòêèé ïóòü
P
. Ýòîò ïóòü äîëæåí ñîäåðæàòü âåðøèíó,
îòëè÷íóþ îò
u
è íå ïðèíàäëåæàùóþ
S
. Ïóñòü
v
ïåðâàÿ òàêàÿ âåðøèíà
íà ïóòè
P
èç âåðøèíû
v
0
â âåðøèíó
u
(ñìîòðèòå ðèñ. 3.9).
Íî òîãäà ðàññòîÿíèå îò
v
0
äî
v
ìåíüøå
D
[
u
]
, à êðàò÷àéøèé ïóòü â
âåðøèíó
v
, öåëèêîì (èñêëþ÷àÿ ñàì óçåë
v
) ëåæèò â
S
. Ñëåäîâàòåëüíî, ïî
ïðåäïîëîæåíèþ èíäóêöèè,
D
[
v
]
< D
[
u
]
â ìîìåíò âûáîðà
u
; òàêèì îáðàçîì,
ìû ïðèøëè ê ïðîòèâîðå÷èþ. Îòñþäà çàêëþ÷àåì, ÷òî òàêîãî ïóòè
P
íåò è
D
[
u
]
äëèíà êðàò÷àéøåãî ïóòè èç
v
0
â
u
.
Ðèñ. 3.9
Âòîðîå óòâåðæäåíèå (î òîì, ÷òî
D
[
u
]
îñòàåòñÿ êîððåêòíûì) î÷åâèäíî ââèäó
ïîñëåäíåãî îïåðàòîðà ïðèñâàèâàíèÿ â àëãîðèòìå.
3.10. ÌÀÊÑÈÌÀËÜÍÛÉ ÏÎÒÎÊ Â ÑÅÒÈ
119
3.10 Ìàêñèìàëüíûé ïîòîê â ñåòè
Ïîä ñåòüþ áóäåì ïîíèìàòü ïàðó
S
=
< G, c >
, ãäå
G
=
< V, E >
ïðîèç-
âîëüíûé îðèåíòèðîâàííûé ãðàô, à
c
:
E
→
R
ôóíêöèÿ, êîòîðàÿ êàæäîìó
ðåáðó
< u, v >
ñòàâèò â ñîîòâåòñòâèå íåîòðèöàòåëüíîå âåùåñòâåííîå ÷èñëî
(
u, v
)
, íàçûâàåìîå ïðîïóñêíîé ñïîñîáíîñòüþ ðåáðà.
Åñëè äëÿ
f
:
E
→
R f
(
u, v
)
ìû èíòåðïðåòèðóåì êàê ïîòîê èç
u
â
v
, òî
âåëè÷èíà
D
f
(
v
)
,
D
f
(
v
) =
X
u
:
<v, u>
∈
E
f
(
v, u
)
−
X
u
:
<u, v>
∈
E
f
(
u, v
)
,
îïðåäåëÿåò ¾êîëè÷åñòâî ïîòîêà¿, âûõîäÿùåãî èç âåðøèíû
v
.
Åñëè
D
f
(
v
)
>
0
, òî âåðøèíà
v
íàçûâàåòñÿ èñòî÷íèêîì, åñëè
D
f
(
v
)
<
0
,
òî âåðøèíà
v
íàçûâàåòñÿ ñòîêîì. Äëÿ áîëüøèíñòâà âåðøèí
D
f
(
v
)
>
0
.
Âûäåëèì â íàøåé ñåòè äâå âåðøèíû èñòî÷íèê
s
è ñòîê
t
. Ïîä ïîòîêîì
èç âåðøèíû
s
â âåðøèíó
t
â ñåòè
S
áóäåì ïîíèìàòü ïðîèçâîëüíóþ ôóíêöèþ
f
:
E
→
R
, äëÿ êîòîðîé âûïîëíÿþòñÿ óñëîâèÿ:
1.
0
≤
f
(
u, v
)
≤
c
(
u, v
)
äëÿ âñåõ ð¼áåð
< u, v >
∈
E
;
2.
D
f
(
v
) = 0
äëÿ âñåõ
v
∈
V
\ {
s, t
}
.
Âåëè÷èíó
W
(
f
) =
D
f
(
s
)
áóäåì íàçûâàòü âåëè÷èíîé ïîòîêà.
Òàêîé ïîòîê ìîæåò îïèñûâàòü, íàïðèìåð, ïîâåäåíèå ãàçà èëè æèäêî-
ñòè â òðóáîïðîâîäå, ïîòîêè àâòîìîáèëåé, äâèæåíèå ïî æåëåçíîé äîðîãå,
ïåðåäà÷ó èíôîðìàöèè â èíôîðìàöèîííîé ñåòè.
Ìû áóäåì èíòåðåñîâàòüñÿ íàõîæäåíèåì ìàêñèìàëüíîãî ïîòîêà â ñåòè.
Ïîä ðàçðåçîì
()
ñåòè
S
, ñîîòâåòñòâóþùèì ïîäìíîæåñòâó
A
⊆
V
(
A
6
=
∅
,
A
6
=
V
)
ìû ïîíèìàåì ìíîæåñòâî ðåáåð
< u, v >
∈
E
, òàêèõ, ÷òî
u
∈
A,
v
∈
V
\
A
, ò.å.
P
(
A
) =
E
∩
(
A
×
(
V
\
A
))
.
Ðàçðåç ýòî ëèíèÿ èëè ìíîæåñòâî ëèíèé, êîòîðûå ïîëíîñòüþ ðàçäå-
ëÿþò èñòî÷íèê è ñòîê.
120
ÃËÀÂÀ 3. ÝËÅÌÅÍÒÛ ÒÅÎÐÈÈ ÃÐÀÔÎÂ
Äëÿ ïðîèçâîëüíîãî ïîòîêà
f
â ñåòè
S
ïîòîê ÷åðåç ðàçðåç
P
(
A
)
îïðåäå-
ëÿåòñÿ åñòåñòâåííûì îáðàçîì:
f
(
A, V
\
A
) =
X
e
=
<u, v>
∈
P
(
A
)
f
(
u, v
)
.
Ëåììà 3.24. Åñëè
s
∈
A
è
t
∈
V
\
A
, òî äëÿ ïðîèçâîëüíîãî ïîòîêà f èç
s
â
t
èìååò ìåñòî ñîîòíîøåíèå
W
(
f
) =
f
(
A, V
\
A
)
−
f
(
V
\
A, A
)
 îáùåì âèäå ëåììà ãîâîðèò, ÷òî îáùåå êîëè÷åñòâî ïîòîêà ìîæíî èç-
ìåðèòü â ïðîèçâîëüíîì ðàçðåçå, îòäåëÿþùåì
s
îò
t
.
 ÷àñòíîñòè, åñëè
A
=
V
\ {
t
}
, ïîëó÷àåì â ýòîì ñëó÷àå èç ëåììû:
D
f
(
s
) =
W
(
f
) =
f
(
V
\ {
t
}
,
{
t
}
)
−
f
(
{
t
}
, V
\ {
t
}
) =
=
−
(
f
(
{
t
}
, V
\ {
t
}
)
−
f
(
V
\ {
t
}
,
{
t
}
)) =
−
D
f
(
t
)
,
÷òî âûðàæàåò èíòóèòèâíî ïîíÿòíûé ôàêò: â ñòîê âõîäèò â òî÷íîñòè òàêîå
êîëè÷åñòâî ïîòîêà, êàêîå âûõîäèò èç èñòî÷íèêà.
Äîêàçàòåëüñòâî. Ïðîñóììèðóåì óðàâíåíèÿ
D
f
(
v
) = 0
äëÿ âñåõ
v
∈
A
.
Ýòà ñóììà ñîñòîèò èç íåêîòîðîãî êîëè÷åñòâà ñëàãàåìûõ
f
(
u, v
)
ñî çíàêîì
+
èëè
−
, ïðè÷åì õîòÿ áû îäíà èç âåðøèí ïðèíàäëåæèò . Åñëè îáå âåðøèíû
ïðèíàäëåæàò , òî
f
(
u, v
)
ïîÿâëÿåòñÿ ñî çíàêîì ïëþñ â
D
f
(
u
)
è ñî çíàêîì
ìèíóñ â
D
f
(
v
)
, ÷òî â ñóììå äàåò 0.
Êàæäîå èç ñëàãàåìûõ
f
(
u, v
)
, u
∈
A
ïîÿâëÿåòñÿ â òî÷íîñòè îäèí ðàç
ñî çíàêîì ïëþñ â
D
f
(
u
)
, ÷òî â ñóììå äàåò
f
(
A, V
\
A
)
. Àíàëîãè÷íûå ñëà-
ãàåìûå
f
(
u, v
)
, u
∈
V
\
A, v
∈
A
, îòâå÷àþò çà ñëàãàåìîå
f
(
V
\
A, A
)
Ñ
äðóãîé ñòîðîíû, ñóììà ðàâíà
D
f
(
s
) =
W
(
f
)
, èáî
D
f
(
s
) = 0
äëÿ êàæäîãî
v
∈
A
\ {
s
}
.
Îïðåäåëèì ïðîïóñêíóþ ñïîñîáíîñòü ðàçðåçà
P
(
A
)
ñëåäóþùèì ñïîñî-
áîì:
C
(
A, V
\
A
) =
X
e
=
<u, v>
∈
P
(
A
)
c
(
u, v
)
.
Ïîä ìèíèìàëüíûì ðàçðåçîì, ðàçäåëÿþùèì
s
è
t
, áóäåì ïîíèìàòü ïðîèç-
âîëüíûé ðàçðåç
P
(
A
)
,
s
∈
A
,
t
∈
V
\
A
ñ ìèíèìàëüíîé ïðîïóñêíîé ñïî-
ñîáíîñòüþ. Ôóíäàìåíòàëüíûì ôàêòîì òåîðèè ïîòîêîâ â ñåòÿõ ÿâëÿåòñÿ
êëàññè÷åñêàÿ òåîðåìà î ìàêñèìàëüíîì ïîòîêå è ìèíèìàëüíîì ðàçðåçå.