Сети и потоки в сетях. Топологическая сортировка сети. Определение потока. Теорема Форда-Фалкерсона.

Сетью правильнее всего называть любой бесконтурный ориентированный граф. Заметьте: бесконтурный неориентированный граф – это свободное дерево, а бесконтурный орграф – не всегда дерево. Но поскольку, бесконтурный ориентированный граф описывает бинарное отношение строгого частичного порядка, в нем обязательно есть минимальный элемент, то есть вершина, полустепень захода которой равно нулю. Эта вершина называется источником. Такая вершина может быть не одна. И есть вершина, тоже, возможно, не одна, полустепень исхода которой равна нулю, иначе в графе неизбежно образовался бы контур. Такая вершина называется стоком.

В принципе, мы всегда можем стянуть все источники в один, стоки тоже в один и получить сеть с одним источником и одним стоком. Но для этого нужно предварительно найти все источники и все стоки, для чего придется упорядочить вершины по уровням (слоям).

Уровнем вершины v называется максимальная длина пути S (v ₀, v), т.е. максимальное число неповторяющихся дуг, по которым вершина v достижима из источника v ₀.

Отображение V ® N, сопоставляющее каждой вершине номер ее уровня, называется порядковой функцией сети. Процесс распределения вершин по уровням (расчет их порядковой функции) называется топологической сортировкой сети. Одним из простейших алгоритмов топологической сортировки является алгоритм Демукрона.

 

Рассмотрим его на примере орграфа, заданного следующей матрицей смежности. Для наглядности нули заменим пробелами.

 

 

{ u: (v, u)Î E }

{ u: (u, v)Î E }

v

Рис. 3.22. К понятию дивергенции.

Сразу будем работать с матрицей. Прежде всего, заметим, что если в строке все нули, это означает, что из нее никуда нельзя перейти. Такая вершина соответствует стоку. Столбец i в нашей матрице показывает, из каких вершин можно попасть в вершину i. Поэтому столбец из одних нулей будет соответствовать источнику. В примере это вершина 1.Присвоим ей уровень N=0.

Итак, вершину 1 уже зафиксировали на уровне N=0, поэтому ее можно исключить из рассмотрения. Замаскируем (сотрем) в матрице строку и столбец этой вершины и будем работать уже с матрицей (p-1)´(p-1).

Посмотрим, какая вершина в такой сокращенной сети стала источником. Нулевой столбец у нас возник для вершины 2. Поместим ее на уровень N=1 и, исключив из рассмотрения, продолжаем процесс.

 

 

На уровне N=2 у нас оказываются сразу две вершины: 3 и 5. Продолжаем процесс, исключив их из матрицы.

 

На уровне N=3 у нас оказалась одна вершина 4. Продолжаем дальше.

На уровень N=4 опять попало сразу две вершины: 6 и 8.

Теперь ясно, что на уровне N=5 окажутся вершины 7,9,10,11, а на последнем уровне N=6 – только одна вершина 12, которая в нашем примере является стоком. Процесс топологической сортировки завершен.

Заметим, что если на каком-то шаге у нас не появилось ни одного нулевого столбца, это означает, что в графе есть контур. То есть алгоритм Демукрона можно использовать и для обнаружения контуров.

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

Рассмотрим сеть G (V, E) с одним источником s Î V и одним стоком t Î V. Введем для дуг этой сети такое понятие, как пропускная способность. Пропускной способностью дуги назовем любое неотрицательное число, приписанное дуге, то, что мы раньше называли весом. Но теперь оно нам нужно для того, чтобы пропустить по ней какой-то поток, например, транспортный или информационный. Пропускная способность дуги – это ограничение на поток, который по этой дуге может течь. Будем обозначать пропускную способность c (u, v). Тогда любую матрицу неотрицательных весов ориентированного графа можно рассматривать как матрицу пропускных способностей C.

Формально, поток – это некоторая функция, заданная на дугах сети – f: E ® R. Нельзя строго сказать, что R Ì E: хотя дугиу R и E – общие, веса этих дуг могут быть различны.

Введем понятиедивергенциив узле (то есть в вершине). Пусть задана функция f: E ® R. Дивергенцией функции f в вершине v назовем величину (рис. 3.22)

 

С плюсом берется то, что вытекает, а с минусом - то, что втекает.

Дадим полное определение потока.

Функция f: E ® R называется потоком в сети G (V, E), если

1) для любой дуги (u, v) 0£ f (u, v)£ c (u, v);

2) для любой вершины v Î V \{ s, t } div(f,v)= 0 (это условие непрерывности потока; иногда его называют, по аналогии с электрическими цепями, законом Киргофа).

Величина div(f,s)=w(f) называется величиной потока.

Вспомним понятие (u, v) – разреза. В данном случае нас будет интересовать разрез P ( s, t ) между источником и стоком. То есть множество ребер, разбивающее сеть на две компоненты связности, таких что источник и сток находятся в разных компонентах. Можно математически определить этот разрез так:

P (s, t)={(u, v)Î E | u Î S, v Î T }, S Ì V, T Ì V, S Ç T =Æ, s Î S, t Î T..

Разрез P (s, t) полностью «блокирует» любой поток через сеть, независимо от его направления, поскольку связность орграфа определяется только наличием связи между вершинами, без учета ориентации дуг. Но так как дуги в сети имеют ориентацию, введем отдельные обозначения для разных направлений:

P ⁺={(u, v)Î E | u Î S, v Î T } – от источника к стоку,

P ^-={(v,u)ÎE | u Î S, v Î T } – от стока к источнику.

