Побудуємо заданий граф g і деяке відповідне йому остове дерево т (рис. 7.4).

Рисунок 7.4

Побудуємо базис розрізів графа. Знайдемо ранг розрізів: (G)= m- =8. Ранг розрізів відповідає кількості базисних розрізів для графа G.

e₂₀: V₁={ v₂ }; V₂={v₁, v₃, v₄, v₅, v₆, v₇, v₈, v₉},

c₁={ e₁₈, e₁₉, e₂₀, e₂₁, e₂₆};

e₂₅: V₁={ v₂, v₇ }; V₂={v₁, v₃, v₄, v₅, v₆, v₈, v₉ },

c₂={ e₁₈, e₁₉, e₂₂, e₂₃, e₂₄, e₂₅, e₂₆};

e₁₃: V₁={v₉}; V₂={v₁, v₂, v₃, v₄, v₅, v₆, v₇, v₈},

c₃={e₁₃, e₁₄};

e₅: V₁={v₂, v₇, v₈, v₉}; V₂={v₁, v₃, v₄, v₅, v₆},

c₄={e₄, e₅, e₆, e₁₀, e₁₁, e₁₂, e₁₈, e₁₉, e₂₂, e₂₃, e₂₆};

e₈: V₁={ v₂, v₃, v₇, v₈, v₉}; V₂={ v₁, v₄, v₅, v₆},

c₅={ e₇, e₈, e₉, e₁₀, e₁₁, e₁₂, e₁₈, e₁₉, e₂₆};

e₂: V₁={ v₁, v₂, v₃, v₇, v₈, v₉}; V₂={ v₄, v₅, v₆},

c₆={e₁, e₂, e₃, e₁₀, e₁₁, e₁₂, e₁₈, e₁₉};

e₁₅: V₁={ v₁, v₂, v₃, v₄, v₇, v₈, v₉}; V₂={ v₅, v₆},

c₇={ e₁₀, e₁₁, e₁₂, e₁₅, e₁₈, e₁₉};

e₁₇: V₁={ v₁, v₂, v₃, v₄, v₆, v₇, v₈, v₉}; V₂={ v₅},

c₈={ e₁₆, e₁₇, e₁₈, e₁₉}.

Побудуємо базис циклів графа G. Кількість базисних циклів відповідає цикломатичному числу для заданого графа. Отже, у заданому графі є 18 базисних циклів.

Для побудови базису циклів додаємо до остовного дерева Т кожну з хорд у порядку їхнього зростання, виділяємо простий цикл і формуємо базис циклів графа (у вигляді послідовності ребер, що утворять кожний з базисних циклів). Таким чином отримуємо 18 базисних циклів.

Сe1={ e1, e2}; Сe3={e2, e3}; Ce4={e4, e5};	Ce6={e5, e6}; Ce7={e7, e8}; Ce9={e8, e9};
Ce10={e5, e8, e2, e15, e10}; Ce11={e5, e8, e2, e15, e11}; Ce12={e5, e8, e2, e15, e12}; Ce14={e13, e14}; Ce16={e16, e17}; Ce18={e17, e15, e2, e8, e5, e25, e20, e18};		Ce19={e17, e15, e2, e8, e5, e25, e20, e19}; Ce21={ e20, e21}; Ce22={e5, e25, e22}; Ce23={e5, e25, e23}; Ce24={e24, e25}; Ce26={ e8, e5, e25, e20, e26}.

Завдання 9. Задано неорієнтований мультиграф (рис. 7.5). Визначити відстані від вершини v₃ до інших вершин. Побудувати на вершинах графа дерево мінімальної вартості.

Рисунок 7.5

Для пошуку відстані від вершини v₃ скористаємося алгоритмом Дейкстри. У кожному стовпчику вибираємо мінімальну відстань (перша цифра – номер вершини, друга – відстань).

v1		(4,7)	(4,7)
v2		(4,10)	(4,10)	(4,10)	(4,10)
v3	0
v4	(3,2)
v5		(4,6)
v6			(5,13)	(1,19)
v7				(1,10)	(1,10)	(1,10)

d(v3,v1)=7; d(v3,v2)=10; d(v3,v3)=0; d(v3,v4)=2;

d(v3,v5)=6; d(v3,v6)=9; d(v3,v7)=10.

