58
достаточные условия его существования. Необходимые условия существования неизвестны за исключением некоторых особых типов графов.
Приведём два достаточных признака, простых в практическом применении.
Пусть дан связный н-граф G без петель, имеющий 𝑛 ≥ 3 вершин.
Теорема. Если для любых двух несмежных вершин 𝑢 и 𝑣 графа G выполняется условие 𝜌(𝑢) + 𝜌(𝑣) ≥ 𝑛, то в G существует гамильтонов цикл.
Следствие. Если для любой вершины 𝑣 графа G выполняется условие 𝜌(𝑣) ≥ 𝑛/2, то в G существует гамильтонов цикл.
П р и м е р 3.3.2 - Полный граф K5(см. рисунок 3.1.10) является как эйлеровым, так и гамильтоновым, так как выполняются необходимые и достаточные условия эйлеровости и достаточные условия гамильтоновости:
число вершин 𝑛 = 5, произвольно обозначив вершины через a, b, c, d, e, имеем 𝜌(𝑎) = 𝜌(𝑏) = 𝜌(𝑐) = 𝜌(𝑑) = 𝜌(𝑒) = 4 и для любых двух вершин графа выполняется 𝜌(𝑢) + 𝜌(𝑣) = 8 > 5, где 𝑢, 𝑣 ∈ {𝑎, 𝑏, 𝑐, 𝑑, 𝑒}.
П р и м е р 3.3.3 - Для графа на рисунке 3.3.3 б), число вершин которого 𝑛 = 6, не выполняется достаточное условие существования гамильтонова цикла: например, 𝜌(1) + 𝜌(3) = 4 < 6, однако, такой цикл в графе существует, это, например, цикл 1, 2, 4, 5, 3, 6, 1. Таким образом, этот граф как эйлеров, так и гамильтонов.
59
2. Диаметром графа G (обозначается d(G)) называется максимальный из всех эксцентриситетов: d(G) = max{𝑒(𝑣) | 𝑣 ∈ V}.
3. Радиусом графа G (обозначается r(G)) называется минимальный из всех эксцентриситетов: r(G) = min {𝑒(𝑣) | 𝑣 ∈ V}.
4. Вершина v называется периферийной, если 𝑒(𝑣) = d(G); Вершина 𝑣 называется центральной, если 𝑒(𝑣) = r (G). Множество всех центральных вершин графа называется его центром.
П р и м е р 3.4.1 - Рассмотрим граф на рисунке 3.4.1.
D=
0 1 1 1 2
1 0 2 1 1
1 2 0 2 3
1 1 2 0 1
2 1 3 1 0
- матрица расстояний графа.
Рисунок 3.4.1
Наибольшее число в строке - это эксцентриситет соответствующей вершины, поэтому e(1) = 3, e(2) = 2, e(3) = 3, e(4) = 2, e(5) = 2. Диаметр графа d(G)=3, как наибольший из эксцентриситетов, радиус - r(G)= 2, как наименьший. Вершины 1, 3 – периферийные, вершины 2,4,5 – центральные, множество {2,4,5} – центр графа.
Задача нахождения центральных вершин часто возникает на практике, например, если вершинам графа соответствуют районы города, рёбрам – дороги между ними. Требуется оптимально разместить учреждения общего пользования (больницы, рынки, и т.д.). Очевидно, что в этом случае оптимизация заключается в минимизации расстояний от самых отдалённых районов до этих учреждений. Следовательно, местами размещения должны быть центральные вершины графа. Реальные задачи от этих идеальных отличаются тем, что приходится учитывать и другие обстоятельства:
расстояние между районами, стоимость проезда, время проезда и т.д. Для учёта различных обстоятельств используют взвешенные графы.
Определение. Пусть дан граф G (V, E). Пометкой (или распределением меток) графа называется пара функций: f: V → Sv и g: E → SE, где Sv, SE – множества меток вершин и рёбер (дуг). Четвёрка (V, E, f, g) называется взвешенным или помеченным графом.
Если 𝑣 V, то f (𝑣) – вес вершины 𝑣, если e ∈ E, то g(e) – вес дуги e. Часто бывают помеченными только вершины или только рёбра (дуги).
60
П р и м е р 3.4.2 - На рисунке 3.4.2 изображён помеченный граф (V, E, f, g), представляющий схему автомобильных дорог с указанием их длины.
Рисунок 3.4.2
μV1 - Кокчетав, V2 - Экибастуз, V3 - Семипалатинск, V4 - Караганда.
V={V1, V2, V3, V4} , Е={{V1, V2 },{V2, V3}, { V1, V4},{ V2, V4}}, f : V→Sv , Sv – множество городов, f (V1)= Кокчетав, f (V2)= Экибастуз, f (V3)=
Семипалапинск, f (V4) = Караганда. g: E →SE , SE – множество расстояний,
g({V1, V2})=400, g({V2, V3})=600, g({V1, V4})=250, g({V2, V4})=300.
Информацию о весах ребер (дуг) во взвешенном графе можно представлять в виде матрицы весов W=(wij), где wij – вес ребра (дуги) (𝑣𝑖, 𝑣𝑗), если эта дуга существует, если не существует, то соответствующий вес обозначают 0 или ∞ (0 - если i = j; ∞ - если вершины 𝑣𝑖 и 𝑣𝑗 не смежные). Для графа из примера 3.4.2 матрица весов имеет вид: W=
0 400 250
400 0 600 300
600 0
250 300 0
.
Для взвешенных графов также вводятся понятия взвешенных расстояния, эксцентриситета и т.д. Пусть G(V,E) взвешенный граф, в котором вес каждой дуги (𝑣𝑖, 𝑣𝑗) есть некоторое число μ (𝑣𝑖, 𝑣𝑖+1), 𝑣𝑖, 𝑣𝑖+1 ∈ V.
1. Весом маршрута (𝑣1𝑣𝑛+1) называется число μ = ∑𝑛𝑖=1μ (𝑣𝑖, 𝑣𝑖+1).
2. Взвешенным расстоянием dw(𝑣1, 𝑣𝑛+1) между вершинами 𝑣1 и 𝑣𝑛+1 называется минимальный из весов 𝑣1𝑣𝑛+1 маршрутов.
3. Кратчайшим маршрутом между 𝑣1 и 𝑣𝑛+1 называется маршрут, вес которого равен dw(𝑣1, 𝑣𝑛+1).
4. Взвешенным эксцентриситетом вершины 𝑣 (обозначается 𝑒𝑤(𝑣)) называется число 𝑒𝑤(𝑣) = max{dw(𝑣, 𝑢) | 𝑢 ∈V}.
5. Взвешенной центральной вершиной графа G называется вершина 𝑣 , для которой 𝑒𝑤(𝑣) = min{𝑒𝑤(𝑢) | 𝑢 ∈V}.
6. Взвешенным радиусом графа G (обозначается rw (G)) называется взвешенный эксцентриситет центральной вершины.
61
Нахождение кратчайших маршрутов (путей)
Существуют различные способы (алгоритмы) определения кратчайших маршрутов. Выбор каждого из них зависит от условий задачи (например, весы рёбер отрицательные или нет), от способа решения (вручную или на компьютере) и т.д.
Рассмотрим алгоритм Дейкстры, который можно использовать только для взвешенных графов с неотрицательными весами всех рёбер. Этот алгоритм можно встретить в различных вариантах, например, с использованием и без матрицы весов, для применения в компьютере и т.д. Мы рассмотрим два варианта алгоритма Дейкстры (с использованием и нет матрицы весов).
Алгоритм Дейкстры 1.
Пусть G (V, E) – взвешенный граф, имеющий n вершин и W=(wij), – его матрица весов (𝑤𝑖𝑗 > 0). Пусть требуется найти взвешенное расстояние от фиксированной вершины vі (она называется источником) до некоторой другой вершины (вообще по алгоритму Дейкстры 1 находят сразу расстояния от источника до всех остальных вершин).
Обозначим Т1 множество вершинV \ {𝑣𝑖} , т.е. Т1 – это множество всех вершин Vбез источника. Обозначим D(1)=(d1(1) , d2(1), …, dn(1)), где di(1)=0, dj(1)= wij (i ≠ j), т.е. D(1) – это і-ая строка в матрице весов.
Пусть на шаге S уже определены множества вершин TS и строка D(S)=(d1(S) , d2(S), …, dn(S)). Наша задача перейти от TS к TS+1 и от D(S) к D(S+1). Выберем в TS вершину vj такую, что dj(S)=min{ dk(S)/ vk TS}. Положим TS+1 =
= TS\{vj}, D(S+1)=( d1(S+1),…,dn(S+1)), где 𝑑𝑘(𝑆+1) = 𝑑𝑘(𝑆), если 𝑣𝑘 ∉ 𝑇𝑆+1,
𝑑𝑘(𝑆+1) = 𝑚𝑖𝑛{ 𝑑𝑘(𝑆), 𝑑𝑗(𝑆)+ 𝑤𝑗𝑘} , если 𝑣𝑘 ∈ 𝑇𝑆+1.
На шаге S = n -1 получим строку D(n-1)=( d1(n-1), d2(n-1)…, dn(n-1)), в которой dj(n-1) равно взвешенному расстоянию от вершины 𝑣𝑖до вершины 𝑣𝑗:
d j(n-1)=dw(𝑣𝑖, 𝑣𝑗).
П р и м е р 3.4.3 - Рассмотрим граф на рисунке 3.4.3.
Рисунок 3.4.3
W=
0 4 2 10
4 0 7
2
2 0
7
7 0
3 6
10 2 7 3 0 5
6 5 0
- матрица весов.
62
Пусть требуется найти кратчайшие взвешенные расстояния от вершины A (источник) до остальных вершин. V={A, B, C, D, E, F} – множество вершин.
Будем полагать, что min (a, ∞) = a, min (∞, ∞) = ∞, a+∞ = ∞, ∞+∞ = ∞.
1 шаг. А- источник, T1 = V − {A} = {B, C, D, E, F}, 𝐷(1) = (0, 5̂, 6̂ ,∞̂, ∞̂, ∞̂).
2 шаг. В D(1) выбираем среди элементов, отмеченных ^ (т.е. кроме элемента отвечающего источнику) наименьший, и подчёркиваем его. Из T1
убираем вершину, соответствующую подчёркнутому элементу (это В). Строим 𝑇2 = 𝑇1 − {𝐵} = {𝐶, 𝐷, 𝐸, 𝐹}. Для определения D делаем вспомогательную (2) запись: из матрицы W выписываем строку, соответствующую В, и прибавляем ко всем её элементам (кроме первого и второго) подчёркнутое число 5. Сравним полученные числа с соответствующими числами в D и в (1) D ставим на их (2) места наименьшие числа:
+ 5 0 3 7 2 10 5 5 5 5
8 12 7 15, 𝐷(2) = (0,5, 6̂, 12̂, 7̂, 15̂).
3 шаг. T3 =T2 −
C = D,E,F
, + 6 3 0 ∞ 7 ∞ 6 6 6∞ 13 ∞ , 𝐷(3) = (0,5,6,12̂, 7̂, 15̂).
4 шаг. T4 =T3−
E = D,F , + ∞ 2 7 ∞ 0 4 7 7∞ 11, 𝐷(4) = (0,5,6,12̂, 7, 11̂). 5 шаг. 𝑇5 = 𝑇4− {𝐹} = {𝐷}, + ∞ 10 ∞ 2 4 0
11
13 , 𝐷(5) = (0,5,6,12,7,11).
n = 6, n – 1 = 5, значит, это последний шаг. По виду D делаем (5) вывод, что взвешенные расстояния от вершины А до остальных вершин равны 𝑑𝑤(𝐴, 𝐴) = 0, 𝑑𝑤(𝐴, 𝐵) = 5, 𝑑𝑤(𝐴, 𝐶) = 6, 𝑑𝑤(𝐴, 𝐷) = 12, 𝑑𝑤(𝐴, 𝐸) = 7, 𝑑𝑤(𝐴, 𝐹) = 11.
Алгоритм Дейкстры 2
Этот алгоритм позволяет найти не только вес кратчайшего пути, но и сам путь, его иногда называют алогоритмом расстановки меток. Пусть требуется найти кратчайшее взвешенное расстояние и путь от вершины 𝑣1 до вершины 𝑣𝑛. Каждой вершине поставим в соответствие пару (метку) (∞, 0). Если
63
вершина 𝑣𝑖 имеет метку (𝑤, 𝑣𝑘), то первая координата означает присвоенное расстояние от 𝑣1 до 𝑣𝑖, вторая – предыдущую вершину пути от 𝑣1 до 𝑣𝑖. Метки, как и вершины, могут находиться в двух состояниях – быть временными и постоянными.
Алгоритм содержит следующие шаги:
1) Начинаем с источника 𝑣1. Приписываем этой вершине метку (0,0) и делаем постоянной. Каким - либо образом это отмечаем, например, звёздочкой или подчёркиваем: 𝑣1*(0,0). Остальные вершины временные и имеют метки (∞, 0).
2) Пусть вершина 𝑣𝑗(𝑤, 𝑣𝑘) стала постоянной. Рассмотрим все вершины 𝑣𝑗, смежные с 𝑣𝑖. Прибавим величину 𝑤 к расстоянию (весу) от 𝑣1 до 𝑣𝑗. Если эта сумма меньше, чем временное расстояние, присвоенное вершине 𝑣𝑗 (т.е. её предыдущая первая координата), то заменим этой суммой первую координату 𝑣𝑗, а вторую координату заменим на 𝑣𝑖.
3) Находим минимальное из расстояний, приписанных временным вершинам 𝑣𝑗, смежным с 𝑣𝑗. Вершину с наименьшим весом делаем постоянной.
4) Если вершина 𝑣𝑛 не постоянна, то возвращаемся к пункту 2, если 𝑣𝑛 постоянна, то расстояние, присвоенное вершине 𝑣𝑛, является кратчайшим взвешенным расстоянием от 𝑣1 до 𝑣𝑛. Алгоритм закончен.
Для нахождения пути от 𝑣1 до 𝑣𝑛 надо начать с 𝑣𝑛, по второй координате найти предыдущую ей вершину, для этой вершины аналогично найти предыдущую и т.д., пока не будет достигнута первая вершина пути 𝑣1. Перестановка вершин в обратном порядке даст путь от 𝑣1 до 𝑣𝑛.
Рассмотрим этот метод на том же примере. Для графа на рисунке 3.4.3 найти кратчайшее расстояние и путь от вершины A до вершины F.
Заметим, что этот алгоритм можно оформлять, изображая на каждом шаге граф с указанием вершин с их метками, найденными на этом шаге (см., например, [4], стр.611). Мы обойдёмся без рисунков.
1 шаг. Приписываем источнику А метку (0,0), делаем её постоянной и отмечаем 𝐴∗(0,0), остальные вершины временные и имеют метки (,0): B(,0),
) 0 , (
C ,…, F(,0). 1-ая итерация.
2 шаг. С вершиной А смежны вершины В и С:
- от 𝐴∗(0,0) до 𝐵(∞, 0) расстояние 5, 5+0 < , поэтому В меняет метку: B(5,A); - от 𝐴∗(0,0) до 𝐶(∞, 0) расстояние 6, 6+0 < , поэтому С меняет метку: C(6,A); 3 шаг. min(5,6)=5, поэтому В становится постоянной, отмечаем её:
𝐵∗(5, 𝐴). 𝐵 ≠ 𝐹, возвращаемся на второй шаг.
64 2-ая итерация.
2 шаг. С вершиной В смежны вершины С, D, E, F:
- от B∗(5, A) до C(6, A) расстояние 3, 5+3 = 8 > 6, → C не меняет метку: C(6, A);
- от B∗(5, A) до D(∞, 0) расстояние 7, 5+7 = 12 < , → D меняет метку: D(12, B); - от B∗(5, A) до E(∞, 0) расстояние 2, 5+2 =7 < , поэтому E меняет метку: E(7, B);
- от B∗(5, A) до F(∞, 0) расстояние10,5+10=15<, → F меняет метку: F(15, B);
3 шаг. min(6, 12, 7, 15) = 6, поэтому С становится постоянной: C∗(6, A). F
C , возвращаемся на второй шаг.
3-ая итерация.
2 шаг. С вершиной С смежна вершина E (рассматриваем только временные вершины):
- от C∗(6, A) до E(7, B) расстояние 7, 6+7 = 13 > 7, → Е не меняет метку: E(7, B); 3 шаг. E∗(7, B) - постоянная, E ≠ F, возвращаемся на второй шаг.
4-ая итерация.
2 шаг. С вершиной Е смежна вершина F:
- от E∗(7, B) до F(15,B) расстояние 4, 7+4 = 11 < 15, → F меняет метку: F(11, E); 3 шаг. F∗(11, E) - постоянная.
Для наглядности эти рассуждения можно оформить следующей схемой:
А- источник →A(0,0)−постоянная вершина, [
𝐵(∞, 0) 𝐶(∞, 0) 𝐷(∞, 0) 𝐸(∞, 0) 𝐹(∞, 0)
- временные вершины;
1)𝐴∗(0,0) − [
→ 𝐵(∞, 0) − 0 + 5 = 5 <5 ∞→ 𝐵(5, 𝐴)
→ 𝐶(∞, 0) − 0 + 6 = 6 <6 ∞→ 𝐶(6, 𝐴)
- min (5,6)=5 →B(5,A)−
пост;
2)𝐵∗(5, 𝐴) − [
→ 𝐶(6, 𝐴) − 5 + 3 = 8 > 6 → 𝐶(6, 𝐴)3
→ 𝐷(∞, 0) − 5 + 7 = 12 <7 ∞ → 𝐷(12, 𝐵)
→ 𝐸(∞, 0) − 5 + 2 = 7 <2 ∞ → 𝐸(7, 𝐵)
→ 𝐹(∞, 0) − 5 + 10 = 15 <10 ∞→ 𝐹(15, 𝐵)
- min (6,12,7,15) = 6 →
𝐶∗(6, 𝐴) − пост;
3) 𝐶∗(6, 𝐴) − [→ 𝐸(7, 𝐵) − 6 + 7 = 13 > 7 → 𝐸7 ∗(7, 𝐵)]→ 𝐸∗(7, 𝐵) - пост;
65
4) 𝐸∗(7, 𝐵) − [→ 𝐹(15, 𝐵) − 7 + 4 = 11 < 15 → 𝐹4 ∗(11, 𝐸)]→ 𝐹∗(11, 𝐸) - пост.
Итак, вершина F, до которой надо было найти кратчайшее расстояние, стала постоянной, поэтому процесс завершен. 11 есть кратчайшее расстояние от А до F. Если бы совокупность вершин, смежных с постоянной вершиной, была исчерпана до того, как мы достигли вершину F, то задача не имела бы решения, т.к. не было бы пути от А до F.
Для нахождения кратчайшего пути идём последовательно от F к А по указанию второй координаты: F (11, E), Е (7, В), В (5, А), А. Переставив вершины в обратном порядке, получим искомый путь: (A, B, E, F).
Потоки в сетях
Примерами нагруженных графов являются графы, представляющие сети.
Сети – это системы, которые служат для транспортировки некоторых продуктов из одной точки в другую. Например, система нефтепровода, по которой течёт нефть, транспортная система, по которой перемещаются потоки грузов, водопроводная, компьютерная сети и т.д. Поскольку пропускная способность каналов сетей ограничена, то в практических задачах чаще всего требуется определить максимальные потоки, которые способны пропускать сети. Эта задача успешно решается в теории графов.
Сетью называется связный ориентированный граф G (V, E) без петель. В сети выделяют две вершины s - источник (исток) и 𝑡 - сток. Каждой дуге 𝑒 = (𝑢, 𝑣) ставится в соответствие число 𝑐(𝑒)–пропускная способность дуги 𝑒.
Аналогично матрице смежности или матрице весов, представляющих граф, сеть можно представить матрицей пропускных способностей C = (𝑐𝑖𝑗), где с𝑖𝑗 = {𝑐(𝑣𝑖, 𝑣𝑗),если (𝑣𝑖, 𝑣𝑗) существует
0,если (𝑣𝑖, 𝑣𝑗) не существует .
Потоком в сети называется такая функция 𝑓, определённая на множестве дуг E (𝑓: E → N ∪ {0}), что
1) ∀𝑒 ∈ E: 0 ≤ 𝑓(𝑒) ≤ 𝑐(𝑒);
2) ∀𝑣 ∈ 𝑉 такой, что 𝑣 ≠ 𝑠 и 𝑣 ≠ 𝑡: ∑(𝑢,𝑣)∈E𝑓(𝑢, 𝑣) = ∑(𝑣,𝑢)∈E𝑓(𝑣, 𝑢). Первое условие потока очевидно: величина потока в дуге не может превысить её пропускную способность. Второе условие называется условием сохранения потока: в промежуточных вершинах потоки не создаются и не исчезают. Величину Δ(𝑢, 𝑣) = 𝑐(𝑢, 𝑣) − 𝑓(𝑢, 𝑣) называют остаточной
66
пропускной способностью дуги (𝑢, 𝑣). Если 𝑓(𝑢, 𝑣) = 𝑐(𝑢, 𝑣), то дугу (𝑢, 𝑣) называют насыщенной.
Важную роль при определении максимальных потоков играет понятие разреза. Пусть множество вершин V разбито на два непустых непересекающихся подмножества 𝑆 и 𝑇: 𝑉 = 𝑆 ∪ 𝑇, 𝑆 ∩ 𝑇 = ∅. Множество дуг, начала которых лежат в 𝑆, а концы - в 𝑇, называется ориентированным разрезом, обозначается 𝑃 = (𝑆, 𝑇). Таким образом, 𝑃 = (𝑆, 𝑇) = {(𝑢, 𝑣)|𝑢 ∈ 𝑆, 𝑣 ∈ 𝑇}. Пропускной способностью разреза называется сумма пропускных способностей входящих в него дуг. Поток в сети называется максимальным, если его величина не меньше величины любого другого потока; разрез называется минимальным, если его пропускная способность не больше пропускной способности любого другого разреза сети.
Теорема Форда-Фалкерсона. Максимальный поток в сети равен пропускной способности минимального разреза.
Алгоритм Форда-Фалкерсона нахождения максимального потока основан на следующем:
а) пусть в сети есть путь из 𝑠 в 𝑡, состоящий из ненасыщенных дуг. Тогда поток в сети можно увеличить на величину Δ, равную минимальной из остаточных пропускных способностей дуг, входящих в этот путь. Переберём все возможные такие пути из 𝑠 в 𝑡, проведем в них процедуру увеличения потока. В результате получим полный поток, для которого каждый путь из 𝑠 в 𝑡 содержит, по крайней мере, одну насыщенную дугу;
б) рассмотрим произвольный маршрут из 𝑠 в 𝑡, состоящий как из прямых (ориентированных от 𝑠 к 𝑡), так и обратных (ориентированных от 𝑡 к 𝑠) дуг.
Пусть в этом маршруте прямые дуги не насыщены, а потоки на обратных дугах положительны. Обозначим Δ1- минимальную из остаточных пропускных способностей прямых дуг, Δ2- минимальную из величин потоков на обратных дугах. Тогда поток в сети можно увеличить на величину Δ= min{Δ1,Δ2}, прибавляя Δ к потокам на прямых дугах и вычитая на обратных. Ясно, что при этом условие сохранения потока для вершин, входящих в рассматриваемый маршрут, сохраняется.
Заметим, что дуги, ставшие насыщенными, не должны входить в рассматриваемые далее маршруты. Для удобства их можно на чертеже вычёркивать. Кроме того, если в процессе перебора маршрутов все дуги, исходящие из источника или входящие в сток, стали насыщенными, то алгоритм закончен и максимальный поток найден.
67
П р и м е р 3.4.4 – Найти максимальный поток из 𝑠 в 𝑡 и указать минимальный разрез сети G=(V,E), 𝑉 = {𝑠, 𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑡}, заданной матрицей
пропускных способностей C =
0 0 0 0 0 0
10 0 0 0 0 0
0 9 0 0 0 0
17 13 11 0 0 0
0 0 6 11 0 0
0 0 0 11 13 0
.
Рисунок 3.4.4
По матрице С построим граф (см. рисунок 3.4.4). Начнём перебирать все пути из 𝑠 в 𝑡, указывая над стрелками поток через данную дугу и её пропускную способность (в скобках), под стрелкой то же после увеличения потока на Δ.
Полагаем, что вначале поток через все дуги равен нулю:
1) s v t
) 17 ( 0
) 17 ( 211 ) 11 ( 0
) 11 (
11→ → ; Δ = min (11, 17) = 11;
2) s v v v t
) 10 ( 0
) 10 ( 410 ) 13 ( 0
) 13 ( 210 ) 11 ( 0
) 11 ( 110 ) 13 ( 0
) 13 (
10→ → → → ; Δ = min (13, 11, 13, 10) = 10;
3) s v v t
) 17 ( 11
) 17 ( 212 ) 11 ( 10
) 11 ( 111 ) 13 ( 10
) 13 (
11→ → → ; Δ = min (13-10, 11-10, 17-11) = 1.
Больше прямых путей из 𝑠 в 𝑡 без насыщенных дуг нет. Рассмотрим маршруты из 𝑠 в 𝑡, содержащие как прямые, так и обратные дуги:
1) s v v v t
) 17 ( 12
) 17 ( 2 14 ) 11 ( 0
) 11 ( 3 2 ) 6 ( 0
) 6 ( 12 ) 13 ( 11
) 13 (
13→ → →
− ; min (13-11, 6, 11, 17-12) = 2.
Обе дуги, выходящие из источника, стали насыщенными. Алгоритм закончен. Максимальный поток равен 𝑓𝑚𝑎𝑥 = 𝑓(𝑠, 𝑣1) + 𝑓(𝑠, 𝑣2) = 13 + 11 = 24, или 𝑓𝑚𝑎𝑥 = 𝑓(𝑣4, 𝑡) + 𝑓(𝑣2, 𝑡) = 10 + 14 = 24. Минимальный разрез P = (S, T), где S = {𝑠}, T = {𝑣1, 𝑣2, 𝑣3, 𝑣4, 𝑡} или S = {𝑠, 𝑣1, 𝑣2, 𝑣3, 𝑣4}, T = {𝑡}.
68