Связность в графах

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

Предварительно рассмотрим простую задачу.

Пусть трубопровод состоит из трех труб различного сечения с пропускными способностями 10 л/мин, 5 л/мин, 7 л/мин.

Вполне очевидно, что пропускная способность системы равна 5 л/мин, т.е. совпадает с наименьшей пропускной способностью труб.

10 л/мин 5 л/мин 7 л/мин

Рис. 48. Трубопровод

Пусть имеется некоторый взвешенный орграф G (V, E). Выделим в этом графе некоторые две вершины s, t, которые назовем источником и стоком.

Будем рассматривать веса как пропускную способность дуги q . Количество фактически проходящих единиц по дуге обозначим через z . z - поток, проходящий через дугу i j. Ясно, что q z .

Пусть к источнику S прибывает поток Р. Для того, чтобы сеть функционировала нормально, должно быть Р = Р , Р - Р= 0. Требуется организовать перемещение так, чтобы величина Р была максимальной.

Разделим множество вершин на подмножества Х и Х . Рассмотрим дугу (VV ) и отнесем вершину V к Х , а V к Х . Таким образом, для данного разбиения (Х, Х ) концы дуг принадлежат разным подмножествам. Такое разбиение называется разрезом, отделяющим вершину V от V . Совокупность потоков, протекающих через ХХ, называется потоком разреза.

6.8.1. Теорема Форда – Фолкерсона

Теорема. Максимальный поток сети равен минимальному потоку разреза.

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

Так как максимальный поток обязательно пройдет по дуге минимального разреза, то это будет означать, что он совпадает с минимальным потоком разреза. Это будет выполняться, если выполняется условия: Р = Р , т.е. Р - Р_t = 0.

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

Будем последовательно строить разрезы, и назначать каждой вершине некоторое число – метку r по следующему правилу.

r= min (r, q _ij - z ), если z ≤ q и дуга исходит из вершины V , и r = z , при z >0, если дуга заходит в V .

Для определенности в метку будем включать указатель вершины, из которой мы пришли в вершину V , то есть метка будет выглядеть: + V,r, если V - вершина исхода; и - V, r, если V - вершина захода. Будем строить разрезы.

Включаем в разрез источник ─ вершину V ₁, присвоив ей метку r = ∞, и положив все потоки z = 0.

Просматриваем все смежные вершины, идущие в прямом направлении Γ+. Если им не присвоены метки, то присваиваем их

r=min (r,q-z ) (1)

Тем самым включаем эти вершины в подмножество Х₁.

Просматриваем все смежные вершины, идущие в обратном направлении Γ-. Если им не присвоены метки, то присваиваем их

r= z> 0 (2).

Тем самым включаем эти вершины в подмножество Х₁.

Проделаем это со следующей вершиной и со следующей, пока не дойдем до вершины t.

1). При этом, может оказаться, что вершина t попадает во множество Х . Это будет означать, что полученные нами потоки могут быть увеличены на некоторую величину в для дуг в прямом направлении, и уменьшены в обратном направлении. Для полученной цепи, связывающей сток и источник (вершины меток) полагаем потоки равными меткам.

Для дуг, идущих в прямом направлении найдем b₁ = min (q _ij - z ).

Для дуг, идущих в обратном направлении найдем b₂ = min z> 0.

Найдем b = min (b₁, b₂). Используя метки, строим цепь, связывающую сток с источником. Такие цепи называются аугментальными. Для дуг, идущих в прямом направлении, к имеющимся потокам прибавим величину b, и вычтем b из потоков в обратном направлении.

После этого стираем все метки и строим новые разрезы с новыми потоками.

2). Вершина t не попала в Х ₁. Это значит, что для дуг в прямом направлении имеем q _ij = z , а для дуг в обратном направлении

z .= 0. Иначе говоря, величина потока равна значению разреза, который и будет минимальным.

Т.к. пропускные способности дуг выражаются целыми числами, то в случае 1) мы увеличивали поток на некоторое целое число, значит рано или поздно получим максимальный поток. Это наступит тогда, когда не останется аугментальных цепей.

