Пусть дан граф Gс множ (N,U)-связный. Каждому ребру поставлено в соответствии неотрицательное число cij, которое называется весом ребра. Графы такого типа называются взвешаными сетями.
Необходимо найти минимальное по весу остовное дерево.В данном случае под весом понимают сумму весов его рёбер.
Теорема. Пусть G(N,U)-связный взвешаный граф, взвешаны рёбра с матрицей весов cij. D1(N1,U1),D2(N2,U2),…,Dk(Nk,Uk)-остовный лес.
N=∪Ni Ni≠Æ Ni∩Nj=Æ i≠j
(p,l)-ребро исходного графа такое, что pЄN1, l∉N1. Среди подобных рёбер (p,l) имеет минимальный вес. Тогда среди всех остовных деревьев D, включавших {Di} в качестве остовного леса, найдётся дерево минимального веса, содержащее ребро (p,l).
Доказательство. Предположим противное: описаное в теореме остовное дерево Т не содержит ребро (p,l). Добавим в дерево Т ребро (p,l). При этом новый граф Т’ имеет в точности 1 цикл с ребром (p,l). В этом цикле обязательно найдётся ребро (α,β) такое, что αЄD1, β∉D1. Возможны 2 случая:
1.Вес ребра (p,l) совпадает с весом ребра (α,β). В этом случае выбрасываем ребро (α,β) и тогда новый граф Т’’ совпадает с деревом, описанным в условии теоремы.
2. Если ребро (α,β)> веса ребра (p,l). Cα,β>cp,l. Тогда исходное дерево Т не является минимальным по весу. Противоречие получено. Теорема доказана.
Алгоритм Краскала-алгоритм решения задачи по минимальным остовных деревьев.
1.Среди все рёбер графа G находим ребро минимального веса, удаляем его из графа и заносим его в строящееся остовное дерево.
2.Если в строющемся дереве n-1 вершин, где n-колич вершин остовного дерева, то оптимальное ребро построено. Конец работы алгоритма. Иначе переходим на шаг 3.
3. Среди всех рёбер графа G таких, что добавление любого из них в строющееся дерево не приводит к появлению цикла. Выбираем ребро минимального веса. Удаляем его из цикла и заносим его в дерево. Переходим на шаг 2.
Алгоритм Прима.
1.Выбираем произвольную вершину i. Среди всех рёбер, инцидентных этой вершине, выбирается ребро минимального веса, удаляется из графа и заносится в остовное дерево.
2. Если в дереве n-1 ребро, где n-количество вершин исходного графа, то оптимальное дерево построено. Конец работы алгоритма. Иначе переходим на шаг 3.
3.Среди всех рёбер графа G, таких, что в каждой из них инцидентна в точности одной вершине, вошедшей в строющееся дерево находим ребро минимального веса, удаляем его из графа и заносим его в строющееся дерево. Переходим на шаг 2.
39. Задача о максимальном потоке и минимальном разрезе. Алгоритм Форда-Фалкерсона.
Задан вершинный орграф G=(N,U). Взвешены дуги. Дуге (I,j) приписано неотрицательно число ci≥0, которое называется пропускной способностью дуги. Граф, лежащий в основе орграфа G-связный.
Выделены 2 вершины s и t. S-источник, t-сток. Такие орграфы-сети.
Потоком по сети G называется множество чисел xij таких, что:
1.0≤xij≤cij
2.Закон сохранения потока в вершине: ∀k≠s,t выполняется, что суммарный поток втекающей вершины равен суммарному потоку вытекающему из неё.
3.Закон сохранения потока в сети:поток, втекающий в сеть через вершину s=потоку вытекающему из сети через вершину t.
Задача состоит в том, что необходимо максимилизировать величину потока из сети при ограничении 1,3.
Идея решения задачи о макс потоке следующая:последовательно находить всевозможные пути из s в t и для каждого такого пути макс поток вычислять.
Задача о мини разрезе. Пусть У⊆Nи пусть SЭУ и t∉У.
Разрезом сети G(Y,Y) назыв множ таких рёбер (i,j) таких, что {iЄY, jЄY} или наоборот: {iЄY, jЄY}
Пропускной способностью разреза назыв величина с (У,У)=∑сij
(i,j)Є(Y,Y)
Задача о мин разрезе формулируется след образом: с(У,У) минилизировать -> min(Y,Y). Мин ищется по всевозможным разрезам, выделяющие источник по стокам.
Алгоритм Форда-Фолкерсона.
I этап. Выбираем некоторый начальный поток. В качестве такого потока можно взять xij=0.Вершина S получает метку(S,∞). Это значит, что мы пытаемся засунуть в сеть бесконечный по величине макс поток. Вершина S при этом считается помеченной, но не просмотренной. Все остальные вершины не помечены.
II этап. Выбираем произвольную помеченную и не просмотренную вершину и пытаемся пометить из неё все смежные с ней вершины. Предположим, выбранная вершина k и пытаемся пометить смежну к ней вершину i. Возможны 2 случая:
1.в исходном графе имеется дуга (k,i)
2.в исходном графе имеется дуга (i,k)
Рассмотрим первый случай. Имеем 2 случая:
1.Если cki>xki, то по дуге (k,i) ток можно увеличить на величину ε^+(i)=min{cki-xki,ε(k)}
2.Если сki=xki, то дуга в этом случае дуга назыв насыщенной вершину i пометить из вершины k нельзя и поток по этой дуге увеличить нельзя. Рассмотрим II случай. Здесь также 2 случая:
1.xik>0, то поток по дуге (i,k) можно уменьшить на величину ε^(-)(i)=min(xik,ε(k)). При этом, вообще говоря, поток по сети увеличивается.
2.Если xik=0, то вершину i из вершины k пометить нельзя. Независимо от того, удалось ли пометить все смежные с k вершины, вершина к считается помеченной и просмотренной. Процедура расстановки пометки продолжается до тех пор, пока не будет помечена вершина Е. Если вершину Е удаётся пометить, то переходим на след этап. В противном случае текущий поток является макс и при этом определяется мин разрез.
III этап. Начиная из вершины t, по меткам определяем путь из s в t. Пусть вершина t имеет метку M(t)=(in,ε^+(t)), вершина M(in)=(in-1,…), M(in-1)=(in-2,…) и тем самым будет определён полупуть (S=i1,i2,…,in,t), дуговые потоки для этого полупути изменяем на величину ε(t). В случае ориентации дуги из s в t, воток по дуге увеличиваем на величина ε(t), в случае обратного-уменьшаем на величину ε(t). После этого все метки, за исключением метки вершины s, вытираются, все вершины, кроме вершины s считаются непомеченными, а вершина s помеченной и не просмотренной. Возвращаемся на II этап.
40. Теорема Форда-Фалкерсона
Теорема Форда-Фалкерсона.Величина макс потока в сети=пропускной способности мин разреза, отделяющего источник от стока.
Следствие. Решая задачу о макс потоке, мы решаем задачу о мин разрезе и наоборот.
При решении этой пары задач, используется система меток: помечаются вершины, метка вершины i(M(i)) состоит из двух частей:(M(i)=(k,ε^ 
(i))), k-указывает: из какой вершины была помечена вершина i, если ε^+(i), то это указывает, что по дуге (k,i) можно увеличить поток на величину ε(i), если ε^-(i)-уменьшить поток на величину ε(i). В процессе работы алгоритма, каждая из вершин может находиться в одном из трёх состояний:
1.Вершина не помечена
2.вершина помечена и не просмотрена
3.вершина помечена и просмотрена