ТРАНСПОРТНАЯ СЕТЬ
— в простейшем случае Бержа граф
каждой дуге
которого приписана пропускная способность — целое число с
а среди вершин особо выделены две: вход
и выход z. Потоком по Т. с. наз. ф-ция
, определенная на дугах, принимающая целые значения и такая, что:
2) для любой вершины 
сумма значений 
на всех дугах, заходящих в х, равна сумме значений на дугах, исходящих из х.
Сумма значений 
на дугах, заходящих в z, равна сумме значений на дугах, исходящих
из 
величиной потока. Разрезом Т. с., определяемым подмн-вом 
ее вершин, содержащим 
мн-во 
тех дуг, которые имеют начало в А, а конец в 
пропускной способностью разреза наз. сумма 2 с 
по всем и 
Осн. теорема теории Т. с.: наибольшая величина потока по сети равна наименьшей из пропускных способностей ее разрезов. С помощью этой теоремы обосновывают следующий практически эффективный алгоритм Форда—Фалкерсона для нахождения наибольшего потока: пусть какой-то поток 
уже известен (напр., тривиальный 
ищем такую цепь Q с началом 
и концом z, что на каждой её дуге и, ориентированной внаправлении обхода цепи, 
а на каждой дуге, ориентированной в направлении, противоположном обходу, 
заменив 
на 
если и — дуга 1-го типа, и на 
если и — дуга 2-го типа (и не меняй значений 
на дугах, не принадлежащих цепи Q), увеличим поток по сети на 1; 2) если цепей указанного вида больше нет, то поток 
наибольший.
В более общем случае Т. с. может иметь по нескольку входов и выходов, а вместо чисел 
задают произвольные мн-ва 
целых неотрицательных чисел, и условие (1) заменяют таким: 
проблема существования потока по такой сети уже не тривиальна (т. к. некоторые 
) могут не содержать числа 
). В случае, когда все 
целочисленные интервалы (конечные или бесконечные), задачи существования, максимизации и минимизации потока сводятся к рассмотренной выше, а для общего случая их эффективное решение не найдено. С другой стороны, к задачам, рассматриваемым в теории Т. с., можно свести многие комбинаторные задачи, в т. ч. задачи, рассматриваемые в графов теории.
Лит.: Хоанг Туй. Графы и транспортные задачи. «Сибирский математический журнал», 1963, т. 4, № 2; Визиег В. Г., Плесневич Г. С. К проблеме минимальной раскраски вершин графа. «Сибирский математический журнал», 1965, т. 6, № 1; Берж К. Теория графов и ее применения. Пер. с франц. М., 1962 [библиогр. с. 293—302]; Форд Л. Р., Фалкерсон Д. Р. Потоки в сетях. Пер. с англ. М., 1966 [библиогр. с. 266—272].
А. А. Зыков.