Для побудови дерева мінімальної вартості упорядкуємо ребра в порядку зростання їхніх ваг. Після цього включаємо в остовне дерево ребра в порядку зростання їхніх ваг, якщо знов включене ребро утворить цикл з раніше включеними ребрами, то його пропускають (рис. 7.6).

v 1 – v6 = 2; v4 – v3 = 2; v1 – v7 = 3; v1 – v2 = 4;

v4 – v5 = 4; v1 – v4 = 5; v1 – v2 = 6; v2 – v6 = 6;

v5 – v6 = 7; v6 – v7 = 8; v2 – v4 = 8; v2 – v5 = 9.

Рисунок 7.6

Завдання 10. Задана транспортна мережа (рис. 7.7). Пропускнi спроможностi дуг, задані номерами j та k вказанi у табл. 6.6. х₀ – вхiд мережi, z – вихiд. Знайти найбiльший потiк та найменший розрiз мережi.

1. Пропускаємо по мережі деякий початковий потік.

Рисунок 7.7

Розмір початкового потоку у мережі .

По черзі розглянемо всі шляхи між х₀ і z та для кожної дуги обраного шляху знайдемо різницю між пропускною здатністю дуги і потоком, що проходить по дузі. Потім збільшимо потік таким чином, щоб шлях, що веде з х₀ у z, містив хоча б одну насичену дугу.

Для кожної дуги обраного шляху додаємо до чисельника мінімальну отриману різницю. В результаті цієї дії хоча б одна дуга шляху стає насиченою. Після цього вибираємо наступний шлях. Повторюємо ці дії доти, поки не одержимо повний потік у мережі.

(рис. 7.8).

; (рис. 7.9).

; (рис. 7.10).

; (рис. 7.11).

.

Всі існуючі і розглянуті шляхи від х₀ до z містять потік , який є повним.

Рисунок 7.8	Рисунок 7.9
Рисунок 7.10	Рисунок 7.11

2. Збільшення потоку мережі знаходиться в розмітці вершин індексами, що вказують шлях, за яким можлива зміна потоку. Якщо розмітка досягає вершини z, то потік можна збільшити по шляху, що відповідає отриманій розмітці. Збільшення потоку можливо доти, поки в результаті розмічування вершина z одержує позначки.

Процедура розмітки вершин:

Крок 1. Позначаємо х₀ індексом .

Крок 2. Якщо x_i вже має позначку, то:

• позначка приписується всім непозначеним вершинам, які зв'язані з x_i ненасиченою дугою, що веде з x_i до даної вершини;

• позначку отримують усі непозначені вершини, пов'язані зайнятою дугою, що йде з даної вершини у вершину x_i.

Таким чином, позначку отримують усі вершини y, що задовольняють умовам: , у – непозначена, отримують усі y, що задовольняють умовам , y – непозначена.

Крок 3. Якщо в результаті такої розмітки виявиться позначена вершина z, то переходимо до пункту 4. У протилежному випадку потік, який було отримано на попередньому циклі, був максимальним.

Крок 4. Будуємо шлях від х₀ до z, усі вершини якого відповідають номерам позначок попередніх вершин з точністю до знака. Побудова шляху починається від вершини z. Потік у всіх дугах шляху змінюється за такими правилами:

Як результат отримуємо новий потік у мережі, який дорівнює .

Переходимо до пункту 1. Маємо шлях , яким можливе збільшення потоку: . Збільшимо потік на 1 по дугах та зменшимо на 1 – по (х₄,х₂) (рис. 7.12).

Рисунок 7.12

Повторимо розмітку.

Одержимо потік . При подальшій розмітці позначки одержують тільки вершини x₀ і x₁ (рис. 7.13 – позначки, виділені напівжирною рамкою).

Рисунок 7.13

Оскільки розмітка не досягає вершини z, потік – максимальний. Для знаходження мінімального розрізу використовують позначки, що передаються від входу всіма можливими способами. Вершини, які при цьому не одержують позначок, утворять множину вершин розрізу А. Позначені вершини утворять множину .

Усі дуги, що йдуть з вершин множини у вершини множини А, і утворюють мінімальний розріз. У нашому прикладі: , . Розріз утворить дуги: .

Пропускна здатність цього розрізу дорівнює сумі пропускних здатностей вхідних у нього дуг, тобто 17.

З прикладу видно, що розмір максимального потоку мережі дорівнює розміру мінімального розрізу, що емпірично доводить теорему Форда-Фалкерсона.