ся, якщо їх елементи впорядковані.
Якщо існує шлях з хi в хj, то вершина хi називається попередньої вершині хj, а хj - подальшою хi.
Впорядкування вершин зв'язного графа без контурів означає розбивка його вершин на групи так, щоб:
) вершини 1-ї групи не мали попередніх, а вершини останньої - подальших;
) вершини будь-який інший групи не мали попередніх в такій групі;
) вершини однієї і тієї ж групи не єдналися з дугами.
Графічний спосіб упорядкування вершин (алгоритм Фалкерсона).
1. Знаходяться вершини графа, в які не входить жодна дуга. Такі вершини утворюють 1-у групу. p>. Вершини і виходять з них дуги встановленої групи виключаються з далекої-шего розгляду. p>. Встановлюється наступна група вершин, в які не входить жодна дуга. p>. Якщо процес упорядкування не закінчений, те перехід п. 2. p>. В отриманому графі, Ізоморфне вихідного, перенумеровуються вершини. br/>
3. Мережі і потоки на мережах. Постановка задачі про максимальний потік
Мережа - кінцевий зважений зв'язний орграф без контурів і петель, орієнтований в одному загальному напрямку від вершини I (витік, вхід) до вершини S (стік, вихід).
Для наочності уявімо, що по ребрах від витоку до стоку прямує деяку речовину (вантаж, ресурс, інформація тощо).
Максимальна кількість rij речовини, яка може пропустити за одиницю часу ребро (i, j), називається його пропускною здатністю. У загальному випадку rij? rji. Якщо вершини не з'єднані, rij = 0. Т.к. немає петель, то rii = 0. Пропускну здатність можна задати квадратною матрицею. p> Кількість хij речовини, що проходить по ребру (i, j) в одиницю часу, називається потоком по ребру (i, j). Передбачається, що якщо з хi в хj направляється потік хij, то з xj в xi направляється потік (-хij)
xij = - xji. (1)
Потік по кожному ребру не перевищує його пропускну здатність
xij rij (i =; j =). (2)
Кількість речовини, притікає в вершину, дорівнює кількості речовини, що випливає з неї
(i I, S). (3)
Сукупність Х = потоків по всіх ребрах мережі називають потоком по мережі. Загальна кількість речовини випливає з витоку I, збігається із загальною кількістю речовини, що надходить в сток S, тобто br/>
F = xIj = xiS. (4)
Функцію F називають потужністю потоку.
Якщо на мережі заданий потік Х =, то ребро (i, j) називається насиченим, якщо потік xij по ньому збігається з його пропускною здатністю rij (xij = rij), і ненасиченим, якщо xij
Задачу про максимальний потік можна сформулювати наступним чином: знайти сукупність Х * = {x * ij} потоків x * ij по всіх ребрах мережі, яка задовольняє умовам (1) - (3) і максимізує лінійну функцію (4). Це типова ЗЛП. p> Зауваження. Не всякі n2 чисел можуть задавати потік по мережі. Тільки такі n2 чисел xij задають потік, які задовольняють умовам (1) - (3). p> Приклад.
4. Поняття розрізу. Теорема Форда-Фалкерсона. Алгоритм розв'язання задачі про максимальний потік
Нехай дана деяка мережу. Розіб'ємо безліч вершин мережі на два непересічних безлічі А і В так, щоб витік I потрапив в А, а сток S - у В. У цьому випадку на мережі заданий розріз. Сукупність ребер (i, j), початкові вершини яких належать А, а кінцеві - В, називається розрізом мережі (А/B). p> Пропускний здатністю розрізу називають суму пропускних здібностей всіх ребер розрізу R (A/B) = rij.
Сума всіх потоків xij по всіх ребрах розрізу називається потоком через розріз
X (A/B) = xij.
Теорема Форда-Фалкерсона: на будь-якій мережі максимальна величина потоку дорівнює мінімальній пропускній здатності розрізу.
Теорема дозволяє визначити максимальний потік для відносно простих мереж. У загальному випадку використовують наступний алгоритм. p> Алгоритм розв'язання задачі про максимальний потік.
1.Построіть початковий потік Х = (чим більше величина обраного потоку, тим швидше вирішується завдання).
. На основі заданої мережі будується нова мережа:
а) кожна дуга, для якої залишається у новій мережі з первісної rij;
б) кожна дуга для якої замінюється на дві:
одна дуга того ж напрямку з пропускною здатністю rij-;
друга дуга противоположенного напрямки з пропускною здатністю.
. Якщо в новій мережі можна знайти ненульовий потік з I в S, то цей потік додає-ся до початкового. У результаті виходить новий потік і переходять до п. 2. p> Якщо ж у новій мережі відсутні ненульові потоки з I в S, то максимальний потік мережі побудований.
Приклад. p> 5. Елементи мережевого планування
Мережевий графік - мережа, вершини якої - "події", результати певних робіт або стану етапів проміжних робіт), а дуги - В«роботиВ» (протяжний у часі процес, що призводить до відповідного В«п...
