4. Сетевые модели

Определение. Сеть - ориентированный связный граф без петель, где - множество вершин, A - множество дуг.

Определим поток в сети , как целочисленную функцию, заданную на ее дугах: для . Дуге , инцидентной вершинам и : соответствует поток , тогда дуге соответствует поток . Множество дуг, исходящих из , обозначим . Множество дуг, входящих в , обозначим . Тогда чистый поток из вершины :

Если , то вершина v - источник, а если , то v - сток. При - промежуточная вершина. Множество всех вершин есть объединение всех источников, стоков и промежуточных вершин: .

Закон сохранения потока в сети: .

4.1 Сведение сети к сети с одним источником и одним стоком

Сеть с источниками и стоками можно свести к сети с одним источником v и одним стоком w:

Величина потока в сети .