ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.03.2021
Просмотров: 862
Скачиваний: 9
3.10. ÌÀÊÑÈÌÀËÜÍÛÉ ÏÎÒÎÊ Â ÑÅÒÈ
121
Òåîðåìà 3.25. Âåëè÷èíà êàæäîãî ïîòîêà èç
s
â
t
íå ïðåâîñõîäèò ïðî-
ïóñêíîé ñïîñîáíîñòè ìèíèìàëüíîãî ðàçðåçà, ðàçäåëÿþùåãî
s
è
t
, ïðè÷åì
ñóùåñòâóåò ïîòîê, äîñòèãàþùèé ýòîãî çíà÷åíèÿ.
Äîêàçàòåëüñòâî. Ïóñòü
P
(
A
)
ìèíèìàëüíûé ðàçðåç. Â ñèëó ëåììû äëÿ
ïðîèçâîëüíîãî ïîòîêà
f
èìååì
W
(
f
) =
f
(
A, V
\
A
)
−
f
(
V
\
A, A
)
≤
f
(
A, V
\
A
) =
=
X
e
∈
P
(
A
)
f
(
e
)
≤
X
e
∈
P
(
A
)
c
(
e
) =
C
(
A, V
\
A
)
.
Ñóùåñòâîâàíèå ïîòîêà, äëÿ êîòîðîãî óêàçàííîå íåðàâåíñòâî ïåðåõîäèò â
ðàâåíñòâî (òàêîé ïîòîê, î÷åâèäíî, ìàêñèìàëåí), ãîðàçäî áîëåå ãëóáîêèé
ôàêò, êîòîðûé çäåñü ìû äîêàçûâàòü íå áóäåì.
122
ÃËÀÂÀ 3. ÝËÅÌÅÍÒÛ ÒÅÎÐÈÈ ÃÐÀÔÎÂ
Ëèòåðàòóðà
[1] Ñòåíëè Ð. Ïåðå÷èñëèòåëüíàÿ êîìáèíàòîðèêà. Ì.: Ìèð, 1990.
[2] Ëèïñêèé Â. Êîìáèíàòîðèêà äëÿ ïðîãðàììèñòîâ. Ì.: Ìèð, 1988.
[3] Ðûáíèêîâ Ê.À. Ââåäåíèå â êîìáèíàòîðíûé àíàëèç. Ì.: ÌÃÓ,1985.
[4] Ãàâðèëîâ Ã.È., Ñàïîæåíêî À.À. Çàäà÷è è óïðàæíåíèÿ ïî êóðñó äèñ-
êðåòíîé ìàòåìàòèêè. Ì.: Íàóêà, 1992.
[5] Ðèîðäàí Äæ. Ââåäåíèå â êîìáèíàòîðíûé àíàëèç. Ì.: ÈË, 1963.
[6] Õîëë Ì. Êîìáèíàòîðèêà. Ì.: Ìèð, 1970.
[7] Ìåíäåëüñîí Ý. Ââåäåíèå â ìàòåìàòè÷åñêóþ ëîãèêó.- Ì.: Íàóêà, 1976.
[8] Äèñêðåòíàÿ ìàòåìàòèêà è ìàòåìàòè÷åñêèå âîïðîñû êèáåðíåòèêè.
Ïîä ðåä. Ñ.Â.ßáëîíñêîãî, Î.Â.Ëóïàíîâà, Ò.1, Ì.; Íàóêà, 1974.
[9] ßáëîíñêèé Ñ.Â. Ââåäåíèå â äèñêðåòíóþ ìàòåìàòèêó. Ì.: Íàóêà, 1979.
[10] Îðå Î. Òåîðèÿ ãðàôîâ. Ì.: Íàóêà, 1968.
[11] Êðèñòîôèäèñ Í. Òåîðèÿ ãðàôîâ. Àëãîðèòìè÷åñêèé ïîäõîä. Ì.: Ìèð,
1987.
[12] Åìåëè÷åâ Â.À., Ìåëüíèêîâ Î.È. è äð. Ëåêöèè ïî òåîðèè ãðàôîâ. Ì.:
Íàóêà, 1990.
[13] Óèëñîí Ð.Äæ. Ââåäåíèå â òåîðèþ ãðàôîâ. Ì.: Ìèð, 1977.
[14] Õàðàðè Ô. Òåîðèÿ ãðàôîâ. Ì.: Ìèð,1973.
123