Таким образом, установлено существование минимального разреза. Теорема доказана. Заодно, получен алгоритм нахождения наибольшего потока.

Пример.

Граф задается матрицей смежности (пропускных способностей дуг).

	V1	V2	V3	V4	V5	V6	V7	V8	V9	V10
V1
V2
V3
V4
V5
V6
V7
V8
V9
V10

V₂ V₆ V₈ V₁₀

●

V1 ● V4

● ● ●

V₃ V₅ V₇ V₉

Рис. 49. Пример сети с 10 вершинами

Вершина V ₁ ─ источник, вершина V ₁₀ ─ сток. Строим разрезы.

Вершине V ₁присваиваем метку r ₁= ∞, положив все потоки z = 0.

Просматриваем вершину V 1.

Γ+ (V ₁) = { V₂, V₃ }.

Присваиваем вершине V ₂ метку + V₁, r₂= min (r₁,q₁₂- z₁₂) = = min (∞, 10 -0) =10. Метка V₂: + V₁, r₂ = 10.

Присваиваем вершине V ₃ метку + V₁, r₃= min (r₁,q₁₃- z₁₃) = = min (∞, 17 -0) =17. Метка V₃: + V₁, r₃ = 17.

Γ- (V ₁) – пусто.

Вершина V ₁ помечена и просмотрена.

Просматриваем вершину V ₂.

Γ+ (V ₂) = { V₄, V₆ }.

Присваиваем вершине V₄ метку + V₂, r₄= min (r₂, q₂₄- z₂₄) = min (10, 13 -0) =10. Метка V₄: + V₂, r ₄ = 10.

Присваиваем вершине V₆ метку + V₂, r₆= min (r₂, q₂₆- z₂₆) = min (10, 23 -0) =10. Метка V₆: + V₂, r₆ = 10.

Γ- (V₂) = { V ₁}. Но V₁ помечена.

Вершина V₂ помечена и просмотрена.

Просматриваем вершину V₃.

Γ+ (V3) = { V₄ }. Но V₄ помечена.

Γ- (V₃) = { V₁, V₅ }. Но V₁ помечена, а z₅₃ = 0..

Вершина V₃ помечена и просмотрена.

Просматриваем вершину V₄.

Γ+ (V₄) = { V₅ }.

Присваиваем вершине V₅ метку + V₄, r₅= min (r₄, q₄₅- z₄₅) = min (10, 5 -0) = 5. Метка V₅: + V₄, r₅ = 5.

Γ- (V₄) = { V₂, V₃ }. Но V₂ помечена, и V₃ помечена.

Вершина V₄ помечена и просмотрена.

Просматриваем вершину V₅.

Γ+ (V₅) = { V₇, V₃ }.

Присваиваем вершине V7 метку + V₅, r₇= min (r₅, q₅₇- z₅₇) = min( 5, 11 -0) = 5. Метка V₇: + V₅, r₇ = 5.

Вершина V₃ помечена.

Γ- (V₅) – { V₄, V₆ }. Но V₄ и V₆ помечены.

Вершина V₅ помечена и просмотрена.

Просматриваем вершину V₆.

Γ+ (V₆) = { V₅, V₇, V₈ }. Но V₅ и V₇ помечены. Присваиваем вершине V₈ метку + V₆, r₈= min (r₆, q₆₈- z₆₈) = min (10, 21 -0) =10. Метка V₈: + V₆, r₈ = 10.

Γ- (V₆) = { V₂ }. Но V₂ помечена.

Вершина V₆ помечена и просмотрена.

Просматриваем вершину V₇.

Γ+ (V₇) = { V₉, V₁₀ }.

Присваиваем вершине V₉ метку + V₇, r₉= min (r₇, q₇₉- z₇₉) = min (5, 8 - 0) =5. Метка V₉: + V₇, r₉ = 5.

Присваиваем вершине V₁₀ метку + V₇, r₁₀= min (r₇, q₇₁₀- z₇₁₀) = min (5, 11 - 0) = 5. Метка V₁₀: + V₇, r₁₀ = 5

