8. Найти максимальный поток из вершины X1 в вершину X13

(вариант работы с картинками в файле) 

В начале положим для всех дуг (x, y) f(x,y) = 0

Все дуги є I, так как f(x, y) < c(x, y)

(x₁, x₂) (x₂, x₆) (x₆, x₉) (x₉, x₁₃)

i(x₁, x₂) = 3                 (x₁, x₂) є IR

i(x₂, x₆) = 2                 (x₂, x₆) є R

i(x₆, x₉) = 3                 (x₆, x₉) є IR

i(x₉, x₁₃) = 4                (x₉, x₁₃) є IR

 

min{3, 2, 3, 4} = 2

 

f(x₁, x₂) = 0 + 2 = 2

f(x₂, x₆) = 0 + 2 = 2

f(x₆, x₉) = 0 + 2 = 2

f(x₉, x₁₃) = 0 + 2 = 2

(x₁, x₃) (x₃, x₆) (x₆, x₉) (x₉, x₁₃)

i(x₁, x₃) = 3

i(x₃, x₆) = 1

i(x₆, x₉) = 3 – 2 = 1

i(x₉, x₁₃) = 4 – 2 = 2

 

min{3, 1, 1, 2} = 1

 

f(x₁, x₃) = 0 + 1 = 1

f(x₃, x₆) = 0 + 1 = 1

f(x₆, x₉) = 2 + 1 = 3

f(x₉, x₁₃) = 2 + 1 = 3

 

(x₁, x₃) (x₃, x₇) (x₇, x₉) (x₉, x₁₃)

i(x₁, x₃) = 3 – 1 = 2

i(x₃, x₇) = 2

i(x₇, x₉) = 1

i(x₉, x₁₃) = 4 – 3 = 1

 

min{2, 2, 1, 1} = 1

 

f(x₁, x₃) = 1 + 1 = 2

f(x₃, x₇) = 0 + 1 = 1

f(x₇, x₉) = 0 + 1 = 1

f(x₉, x₁₃) = 3 + 1 = 4

 

(x₁, x₄) (x₄, x₆) (x₆, x₁₀) (x₁₀, x₁₃)

i(x₁, x₄) = 3 – 0 = 3

i(x₄, x₆) = 1 – 0 = 1

i(x₆, x₁₀) = 2 – 0 = 2

i(x₁₀, x₁₃) = 3 – 0  = 3

 

min{3, 1, 2, 3} = 1

 

f(x₁, x₄) = 1

f(x₄, x₆) = 1

f(x₆, x₁₀) = 1

f(x₁₀, x₁₃) = 1

 

(x₁, x₂) (x₂, x₈) (x₈, x₁₀) (x₁₀, x₁₃)

i(x₁, x₂) = 3 – 2 = 1

i(x₂, x₈) = 2 – 0 = 2

i(x₈, x₁₀) = 2 – 0 = 2

i(x₁₀, x₁₃) = 3 – 1  = 2

 

min{1, 2, 2, 2} = 1

 

f(x₁, x₂) = 2 + 1 = 3

f(x₂, x₈) = 0 + 1 = 1

f(x₈, x₁₀) = 0 + 1 = 1

f(x₁₀, x₁₃) = 1 + 1 = 2

 

(x₁, x₅) (x₅, x₈) (x₈, x₁₀) (x₁₀, x₁₃)

i(x₁, x₅) = 3

i(x₅, x₈) = 3

i(x₈, x₁₀) = 2 – 1 = 1

i(x₁₀, x₁₃) = 3 – 2  = 1

 

min{3, 3, 1, 1} = 1

 

f(x₁, x₅) = 0 + 1 = 1

f(x₅, x₈) = 0 + 1 = 1

f(x₈, x₁₀) = 1 + 1 = 2

f(x₁₀, x₁₃) = 2 + 1 = 3

 

(x₁, x₃) (x₃, x₇) (x₇, x₁₁) (x₁₁, x₁₃)

i(x₁, x₃) = 3 – 2 = 1

i(x₃, x₇) = 2 – 1 = 1

i(x₇, x₁₁) = 2 – 0 = 2

i(x₁₁, x₁₃) = 4 – 0  = 4

 

min{1, 1, 2, 4} = 1

 

f(x₁, x₃) = 2 + 1 = 3

f(x₃, x₇) = 1 + 1 = 2

f(x₇, x₁₁) = 0 + 1 = 1

f(x₁₁, x₁₃) = 0 + 1 = 1

 

(x₁, x₄) (x₄, x₇) (x₇, x₁₁) (x₁₁, x₁₃)

i(x₁, x₄) = 3 – 1 = 2

i(x₄, x₇) = 2 – 0 = 2

i(x₇, x₁₁) = 2 – 1 = 1

i(x₁₁, x₁₃) = 4 – 1  = 3

 

min{2, 2, 1, 3} = 1

 

f(x₁, x₄) = 1 + 1 = 2

f(x₄, x₇) = 0 + 1 = 1

f(x₇, x₁₁) = 1 + 1 = 2

f(x₁₁, x₁₃) = 1 + 1 = 2

 

(x₁, x₅) (x₅, x₈) (x₈, x₁₁) (x₁₁, x₁₃)

i(x₁, x₅) = 3 – 1 = 2

i(x₅, x₈) = 3 – 1 = 2

i(x₈, x₁₁) = 1 – 0 = 1

i(x₁₁, x₁₃) = 4 – 2  = 2

 

min{2, 2, 1, 2} = 1

 

f(x₁, x₅) = 1 + 1 = 2

f(x₅, x₈) = 1 + 1 = 2

f(x₈, x₁₁) = 0 + 1 = 1

f(x₁₁, x₁₃) = 2 + 1 = 3

 

(x₁, x₄) (x₄, x₇) (x₇, x₁₂) (x₁₂, x₁₃)

i(x₁, x₄) = 3 – 2 = 1

i(x₄, x₇) = 2 – 1 = 1

i(x₇, x₁₂) = 1 – 0 = 1

i(x₁₂, x₁₃) = 3 – 0  = 3

 

min{1, 1, 1, 3} = 1

 

f(x₁, x₄) = 2 + 1 = 3

f(x₄, x₇) = 1 + 1 = 2

f(x₇, x₁₂) = 0 + 1 = 1

f(x₁₂, x₁₃) = 0 + 1 = 1

 

(x₁, x₅) (x₅, x₈) (x₈, x₁₂) (x₁₂, x₁₃)

i(x₁, x₅) = 3 – 2 = 1                

i(x₅, x₈) = 3 – 2 = 1                

i(x₈, x₁₂) = 3 – 0 = 3               

i(x₁₂, x₁₃) = 3 – 1  = 2             

 

min{1, 1, 3, 2} = 1

 

f(x₁, x₅) = 3

f(x₅, x₈) = 3

f(x₈, x₁₂) = 1

f(x₁₂, x₁₃) = 2

 

Увеличивающего пути нет!

Максимальный поток = 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 12