В бесконтурной сети, как мы определили ее выше, в этом вообще-то нет необходимости. Но, в общем случае, контуры все-таки допускаются, то есть поток будет течь через разрез и в том, и в другом направлении.

Сумма пропускных способностей дуг разреза P (s, t) называется пропускной способностью разреза и обозначается С (P), а сумма потоков по всем дугам разреза F (P).

Можно показать, что для разреза P (s, t) w (f)= F (P ⁺)- F (P ^-). Для этого достаточно рассмотреть величину потока через вершины v Î S, инцидентные всем дугам разреза. Эта величина равна Какие-то дуги выходят из этих вершин, а какие-то входят в них. Поток может течь и по тем, и по другим. Отсюда и получается, что w=F(P⁺)-F(P^-).Аналогично можно показать, что div(f,s)=-div(f,t).

Наиболее часто встречающейся задачей является вопрос о том, какой же максимальный поток f * можно пропустить через сеть с заданной матрицей пропускных способностей С. На этот вопрос дает ответ следующая теорема.

Теорема Форда-Фалкерсона. Величина максимального потока в сети равна минимальной пропускной способности ее P(s, t) разреза.

Попытаемся построить максимальный поток в сети. Т.е., в ней нет контуров, которые образуют циркуляцию потока. Из теоремы Форда-Фалкерсона и из того, что w = F (P ⁺)- F (P ^-), следует, что циркуляция не влияет на общую величину потока, поскольку величина потока в любом контуре равна нулю.

Рассмотрим сеть со следующей матрицей пропускных способностей С.

 

	*
		*
			*
				*
					*
						*
							*
								*

В любом случае пропускные способности дуг можно нормировать таким образом, чтобы поток оказался целочисленным.

Попробуем построить в этой сети максимальный поток. Чаще всего применяется схема постепенного наращивания потока, по принципу просмотра вершин, соответствующей поиску в ширину. Таким способом получаем самые короткие пути от источника до стока, и, следовательно, их наибольшее количество. Мощность минимального разреза равна максимальному количеству не пересекающихся по ребрам простых цепей. Но поскольку нас интересует не просто минимальный разрез, а разрез минимальной пропускной способности, в данном случае ребер в таком разрезе может оказаться и больше, чем в минимальном.

Вначале поток f ₀=0. Возьмем все множество достижимых из источника s =1 вершин: {2,3,6}. В этом множестве есть вершина, из которой достижим сток t =8. Через этот путь (1®6®8) можно пропустить поток, который допускает минимальная пропускная способность входящих в путь дуг. В данном случае это дуга (6,8). Ее пропускная способность с _6,8=1.

Итак, f ₁=1. Теперь уберем насыщенную дугу из сети и убавим пропускную способность дуги (1,6) на единицу.

	*
		*
			*
				*
					*
						*
							*
								*

Больше вершин, из которых достижим сток, в рассматриваемом множестве нет. В соответствии с принципом поиска в ширину, переходим к анализу множества смежности вершины 2: {3,4}. Сток достижим из вершины 4, отсюда имеем путь 1®2®4®8. Минимальную пропускную способность здесь имеет дуга (2,4): с _2,4=2. Увеличиваем поток f ₂= f ₁+2=3, дугу (2,4) исключаем из сети, а пропускные способности дуг (1,2) и (4,8) уменьшаем на 2.

 

	*
		*
			*
				*
					*
						*
							*
								*

 

	*
		*
			*
				*
					*
						*
							*
								*

Рассмотрим множество смежности вершины 3. Оно состоит из одной вершины 5, из которой сток, тем не менее, достижим. Получаем путь 1®3®5®8, в котором минимальную пропускную способность имеет дуга (1,3). Увеличиваем поток на единицу f ₃= f ₂+1=4, убираем насыщенную дугу и убавляем на единицу пропускные способности остальных дуг пути.

	*
		*
			*
				*
					*
						*
							*
								*

Несмотря на то, что через вершину 6 мы уже ходили, дуга (1, 6), осталась ненасыщенной. Поэтому рассмотрим множество смежности этой вершины так же, как и для предыдущих вершин. Здесь можно получить сразу несколько путей. Рассмотрим их по порядку. В пути 1®6®4®8 минимальная пропускная способность дуги с _4,8=1. Увеличиваем поток: f ₄= f ₃+1=5, убираем дугу (4,8) и уменьшаем пропускные способности остальных: с _1,6=2, с _6,4=1. В пути 1®6®7®8 сразу две дуги имеют минимальную пропускную способность с _1,6= с _6,7=2. Увеличиваем поток f ₅= f ₄+2=7 и исключаем эти дуги из сети. В результате всех проделанных действий наша таблица принимает следующий вид.

	*
		*
			*
				*
					*
						*
							*
								*

Теперь, по правилу поиска в ширину, переходим к рассмотрению вершин из множества смежности вершины 2, на текущем шаге состоящего из одной вершины 3. Имеем следующий путь: 1®2®3®5®8 с минимальной пропускной способностью с _2,3= с _3,5= с _5,8=2. Увеличиваем поток f ₆= f ₅+2=9. Дуги (2,3), (3,5), (5,8) удаляем, а пропускную способность дуги (1,2) уменьшаем на 2. В результате получаем

У нас осталась одна цепь, соединяющая s и t: 1,2,7,8, но в ней дуга (7,2) направлена от стока к источнику. Такие цепи называются аугментальными. Если по дуге (7,2) тек поток, его можно было бы уменьшить и, соответственно, увеличить поток от s к t. Но поток по дуге (7,2) равен нулю, следовательно, поток f =9 максимален. Попробуйте сами найти разрез P(s, t), пропускная способность которого, с учетом направления всех входящих в него дуг, равна 9.