Γ- (V₇) = { V₅, V₆ V₈ }. Но они помечены.

Вершина V₇ помечена и просмотрена.

Все вершины помечены. Получили цепь V₁₀, V₇, V₅, V₄, V₂, V₁.

Назначим новые потоки, учитывая, что b= 5.

Метка V₁₀: + V₇, r₁₀ = 5. Значит, поток z₇₁₀ = 0 + 5 =5.

Метка V₇: + V₅, r₇ = 5. Значит, поток z₅₇ = 0 + 5 =5.

Метка V₅: + V₄, r ₅ = 5. Значит, поток z₄₅ = 0 + 5 =5..

Метка V₄: + V₂, r ₄ = 10. Значит, поток z₂₄ = 0 + 5 =5.

Метка V₂: + V₁, r₂ = 10. Значит, поток z₁₂ = 0 + 5 = 5.

Остальные потоки равны 0.

Стираем все метки и начинаем с начала строить разрезы с новыми потоками.

Вершине V₁ присваиваем метку r₁ = ∞.

Просматриваем вершину V₁.

Γ+ (V₁) = { V₂, V₃ }.

Присваиваем вершине V₂ метку + V₁, r₂= min (r₁, q₁₂- z₁₂) = min (∞, 10 -5) = 5. Метка V₂: + V₁, r₂ = 5.

Присваиваем вершине V₃ метку + V₁, r₃= min (r₁, q₁₃- z₁₃) = min( ∞, 17 -0) = 17. Метка V₃: + V₁, r₃ = 17.

Γ- (V₁) – пусто.

Вершина V₁ помечена и просмотрена.

Просматриваем вершину V₂.

Γ+ (V₂) = { V₄, V₆ }.

Присваиваем вершине V₄ метку + V₂, r₄= min (r₂, q₂₄- z₂₄) = min (5, 13 -5) = 5. Метка V₄: + V₂, r₄ = 5.

Присваиваем вершине V₆ метку + V₂, r₆= min (r₂, q₂₆- z₂₆) = min (5, 23 -0) = 5. Метка V₆: + V₂, r₆ = 5.

Γ- (V₂) = { V₁ }. Но V₁ помечена.

Вершина V₂ помечена и просмотрена.

Просматриваем вершину V₃.

Γ+ (V₃) = { V₄ }. Но V₄ помечена.

Γ- (V₃) = { V₁, V₅ }. Но V₁ помечена, а z₅₃ = 0..

Вершина V₃ помечена и просмотрена.

Просматриваем вершину V₄.

Γ+ (V₄) = { V₅ }.

Присваиваем вершине V₅ метку + V₄, r₅= min (r₄, q₄₅- z₄₅) = min (5, 5 -5) = 0. Значит, этой вершине метку не присваиваем.

Γ- (V₄) ={ V₂, V₃ }. Но V₂ помечена, и V₃ помечена.

Вершина V₄ помечена и просмотрена.

Т.к. вершина V₅ не помечена, то её пока не просматриваем.

Просматриваем вершину V₆.

Γ+ (V₆) = { V₅, V₇, V₈ }.

Присваиваем вершине V₅ метку + V₆, r₅= min (r₆, q₆₅- z₆₅) = min (5, 14 - 0) = 5. Метка V₅: + V₆, r₅ = 5.

.Присваиваем вершине V₇ метку + V₆, r₇= min (r₆, q₆₇- z₆₇) = min (5, 10 - 0) = 5 Метка V₇: + V₆, r₇ = 5.

Присваиваем вершине V₈ метку + V₆, r₈= min (r₆, q₆₈- z₆₈) = min (5, 21 - 0) = 5. Метка V₈: + V₆, r₈ = 5.

Γ- (V₆) = { V₂ }. Но _V2 помечена.

Вершина V₆ помечена и просмотрена.

Просматриваем вершину V₅.

Γ+ (V₅) = { V₇, V₃ }. Но V₃ и V₇ помечены.

Γ- (V₅) – { V₄, V₆ }. Но V₄ и V₆ помечены.

Вершина V₅ помечена и просмотрена.

Просматриваем вершину V₇.

