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

Варианты задач:

Задачи о MAX потоке

Рассмотрим граф G=(X,A) с пропускными способностями дуг g,i,j, источником S и стоком t.S,t X.Множество чисел ,определенных на дугах ( , называется потоками в

дугах, если выполняется условие

ij qij (xI xj) A(2)

максимально

),	Теорема Форда-Фацкерсона:
	(о максимальном потоке и максимальном

Доказательство.

Алгоритм начинает работу с произвольного допустимого потока (можно взять и 0-й поток), затем стремится увеличить величину потока с помощью систематического поиска всех возможных аугментальных целей потока от s к t. Поиск аугментальной цели осуществляется с помощью расставленных пометок в вершинах графа. Поэтому указывают, вдоль каких дуг может быть увеличен поток и на сколько.

Как только найдена одна из таких цепей, поток вдоль нее увеличивают до max значения, а пометки в вершинах стираются и вновь полученный поток используется в качестве исходного при новой расстановке пометок. Алгоритм работу заканчивает и дает max поток, если нельзя найти ни 1 аугментальную цель.

Алгоритм расстановки пометок для задачи о max (от s и t) потоке.

А. Расстановка пометок.

Пример задачи о max потоке.

Пусть дан граф G (направленный, без циклов, нумерация вершины от меньшего номера к большему).