Сеть. Поток в сети. Задача о максимальном потоке в сети. Алгоритм нахождения максимального потока.

 

Сетью называется ориентированный граф G=(V,E), каждому ребру (u,v)ÎE которого поставлено в соответствие число c(u,v) ³ 0, называемое пропускной способностью ребра. В случае (u,v)ÏE, полагаем c(u,v)=0.

В графе выделены 2 вершины: источник s и сток t. Граф связен, т.е..

Пусть дана сеть G=(V,E), пропускная способность которой задаётся функцией с.

Потоком в сети G назовём функцию, обладающую следующими свойствами:

1. Ограничение, связанное с пропускной способностью: для всех u,v изV;

2. Кососимметричность: для всех u,v из V;

3. Сохранение потока: для всех u из V - {s,t}.

 

Величина потока определяется как сумма потоков по всем рёбрам выходящим из истока.

 

Дан ориентированный граф.

Будем рассматривать его как сеть труб, по которым некоторое вещество движется от источника к стоку. Веса на рёбрах - пропускная способность трубы.

Задача о максимальном потоке:

Найти максимально возможную скорость производства (и потребления) вещества, при которой его ещё можно доставить от истока к стоку при данных пропускных способностях труб. Или - для данной сети G с истоком s и стоком t найти поток максимальной величины.

Вершину сети v, для которой deg^-(v)>0 (полустепень исхода) и deg⁺(v)=0 (полустепень захода) будем называть источником, а вершину w, для которой deg⁺(w)>0 и deg^–(w)=0 – стоком.

Поток называется максимальным, если он имеет наибольшую величину (среди всех потоков через данную сеть).

Назовём разрезом сети G=(V, E) разбиение множества V на две части S и T=V \ S, для которых sÎS и tÎT.

Пропускной способностью разреза (S,T) называют сумму пропускных способностей, пересекающих разрез рёбер.

Для заданного потока f величина потока через разрез (S,T) определяется как сумма f(S,T) по пересекающим разрез рёбрам.

Минимальным разрезом называется разрез наименьшей пропускной способности (среди всех разрезов сети).

Теорема Форда-Фалкерсона:

Во всякой сети величина максимального потока равна пропускной способности любого минимального разреза.

 

Идея алгоритма состоит в нахождении сквозных путей с положительными потоками от источника к стоку.

Рассмотрим ребро, с начальной пропускной способностью.

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

(c_ij, c_ji) – остаточная пропускная способность.

Сеть, где все рёбра имеют остаточную пропускную способность, называется остаточной.

Для произвольного узла j, получающего поток от узла i, определим метку [a_{j, i}], где a_j – величина потока между узлами.

Алгоритм Форда-Фалкерсона нахождения максимального потока

1. Для всех рёбер (i,j) положить остаточную пропускную способность равной первоначальной:

Назначим a₁=¥ и пометим узел 1 меткой [¥,-].

Полагаем i=1.

1. Определить множество S_i, как множество узлов j, в которые можно перейти из i по ребру с положительной остаточной пропускной способностью.

Если S_i¹Æ, выполняем шаг 3, иначе шаг 4.

1. В множестве S_i находим узел k, такой, что

 

Положим a_k=c_ik и пометим узел k меткой [a_k,i].

Если последней меткой помечен узел стока (k=n), сквозной путь найден, переходим к шагу 5.

Иначе полагаем i=k и возвращаемся к шагу 2.

1. (Откат назад). Если i=1, сквозной путь невозможен, переходим к шагу 6.

Если i¹1, находим помеченный узел r, непосредственно предшествующий узлу i, и удаляем узел i из множества узлов, смежных с узлом r.

Полагаем i=r и возвращаемся к шагу 2.

1. (Определение остаточной сети).

Обозначим через множество узлов, через которые проходит p-й найденный сквозной путь от источника к стоку.

Тогда максимальный поток, проходящий по этому пути равен:

 

Остаточные пропускные способности рёбер, составляющих сквозной путь, уменьшаются на f_p в направлении движения потока и увеличиваются на f_p в противоположном направлении.

Для ребра (i,j), входящего в сквозной путь, текущие остаточные стоимости будут равны:

a), если поток i®j;

b) , если поток j ®i.

 

Восстанавливаем все узлы, удалённые на шаге 4. Полагаем i=1. Возвращаемся к шагу 2.

1. (Решение).

a) При m найденных сквозных путях максимальный поток вычисляется по формуле:

 

b) Имея значения начальных и конечных пропускных способностей ребра (i,j) вычисляем оптимальный поток через это ребро.

Положим

 

 

Если a>0, то поток, проходящий через ребро (i,j), равен a.

 

Если b>0, то поток равен b.

 

Случай, когда одновременно a>0 и b>0 невозможен.

 

 

Основные понятия теории графов: граф, способы задания, маршруты, связность, расстояния в графах, степени вершины.

