12. Потоки в сетях.

Многие прикладные задачи, связанные с перевозкой грузов, организацией коммуникаций, распределением товаров и т.п., естественно

приводят к определению важного класса ориентированных графов, называемых сетями. Цель контрольной работы - изучить основные свойства сетей и рассмотреть практические задачи, решение которых сводится к основной задаче транспортных сетей о максимальном потоке. Рекомендуется следующий план работы:

1) Изучить такие основополагающие понятия теории сетей, как ориентированный граф, сеть, поток в сети и разрез сети (/1/, с. 126-131; 163-166; /2/, с. 114-117; /3/, с. 136-138).

2) Разобрать доказательство теоремы Форда-Фалкерсона о максимальном потоке и минимальном разрезе (/1/, с. 165-171; /2/, с. 114-118; /3/, с. 138-141).

3) Рассмотреть прикладные задачи, решение которых сводится к построению максимального потока в сети (/2/, с. 119-122).

Литература, рекомендуемая для изучения темы