Γ+ (V₇) = { V₉, V₁₀ }.

Присваиваем вершине V₉ метку + V₇, r₉= min (r₇, q₇₉- z₇₉) = min( 5, 8 - 0) =5. Метка V₉: + V₇, r₉ = 5.

Присваиваем вершине V₁₀ метку + V₇, r₁₀= min (r₇, q₇₁₀- z₇₁₀)= min (5, 11 - 5) = 5.

Все вершины помечены.

Получили цепь V₁₀, V₇, V₆, V₂, V₁.

Назначим новые потоки, учитывая, что b = 5.

Метка V₁₀: + V₇, r₁₀ = 5. Значит, поток z₇₁₀ = 5 + 5 = 10.

Метка V₇: + V₆, r₇ = 5. Значит, поток z₆₇ = 0 + 5 = 5.

Метка V₆: + V₂, r₅ = 5. Значит, поток z₂₆ = 0 + 5 = 5.

Метка V₂: + V₁, r₂ = 10. Значит, поток z₁₂ = 5 + 5 = 10.

Потоки имеют вид

V₂ 5 V₆ V₈ V₁₀

● ● ● ●

10 5

V₁ ● ● V₄ 5 10

● ● 5 ● ●

V₃ V₅ V₇ V₉

Рис. 50. Распределение потоков после второй итерации

Стираем все метки и начинаем с начала строить разрезы с новыми потоками.

Вершине V₁ присваиваем метку r₁ = ∞.

Просматриваем вершину V₁.

Γ+ (V₁) = { V₂, V₃ }.

Присваиваем вершине V₂ метку + V₁, r₂= min (r₁, q₁₂- z₁₂) = min (∞, 10 - 10) = 0. значит, вершине V₂ метка не присваивается.

Присваиваем вершине V₃ метку + V₁, r₃= min (r₁, q₁₃- z₁₃) = min (∞, 17 - 10) = 1. Метка V₃: + V₁, r₃ = 17.

Γ- (V₁) – пусто.

Вершина V₁ помечена и просмотрена.

Т.к. вершина V₂ не помечена, то её пока не просматриваем.

Просматриваем вершину V₃.

Γ+ (V₃) = { V₄ }.

Присваиваем вершине V₄ метку + V₃, r₄= min (r₄, q₃₄- z₃₄) = min (17, 11 - 0) = 11. Метка V₄: + V₃, r₄ = 11.

Γ- (V₃) = { V₁, V₅ }. Но V₁ помечена, а z₅₃ = 0.

Вершина V₃ помечена и просмотрена.

Просматриваем вершину V₄.

Γ+ (V₄) = { V₅ }.

Присваиваем вершине V₅ метку + V₄, r₅= min (r₄, q₄₅- z₄₅) = min( 11, 5 - 5) = 0. Значит, этой вершине метку не присваиваем.

Γ- (V₄) = { V₂, V₃ }. Но V₃ помечена.

Присваиваем вершине V₂ метку - V₄, r₂= z₂₄ = 5.

Метка V2: - V₄, r₂ = 5.

Вершина V₄ помечена и просмотрена.

Просматриваем вершину V₂.

Γ+ (V₂) = { V₄, V₆ }.

Но V₄ помечена.

Присваиваем вершине V₆ метку + V₂, r₆= min (r₂, q₂₆- z₂₆) =

min (5, 23 - 5) = 5. Метка V₆: + V₂, r₆ = 5.

Γ- (V₂) = { V₁ }. Но V1 помечена.

Вершина V₂ помечена и просмотрена.

Т.к. вершина V₅ не помечена, то её пока не просматриваем.

Просматриваем вершину V₆.

Γ+ (V₆) = { V₅, V₇, V₈ }.

Присваиваем вершине V₅ метку + V₆, r₅= min (r₆, q₆₅- z₆₅) = min (5, 14 - 5) = 5.

Метка V₅: + V₆, r₅ = 5.

Присваиваем вершине V₇ метку + V₆, r₇= min (r₆, q₆₇- z₆₇) = min (5, 10 - 5) = 5. Метка V₇: + V₆, r₇ = 5.