Граф G задаётся множеством точек или вершин х₁, х₂,…, х_n (которое обозначается через Х) и множеством линий или ребер а₁, а₂,…, а_m (которое обозначается через А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задаётся (и обозначается) парой (Х, А).

Если ребра из множества А ориентированы, то они называются дугами, и граф с такими ребрами называется ориентированным графом. Если ребра не имеют ориентации, то граф называется неориентированным.

Чаще употребляемое описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины. Соответствие Г называется отображением множества Х в Х, а граф в этом случае обозначается парой G = (Х, Г)

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

Способы задания графов:

1. Явное задание графа как алгебраической системы.
2. Геометрический
3. Матрица смежности
4. Матрица инцидентности

Для алгебраического задания графов удобно использовать следующие матрицы:

- Пусть дан граф G, его матрица смежности обозначается через А = [a_ij] и определяется следующим образом:

a_ij = 1 если в G существует дуга (x_i, x_j)

a_ij = 0 если в G нет дуги (x_i, x_j)

 

- Пусть дан граф G с n вершинами и m дугами. Матрица инциденций графа G обозначается B=[b_ij] и является матрицей размерности n´m, определяемой следующим образом:

b_ij = 1, если x_i является начальной вершиной дуги a_j

b_ij = -1, если x_i является конечной вершиной дуги a_j

b_ij = 0, если x_i не является концевой вершиной дуги a_j

Поскольку каждая дуга индидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент, равный 1, и один – равный –1, либо все элементы столбца равны 0.

Если G – неориентированный граф, то его матрица инциденций определяется также как и выше, за исключением того, что все элементы, равные –1, заменяются на +1.

Рассмотрим различные способы задания для одного и того же графа.

1. <{ a,b,c,d },{ u,v,w,x }; {(u,a),(u,b),(v,b),(v,c),(w,c),(w,a),(x,c), (x,d)}>. Так как мы рассматриваем только простые графы, граф нам проще определять как модель, носителем которой является множество вершин, а отношение – бинарное отношение смежности вершин. Тогда данный граф запишется как <{ a,b,c,d }; {(a,b), (b,a),(b,c),(c,b),(a,c),(c,a),(c,d),(d,c)}>. В таком представлении ребру соответствуют две пары вершин (v ₁ ,v ₂) и (v ₂ ,v ₁), инцидентных данному ребру. Чтобы задать такое представление, достаточно для каждого ребра указать двухэлементное множество вершин – его мы и будем отождествлять с ребром. Для данного графа рёбра задаются множеством {{ a,b },{ b,c },{ a,c },{ c,d }} и граф мы будем записывать как пару (V,E), где V – множество вершин, а E – множество рёбер.

1. Геометрический

 

3. Матрица смежности

	a	b	c	d
A
B
C
d

4. Матрица инциденций

	u	v	w	x
D
C
B
A

Маршруты. Связность.

Маршрут – это последовательность рёбер e₁,..,e_m такая, что e_i,e_i+1 имеют общую вершину.

Число рёбер называется длиной маршрута.

Пусть G –неориентированный граф.

Маршрут называется цепью, если все рёбра в нём различны.

Если ни одна из вершин не появляется более 1 раза, то маршрут называется простой цепью.

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

Циклическая цепь называется циклом, а циклическая простая цепь – простым циклом.

Неорграф без циклов называется ациклическим.

Минимальная из длин циклов неорграфа называется обхватом.

ПРИМЕР:

(1,2), (1,2,4,7), (3,4,5,6) – простые цепи

(1,2,4,7,8,4) – цепь не простая

(1,2,4,7,8,4,2) – маршрут, не являющийся цепью

(1,2,4,7,8,4,1) – цикл не простой

(1,2,4,1) – простой цикл

Обхват графа =3

Пусть G – ориентированный граф.

Путь – маршрут, у которого все дуги различны.

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

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

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

 

Неориентированный граф называется связным, если любые две его несовпадающие вершины соединены маршрутом.

Орграф называется связным, если соответствующий ему неорграф тоже является связным.

Орграф называется сильно связным, если для каждой пары различных вершин а и b существуют (a,b)-путь и (b,a) – путь.

Любой связный неорграф является сильно связным.

Всякий максимальный по включению связный подграф данного графа называется его компонентой связности.

Пусть G=<M,R> - связный неорграф, a,b – две его несовпадающие вершины. Длина кратчайшего (a,b)- маршрута называется расстоянием между вершинами a и b и обозначается через ρ(a,b). Положим ρ(a,a)=0. Тогда введённое таким образом расстояние удовлетворяет следующим аксиомам метрики:

¾ ρ(a,b)≥0;

¾ ρ(a,b)=0Ûa=b;

¾ ρ(a,b)= ρ(b,a);

¾ ρ(a,b)≤ ρ(a,с)+ ρ(с,b).

Если М={a₁, a₂,…,a_n}, то матрица P=(p_ij), в которой p_ij= ρ(a_i, a_j), называется матрицей расстояний.

Для фиксированной вершины a величина называется эксцентриситетом вершины а. Эксцентриситет вершины равен расстоянию от данной вершины до наиболее удалённой от неё.

Максимальный среди всех эксцентриситетов вершин называется диаметром графа G и обозначается через d(G): . Вершина называется периферийной, если d(G)=e(a).

Минимальный из эксцентриситетов графа G называется его радиусом и обозначается через r(G): . Вершина а называется центральной, если e(a)=r(G). Множество всех центральных вершин графа называется его центром.

Степенью (deg v) или валентностью вершины v неориентированного графа G называется число рёбер, инцидентных вершине v.

Вершина степени 0 называется изолированной.

Вершина степени 1 называется концевой или висячей.

Пусть G – ориентированный граф.

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

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

Справедливо соотношение:

Лемма:

Сумма степеней всех вершин графа является чётным числом и равна удвоенному числу рёбер.