Транспортной сетью называется пара =(,) , где — взвешенный орграф, удовлетворяющий следующим условиям:
а) нет петель;
б) существует только одна вершина, не имеющая ни одного прообраза — это исток;
в) существует только одна вершина , не имеющая ни одного образа — это сток;
— функция пропускных способностей дуг ,которая является положительной вещественной функцией, определенной на множестве дуг графа, т.е. каждой дуге графа поставлено в соответствие положительное число (), называемое пропускной способностью дуги .
Вершина, не имеющая ни одного прообраза, называется входом сети или источником и обычно обозначается , а вершина ,не имеющая ни одного образа, называется выходом сети или стоком и обозначается . В транспортной сети существует один исток и один сток. Случаи, когда имеется несколько источников или несколько стоков, могут быть сведены к случаю c единственными и введением обобщенных (фиктивных) источника и стока.
Поток в дуге транспортной сети — количество продукта, передаваемого по дуге в единицу времени. Принимается условие: суммарный поток, заходящий в любую вершину сети (кроме истока и стока) равен суммарному потоку , выходящему из этой вершины.
Дуга сети называется насыщенной, если поток по этой дуге равен пропускной способности этой дуги. Поток по пути называется полным, если хотя бы одна дуга пути насыщена.
Величиной потока в сети называется сумма значений этой функции по всем выходным дугам сети (выходные дуги сети — это дуги, инцидентные стоку).
Разрезом сети называется минимальное (в смысле отношения включения) множество дуг, удаление которых “ разрывает” все пути, соединяющие исток и сток.
Пропускной способностью разреза называется число, равное сумме пропускных способностей дуг этого разреза. Разрез называется минимальным, если имеет наименьшую пропускную способность.
Отыскание минимального разреза — одна из основных задач анализа транспортных сетей.
В силу конечности графа минимальный разрез может быть найден перебором всех разрезов, но в задачах практической размерности минимальный разрез определяют при помощи теоремы Форда-Фалкерсона.
Список литературы
1. Электронный учебник по решению задач на графах — Татарский институт содействия бизнесу, http://www.tisbi.ru/resource/lib/graph/cont.htm