Присваиваем вершине V₈ метку + V₆, r₈= min (r₆, q₆₈- z₆₈) = min (5, 21 - 0) = 5. Метка V₈: + V₆, r₈ = 5.

Γ- (V₆) = { V₂ }. Но V₂ помечена.

Вершина V₆ помечена и просмотрена.

Просматриваем вершину V₅.

Γ+ (V₅) = { V₇, V₃ }. Но V₃ и V₇ помечены.

Γ- (V₅) = { V₄, V₆ }. Но V₄ и V₆ помечены.

Вершина V₅ помечена и просмотрена.

Просматриваем вершину V₇.

Γ+ (V₇) = { V₉, V₁₀ }.

Присваиваем вершине V₉ метку + V₇, r₉= min (r₇, q₇₉- z₇₉) = min (5, 8 - 0) = 5. Метка V₉: + V₇, r₉ = 5.

Присваиваем вершине V₁₀ метку + V₇, r₁₀= min (r₇, q₇₁₀- z₇₁₀) = min (5,11- 10) = 1.

Γ- (V₇) = { V₅, V₆ }. Но V₄ и V₆ помечены.

Все вершины помечены.

Получили цепь V₁₀, V₇, V₆, V₂, V₄, V₃, V₁.

Имеем b₁ = 1, b₂ = 5. Тогда b = min (b₁,b₂) = 1.

Назначим новые потоки, учитывая, что b = 1.

Метка V₁₀: + V₇, r₁₀ = 5. Значит, поток z₇₁₀ = 10 + 1 = 11.

Метка V₇: + V₆, r₇ = 5. Значит, поток z₆₇ = 5 + 1 = 6.

Метка V₆: + V₂, r₅ = 5. Значит, поток z₂₆ = 5 + 1 = 6.

Метка V₂: - V₄, r₂ = 5. Значит, поток z₂₄ = 5 - 1= 4.

Метка V₄: + V₃, r₄ = 11. Значит, поток z₃₄ = 0 + 1 = 1.

Метка V₃: + V₁, r₃ = 17. Значит, поток z₁₃ = 0 + 1 = 1.

Потоки имеют вид

V₆

V₂ 6 V₈ V₁₀

10 6

V₁ 4

V₄

1 5 11

1 5

V₃ V₅ V₇ V₉

Рис. 51. Распределение потоков после третьей итерации

Стираем все метки и начинаем с начала строить разрезы с новыми потоками.

Вершине V₁ присваиваем метку r₁ = ∞.

Просматриваем вершину V₁.

Γ+ (V₁) = { V₂, V₃ }.

Присваиваем вершине V₂ метку + V₁, r₂ = min (r₁, q₁₂- z₁₂) = min (∞,10 - 10) = 0. Значит, вершине V₂ метка не присваивается.

Присваиваем вершине V₃ метку + V₁, r₃= min (r₁, q₁₃- z₁₃) = min (∞, 17 - 1) = 16. Метка V₃: + V₁, r₃ = 16.

Γ- (V₁) – пусто.

Вершина V₁ помечена и просмотрена.

Т.к. вершина V₂ не помечена, то её пока не просматриваем.

Просматриваем вершину V₃.

Γ+ (V₃) = { V₄ }.

Присваиваем вершине V₄ метку + V₃, r₄= min (r4, q₃₄- z₃₄) = min (17, 11 - 1) = 10. Метка V₄: + V₃, r₄ = 10.

Γ- (V₃) = { V₁, V₅ }. Но V₁ помечена, а z₅₃ = 0.

Вершина V₃ помечена и просмотрена.

Просматриваем вершину V₄.

Γ+ (V₄) = { V₅ }.

Присваиваем вершине V₅ метку + V₄, r₅= min (r₄, q₄₅- z₄₅) = min (11, 5 - 5) = 0. Значит, этой вершине метку не присваиваем.

Γ- (V₄) ={ V₂, V₃ }. Но V₃ помечена.

Присваиваем вершине V₂ метку - V₄, r₂= z₂₄ = 4.

Метка V₂: - V₄, r₂ = 4.

