дзначені кружечками):
1-й крок
В
2 -й крок
В
3-й крок
В
4-й крок
В
5-й крок
В
6-й крок
В
7-й крок
В
Остаточно маємо:
В
Як видно з малюнка, ребра {6,9}, {7,9}, {3,9}, що живлять вершину w, насичені, а що залишилося ребро {8,9}, що харчується від вершини 8, не може отримати більшу значення вагової функції, так як насичені всі ребра, що живлять вершину 8. Іншими словами - якщо відкинути всі насичені ребра, то вершина w недосяжна, що є ознакою максимального потоку в мережі.
Максимальний потік в мережі дорівнює 12.
Мінімальний розріз мережі по числу ребер: {{0,1}, {0,2}, {0,3}}. Його пропускна здатність дорівнює 16
Мінімальний розріз мережі по пропускній здатності: {{6,9}, {7,9}, {3,9}, {3,8}, {5,8}, {7,8}}. Його пропускна здатність дорівнює 12. br/>
Задача 7 (Завдання про листоношу) Виписати ступеневу послідовність вершин графа G.
а) Вказати в графі G ейлерова ланцюг. Якщо такого ланцюга не існує, то в графі G додати найменше число ребер таким чином, щоб у новому графі можна було вказати ейлерова ланцюг.
б) Вказати в графі G Ейлеров цикл. Якщо такого циклу не існує, то в графі G додати найменшу кількість ребер таким чином, щоб у новому графі можна було вказати Ейлеров цикл.
Статечна послідовність вершин графа G:
(3,6,4,5,3,6,4,3,4,4)
а) Для існування ейлерова ланцюга допустимо тільки дві вершини з непарними ступенями, тому необхідно додати одне ребро, скажімо між вершинами 4 і 7. p> Отримана Ейлерова ланцюг: 0,3,2,0,1,2,5,1,4,5,6,1,7,4,6,9,7,8,9,3,8,5,3.
Схема Ейлеровой ланцюга (доданий ребро показано пунктиром):
В
б) Аналогічно пункту а) додаємо ребро {3,0}, замикаючи ейлерова ланцюг (при цьому виконуючи умова існування Ейлерова циклу - парність ступенів всіх вершин). Ребро {3,0} кратне, що ні суперечить завданням, але при необхідності можна ввести ребра {0,7} і {4,3} замість раніше введених.
Отриманий Ейлером цикл: 0,3,2,0,1,2,5,1,4,5,6,1,7,4,6,9,7,8,9,3,8,5,3,0 .
Схема Ейлерова циклу (додані ребра показані пунктиром):
В
Завдання 8
а) Вказати в графі Gор Гамильтонов шлях. Якщо такий шлях не існує, то в графі Gор змінити орієнтацію найменшого числа ребер таким чином, щоб у новому графі Гамильтонов шлях можна було вказати.
б) Вказати в графі Gор Гамільтонів цикл. Якщо такий цикл не існує, те в графі Gор змінити орієнтацію найменшого числа ребер таким чином, щоб у новому графі Гамильтонов цикл можна було вказати.
а) Гамильтонов шлях (ребра зі зміненою орієнтацією показані пунктиром):
В
б) Гамильтонов цикл (ребра зі зміненою орієнтацією показані пунктиром):
В
Задача 9 (Завдання про комівояжера) Дан повний орієнтований симметрический граф з вершинами x1, x2, ... xn.Вес дуги xixj заданий елементами Vij матриці ваг. Використовуючи алгоритм методу гілок і меж, знайти Гамильтонов контур мінімального (максимального) ваги. Задачу на максимальне значення Гамильтонова контуру звести до задачі на мінімальне значення, розглянувши матрицю з елементами, де. Виконати малюнок. br/>
Вихідна таблиця.
x1
x2
x3
x4
x5
x6
x1
ВҐ
3
7
2
ВҐ
11
x2
8
ВҐ
06
ВҐ
4
3
x3
6
05
ВҐ
7
ВҐ
2
x4
6
ВҐ
13
ВҐ
5
ВҐ
x5
3
3
3
4
ВҐ
5