Вершина V₄ помечена и просмотрена.

Просматриваем вершину V₂.

Γ+ (V2) = { V₄, V₆ }.

Но V₄ помечена.

Присваиваем вершине V₆ метку + V₂, r₆= min (r₂, q₂₆- z₂₆) =

min (4, 23 - 6) = 4 Метка V₆: + V₂, r₆ = 4.

Γ- (V₂) = { V₁ }. Но V₁ помечена.

Вершина V₂ помечена и просмотрена.

Т.к. вершина V₅ не помечена, то её пока не просматриваем.

Просматриваем вершину V₆.

Γ+ (V₆) = { V₅, V₇, V₈ }.

Присваиваем вершине V5 метку + V₆, r₅= min (r₆, q₆₅- z₆₅) = =min (6, 14 - 6) = 6. Метка V₅: + V₆, r₅ = 6.

Присваиваем вершине V₇ метку + V₆, r₇= min (r₆, q₆₇- z₆₇) =

min (6, 10- 6) = 4. Метка V₇: + V₆, r₇ = 4.

Присваиваем вершине V₈ метку + V₆, r₈= min (r₆, q₆₈- z₆₈) = min (6, 21 - 0) = 6. Метка V₈: + V₆, r₈ = 6.

Γ- (V₆) = { V₂ }. Но V₂ помечена.

Вершина V₆ помечена и просмотрена.

Просматриваем вершину V₅.

Γ+ (V₅) = { V₇, V₃ }. Но V₃ и V₇ помечены.

Γ- (V₅) = { V₄, V₆ }. Но V₄ и V₆ помечены.

Вершина V₅ помечена и просмотрена.

Просматриваем вершину V₇.

Γ+ (V₇) = { V₉, V₁₀ }.

Присваиваем вершине V₉ метку + V₇, r₉= min (r₇, q₇₉- z₇₉) = min (4, 8 - 0) = 4. Метка V₉: + V₇, r₉ = 4.

Присваиваем вершине V₁₀ метку + V₇, r₁₀= min (r₇, q₇₁₀- z₇₁₀) = min (4, 11- 11) = 0. Значит, вершине V₁₀ метка не присваивается.

Γ- (V₇) = { V₅, V₈, V₆ }. Но V₅, V₈ и V₆ помечены.

Вершина V₇ помечена и просмотрена.

Просматриваем вершину V₈.

Γ+ (V₈) = { V₇ } Вершина V₇ помечена.

Γ- (V₈) = { V₆, V₁₀ }. Но V₆ помечен, а z_{10 8} = 0.

Вершина V₈ помечена и просмотрена.

Просматриваем вершину V₉^.

Γ+ (V₉) = { V10 }.

Присваиваем вершине V₁₀ метку + V₉, r₁₀= min (r₉, q₉₁₀- z₉₁₀) = min (4, 23 - 0) = 4. Метка V₁₀: + V₉, r₁₀ = 4.

Все вершины помечены.

Получили цепь V₁₀, V₉,V₇, V₆, V₂, V₄, V₃, V₁.

Имеем b₁ = 4, b ₂ =4. Тогда b = min (b ₁, b ₂) = 4.

Назначим новые потоки, учитывая, что b = 4.

Метка V₁₀: + V₉, r₁₀ = 4. Значит, поток z₉₁₀ = 0 + 4 = 4.

Метка V₉: + V₇, r₉ = 4. Значит, поток z₇₉ = 0 + 4 = 4.

Метка V₇: + V₆, r₇ = 5. Значит, поток z₆₇ = 6 + 4 = 10.

Метка V₆: + V₂, r₅ = 5. Значит, поток z₂₆ = 6 + 4 = 10.

Метка V₂: - V₄, r₂ = 5. Значит, поток z₂₄ = 4 – 4 = 0.

Метка V₄: + V₃, r₄ = 11. Значит, поток z₃₄ = 1 + 4 = 5.

Метка V₃: + V₁, r₃ = 17. Значит поток z₁₃ = 1 + 4 = 5.

Потоки имеют вид

V₂ 10 V₆ V₈ V₁₀

V₁

10 11 4

5 5 V₄

V₃ 5

V₅ 5 4 V₉

V₇

Рис. 52. Распределение потоков после четвертой итерации

Стираем все метки и начинаем вновь строить разрезы с новыми потоками.

Вершине V₁ присваиваем метку r₁ = ∞.

Просматриваем вершину V₁.

Γ+ (V₁) = { V₂, V₃ }.

Присваиваем вершине V₂ метку + V₁, r₂= min (r₁, q₁₂- z₁₂) = min (∞, 10 – 10) = 0. Значит, вершине V₂ метка не присваивается.

Присваиваем вершине V₃ метку + V₁, r₃= min (r₁, q₁₃- z₁₃) = min (∞, 17 - 5) = 12.

Метка V₃: + V₁, r₃ = 12.

Γ- (V₁) – пусто.

Вершина V₁ помечена и просмотрена.

Т.к. вершина V₂ не помечена, то её пока не просматриваем.

Просматриваем вершину V₃.

Γ+ (V₃) = { V₄ }.

Присваиваем вершине V₄ метку + V₃, r₄= min (r₄, q₃₄- z₃₄) = min (12, 11 - 5) = 6.

Метка V₄: + V₃, r₄ = 6.

Γ- (V₃) = { V₁, V₅ }. Но V₁ помечена, а z₅₃ = 0.

Вершина V₃ помечена и просмотрена.

Просматриваем вершину V₄.

Γ+ (V₄) = { V₅ }.

Присваиваем вершине V₅ метку + V₄, r₅= min (r₄, q₄₅- z₄₅) = min (11, 5 - 5) = 0. Значит, этой вершине метку не присваиваем.

Γ- (V4) ={ V₂, V₃ }. Но V₃ помечена, а z₂4 = 0.

Вершина V₄ помечена и просмотрена.

Дальнейшая расстановка меток невозможна. Значит, полученный поток является оптимальным. Он равен 15.

Пусть задан граф G, у которого р – вершин и q – ребер. Если для двух вершин существует цепь, то они называются связными. Граф называется связным, если у него все вершины связны. Если граф может быть задан в виде объединения нескольких подграфов, то каждый такой подграф называется компонентой связности, а количество компонент обозначается буквой k.

Рис. 53. G = G₁ U G_2, k =2

●

Рис. 54. Несвязный граф, k =3

Теорема. Пусть имеется три инварианта: р, q и k. Тогда

.

Доказательство по индукции:

1) Докажем, что р – k q (1)

а). Пусть р = 1; q = 0; тогда k= 1 и р – k = 1- 1 = 0 = q ─ верно.

б). Пусть р = 2.

При k = 2, получим q = 0 и р – k = 0 = q. При k = 1: получим q= 1 и р – k = 1 = q.

Слдовательно, неравенство (1) справедливо.

в). Пусть неравенство (1 ) справедливо для некоторого р. Покажем, что оно справедливо и для р= р + 1, то есть мы должны показать, что справедливо р-kq (2) где q - количество ребер, получившихся после добавления вершины, а k - число компонент нового графа.

В самом деле:

При р= р+ 1, k= k + 1 и q = q получим р - k = р + 1- k - 1 = р- k (в силу неравенства (1) ) q = q .

Если же при р= р + 1 имеем q= q + n (n 1) и k= k, то р - k= р+ 1 - k (в силу неравенства (1)) q + 1 q+ n= q.

Неравенство (2) доказано.

2) Докажем, что q (3)

а). Пусть р = 1; q = 0; k = 1. Тогда = 0 = q.

Пусть неравенство (3) справедливо для некоторого р. Докажем, что оно справедливо и для р= р + 1, т.е.

q (4)

б). Пусть р= р + 1; q= q и k=k + 1. (*)

Тогда

= = = q = q

в). Пусть р= р + 1; q= q + 1 и k=k. Тогда

= = (подставляя (*)

и раскрывая скобки) =

+1 (в силу неравенства (3)) q + 1= q .

Что и требовалось доказать.

Дата добавления: 2014-01-06