Елементи теорії оптимізації на графах і мережах

2.3.1 Синтез мережі мінірисьної вартості

 

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

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

З теорії графів і мереж відомо, що розв´язання поставленої задачі є мережа з топологією типу " дерево ".

О з н а ч е н н я. Зв'язний граф (мережа, щозв'язує,) називається деревом, якщо в ньому є відсутні цикли.

Говорять, що граф містить цикли, якщо в ньому можна відшукати замкнуті контури. Відсутність циклів визначає особливість графа типу дерево, що складається в тому, що поміж будь-якою парою його вершин існує лише один єдиний сполучуючий їх шлях, що зв'язує, тобто параметр зв´язності h=1. Кількість ребер у дереві завжди на одиницю менше за число його вершин.

О з н а ч е н н я. Дерево, в яке включено всі вершини, називається покривним.

Математично задача синтезу мережі мінірисьної вартості формулюється таким чином.

 

Нехай задано неоріентований граф G(N, V), де множина вершин N відповідає множині пунктів мережі, сумарне число яких дорівнює n, а множина ребер V – відстаням {lij} поміж парами пунктів. Відома вартість cij організації одного кілометра лінії зв'язку поміж пунктами i та j.

Необхідно знайти деяке покривне дерево G'(N, V'), для якого досягається мінімум цільової функції:

Для розв´язання поставленої задачі існує ряд ефективних алгоритмів. Наведемо один із них, що відомий як алгоритм Прима і носить ім'я автора. Алгоритм зреалізується шляхом наданя позначок вершинам, що вводяться в шуканий граф G'(N, V'), і послідовного введення в нього найбільш коротких ребер, сумарна кількість яких має не перевищувати (n–1) і забезпечувати зв´язність між всіма n вершинами покривного дерева, що покриває.

Пошагова форма алгоритму має такий вид.

Крок 0. Шукана мережа G'(N, V') у вихідному стані містить n вершин і не містить ребер. Обирається одна довільна вершина i й позначається як "о брана ". Інші (n – 1) вершин позначаються як " необрані ".

Крок 1. Відшукується ребро (i, j), що належить до G(N,V) з мінірисьною вагою, у якої вершина i належить до підмножині " обраних " вершин, а вершина j – до підмножини " необраних " вершин.

Крок 2. Ребро (i, j) включається в шукану мережу G'(N, V'), а вершина j виключається з підмножини " необраних " вершин і включається в підмножину " обраних " вершин. Якщо підмножина " необраних " вершин виявилася порожньою – кінець роботи алгоритму. В противному разі – перехід до кроку 1.

Проілюструємо роботу алгоритму Прима на прикладі. Нехай задано 7 пунктів мережі, відстані поміж який зведено в матрицю L=|| lij||, а саме:

L =	0 10 5 12 9 3 9 10 0 7 2 8 4 6  5 7 0 3 1 5 11 12 2 3 0 10 15 10 9 8 1 10 0 12 9 3 4 5 15 12 0 17 9 6 11 10 9 17 0

 

 На кроці 0. Шуканий граф G'(N,V') містить 6 вершин і не містить ребер. Оберемо вершину 3 й позначимо її як ² обрану ² (рис.2.2)

На кроку 1 обираємо ребро (l35) як ребро з найменшою вагою, у якого вершина i =3 належить до підмножини " обраних " вершин (воно поки містить усього лише одну вершину 3), а вершина j =5 – до підмножині " необраних " вершин (тепер це решта вершин). На кроку 2 ребро l35 вводиться в шуканий граф G'^| , а вершина 5 включається у підмножину " обраних " вершин (рис. 2.3)

 

 

Рисунок 2.2                                                   Рисунок 2.3   

 

Оскільки підмножина " необраних " вершин не порожня, повторюємо крок 1. Для цього відшукуємо ребро мінімальної ваги, перебираючи сполучення кожної пари " обраної " й " необраної " вершин. Таким виявилося ребро l34 (рис.2.4). Воно вводиться в граф G', а вершина 4 стає " обраною ".

 

Рисунок 2.4                                        Рисунок 2.5

 

Наступними обираються ребра: l26 (рис. 2.6); l31 (рис. 2.7); l27 (рис. 2.8). На цьому робота алгоритму закінчується, оскільки усі вершини виявилися позначеними як "обрані" (тобто підмножина " необраних " вершин виявилася порожньою підмножиною).

                                                 Рисунок 2.8

 

Здобуто шуканий граф G'(N, V'), що являє собою покривне дерево, оскільки він включає усі вершини, містить число ребер на одиницю менше за число вершин (n=7, v=6) і забезпечує зв´язність кожної пари вершин.

 

2.3.2 Визначення медіани графа

 

Розглянемо таку задачу. Нехай граф G(N, V) являє собою певну кабельну мережу, що з'єднує n абонентських пунктів. Вага кожного ребра (i, j), що належить до V відповідає довжині lij або вартості кабеля, що з'єднує пункти i та j. Необходімо визначити деяку вершину m що належить до N, в якій доцільно розмістити вузол комутації (наприклад, районну АТС) із погляду мінімізації сумарної довжини кабеля, що з'єднує абонентські пункти з УК.

Рохв´язанням поставленої задачі є визначення медиани графа G(N,V).

О з н а ч е н н я. Вершина m належить до N, є медіана графа
G(N, V), якщо вона задовольняє умові:

Величина  називається медіанною довжиною графа G і являє найменшу сумарну довжину ребер, що з'єднують вершину m з іншими вершинами графа.

Алгоритм визначення медиани графа G включає такі кроки.

Крок 1. У вихідній матриці вагів L = [lij], відповідній довжинам ребер, знайти суму елементів для кожного рядка:

Крок 2. Серед множини значень {Ri} відшукати мінірисьне Rm. Вершина m і є медиана графа G.

 

2.3.3 Визначення центра графа

 

Припустимо, що задане місце положення пунктів абонентської мережі, у якій зреалізовується стаціонарний радіодоступ до опорного вузла базової мережі. Необхідно серед пунктів абонентської мережі визначити місцеположення базової станції (БС), котра по радіо-каналах зв'язується з абонентськими пунктами (АП). Бажано, щоби відстань від БС до будь-якого АП була мінімальною, що забезпечить стійкий радіозв'язок за меншої потужності передавача БС. Вочевидь, що такому критерію задовольнити неможливо, тому доводиться мінімізувати відстань до самого віддаленого пункту. При цьому доцільно, щоб БС за можливістю зайняла центральне положення щодо всіх ОП.

Задача віднайдення такого пункту може бути зведена до задачі віднайдення центра графа.

О з н а ч е н н я. Нехай G(N,V) є граф, де N – множина вершин, а V - множина відстаней поміж всіма вершинами.

Вершина s називається центром графа G(N,V), якщо вона задовольняє умові

max lsj  max lij для будь-який i; 1  j  n.

Алгоритм віднайдення центра графа (вершини s) виходить з самого визначення:

Крок 1. У кожному рядку вихідної матриці ваги L = [lij] – відшукуваний елемент з максимальним значенням.

Крок 2. Серед множини максимальних значень елементів рядків відшукуємо найменше lsj  {lij}. Вершина s є центр графа.

Таким чином, мінімізувавши відстань від точки s до самої віддаленої вершини, ми забезпечили до решти вершин гарантовано меншу відстань.

 

2.3.4 Визначення циклу найменшої довжини

 

Ця задача відома як “задача про комівояжера”. Нехай дано граф G(N,V), вершини якого відповідають містам у зоні обслуговування комівояжера, а дуги відбивають зв'язки поміж парами міст. Маршрутом комівояжера називається контур, що включає кожну вершину графа G.

О з н а ч е н н я. Контур, що включає кожну вершину графа G(N,V) лише один разом, називається гамільтоновим контуром (або гамільтоновим циклом).

Назва гамільтонів цикл дано за ім´ям ірландського математика Вильяма Гамільтона, котрий 1859 року вперше почав вивчення цих задач.

Задачею комівояжера називається задача пошуку маршруту комівояжера найменшої довжини. Оптирисьним розв´язанням цієї задачі є гамільтонів цикл найменшої довжини. Задача може бути розв´язана наступним точним методом.

Перенумеруємо n міст цілими числами від 1 до n. Базовому місту надамо номер n. Завважимо, що тур комівояжера однозначно відповідає переставленню цілих чисел 1, 2,..., (n – 1). Базове місто під номером n при цьому постійно займає останню позицію й у процесах переставлення не бере участь. Кожному переставленню можна поставити у відповідність певне число, що визначає довжину маршруту комівояжера як суму довжин ребер циклу, що сполучує всі n вершин графа.

Утворивши усі переставлення з (n – 1) чисел і здобувши довжини маршрутів, кількість яких визначається як (n – 1)!, неважко відшукати маршрут найменшої довжини.

Наближений евристичний алгоритм може бути дістано використанням евристик, наприклад “кожного кроку в цикл включається найближче місто”.

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

 

2.3.5 Перебування найкоротшого шляху в мережі

 

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

О з н а ч е н н я. Шляхом називається послідовність вершин _ir =(i,j,…,r) або послідовність дуг (ребер) _ir ={(i, j),…(до, r)}, що з'єднують пару вершин i та r графа G.

Сума наданих дугам (ребрам) вагів у шляху _ir  визначає довжину шляху.

Шлях із вершини i у вершину r, що має мінірисьно можливу довжину називається найкоротшим шляхом.

Мережа називається зв'язуючою, якщо в ній для кожній пари вершин є принаймні один сполучний їх шлях.

На підстави мережної моделі задачу про віднайдення найкоротшого шляху можна сформулювати в таким чином.

Нехай дана зв´язуюча мережа G, в якій кожній дузі (ребру) надана позитивна вага, пропорційна до її (його) довжині. Потрібно знайти шлях _st поміж заданими вершинами s та t, що має мінірисьно можливу довжину, тобто

L =  lij ® min (на М),

де М – множина всіх можливих шляхів з s в t.

Одним із найбільше ефективних алгоритмів, що розв´язують поставлену задачу, є алгоритм Дейкстри, що носить ім'я автора.

Особливістю цього алгоритму є той факт, що в процесі його виконання водночас будуються найкоротші шляхи з заданої вершини   s у решту вершин мережі. Це пояснюється тим, що будь-яка вершина i _ N може виявитися проміжної в найкоротшому шляху з s в t. По закінченні роботи алгоритму вершина s стає пов'язаною з рештою вершин зв'язуючої мережі G, в тому числі й з вершиною t, найкоротшими шляхами, а дуги (ребра) що увійшли до них, утворять деяку підмежу без циклів, тобто дерево з коренем у вершині s.

Робота алгоритму зреалізується за допомогою розставляння у вершин позначок виду (Lsj, i), де Lsj – довжина найкоротшого шляху з вихідної вершини s в певну вершину j, а i – попередня j вершина в цьому шляху.

Позначки поділяються на тимчасові і постійні. Тимчасові позначки можуть змінюватися в наслідок роботи алгоритму, а постійні – не змінюються.

Нижче наводиться алгоритм Дейкстри в покроковій формі.

Крок 0. Для вершини s покладається Lss= 0, а для інших вершин Lsj= ђ. Всі вершини мають тимчасові позначки виду (Lsj,s).

Крок 1. Серед вершин із тимчасовими позначками вибираємо вершину r, для котрої Lsr=min(Lsj). Позначка вершини r стає постійною.

Крок 2. Якщо усі вершини мережі дістали постійні позначки – кінець роботи алгоритму. В противному разі – перехід до кроку 3.

Крок 3. Перераховуємо тимчасові позначки для вершин, суміжних до вершини r, що дістала постійну позначку на кроку 1, відповідно до виразу: Lsj=min(Lsj,Lsr+Lrj).

Перехід до кроку 1.

Трасування шляху _st складається в оберненому напрямку, наслідуючи з вершини t у s, керуючись вершинами i в постійних позначках.

Проілюструємо роботу алгоритму Дейкстри на прикладі.

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

 

                                         Рисунок 2.9

 

Крок 0. Позначка P для вершини s має вид: Рs=(0,0). Для решти вершин Рi=(ђ,s). Всі позначки тимчасові.

Крок 1. Серед тимчасових позначок найменший параметр довжини має вершина s, оскільки Lss=0. Її позначка стає постійної (позначимо її подвійними скобками).

Крок 3. Перераховуємо тимчасові позначки для вершин, суміжних до вершини s. Для вершини 1 параметр довжини

Ls1=Lss+ls1=0+15=15.

Дістане значення менше за те, що є (Lsi= ђ) і тому нове значення тимчасової позначки буде P1=(15,s).

Для вершини 2 нова позначка має значення P2=(17,s). Для вершини 3 P3=(10,s).

Перейшовши до кроку 1, обираємо вершину 3, оскільки вона має найменший параметр довжини Ls3=10, серед усіх вершин із тимчасовими позначками. Її позначка стає постійної. Оскільки ещё не усі вершини дістали постійні позначки, переходимо до кроку 3 і здійснюємо перерахунок позначок для вершин, суміжних до вершини 3:

P2=(17,s) можна залишити без зміни, оскільки новий параметр довжини дорівнює попередньому значенню.

P5=(22, 3),

Pt=(30, 3).

Вершина 1 на кроку 1 дістає постійну позначку, оскільки її параметр довжини мінімальний.

Нове значення позначки на кроку 3 дістає вершина 4, а саме
 P4=(24, 1).

Повертаючись до кроку 1, встановлюємо постійну позначку для
вершини 5. Змінити значення позначок на кроці 3 не вдається. Фіксуємо наступну вершину з постійною позначкою – це вершина 4.

Змінити тимчасову позначку для вершини t не удаётся – і вона автоматично стає постійною.

На цьому робота алгоритму закінчується.

Трасування шляху _st визначаємо, рухаючись у зворотному напрямку від t до s через вершини, вказані в позначках: t  3  s.

 

2.3.6 Визначення множини шляхів заданої транзитності

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

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

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

У термінах графових моделей задача формулюється в такий спосіб.

Нехай дано певний вихідний граф G(N,V), у відповідності з множиною N потужністю n вершин якого поставлено вузли комутації мережі зв'язку, а з множиною V – з´єднувальні лінії мережі.

Необхідно визначити множину шляхів M={   _si } із заданої вершини s в решту вершин i  N, i_ s, i=1...n, графа G, для яких параметр транзитности Т не перевищує певної заданої величини T0, тобто

Т_ T0, " _si, i_ s, i=1...n.

Одним із найбільше зручних і легко зреалізовуваних на ЕОМ методів визначення шляхів, що відповідають цій вимозі, є побудова так називаного “ ярусного дерева ” шляхів від певної заданої вершини s до решти вершин графа.

На рис. 2.10 наведено вихідний граф й відповідне йому ярусне дерево з параметром Т₀=2. Тут під Т розуміється кількість транзитних вершин.

.

Рисунок 2.10

 

Алгоритм побудови “ярусного дерева” містить у собі такі кроки.

Крок 0. Утворити підмножину нульового яруса, включивши в нього єдиний елемент-вершину s. Використовуючи матрицю суміжності,виписати номера стовпчиків у рядку з номером S, елементи якої дорівнюють asj=1. Таким чином дістано підмножину вершин першого яруса, утворену вершиною s.

Крок 1. Утворити підмножину вершин такого яруса. Для цього:

а) по черзі обираються вершини попереднього яруса, для кожної з яких обирається рядок з одноимённим номером в матриці суміжності;

б) для кожного рядка виписуються номера стовпців, визначувані ненульовими елементами;

в) у кожному з утворених підмножин виключаються номера вершин (номера стовпчиків), щодо яких утворювалися підмножини вершин у попередніх ярусах. Всі невикреслені елементи (номера стовпчиків) утворять підмножини такого яруса.

Крок 2. Якщо номер яруса дорівнює (Т₀+1) – кінець. В противному разі – перейти до кроку 1.

 

2.3.7 Задачі про потоки

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

О з н а ч е н н я 1. Число хijназивається потоком по дузі (ребру)

(i,j), якщо хij _ bij, де bij -пропускна здатність цієї дуги.

О з н а ч е н н я 2. Потоком Pst із певної вершини s, званої джерелом, в певну вершину t, звану стоком, у мережі є множина ненегативних чисел хij (потоків дуг), якщо це число задовольняють таким обмеженням:

                  < -Pst,якщо j = s (джерело);

5 хij - 5 хjr = = 0,якщо j  s,t;                                          (1)

  Pst,якщо j = t (стік).

Pst ³ 0; 0 £ хij £ bij      для всіх (i, j) _ V                                       (2)

Тут перша сума береться по дугах, котрі ведуть у вершину j,а друга сума – по дугах, котрі ведуть з вершини j.

Обмеження (1) характеризує той факт,що в кожну вершину (крім джерела і стоку) приходить стільки потоку,скільки з її виходить, і називаеться умовою зберігання потоку. Обмеження (2) означає, що потік по дузі обмежений її пропускною здатністю.

О з н а ч е н н я 3. Перерізом (розрізом) мережі називається ненадлишкова сукупність дуг (ребер), при вилученні яких з мережі порушується її зв´язність.

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

О з н а ч е н н я 5. Переріз, що розділяє S та t має найменшу пропускну здатність, називається мінімальним перерізом.

Мінімальний переріз, що розділяє джерело s та стікt,є аналогом “вузького місця” у будь-якій мережі й, отже, величина максимального потоку не може перевищити його пропускну здатність. Існує теорема, доведена Фордом та Фалкерсоном, що стверджує, що розмір максирисьного потоку завжди дорівнює мінімальній пропускній здатності серед всіх перерізів, що розділяють s та t. Теорема про максимальний потік та мінімальний переріз є основний у теорії потоків у мережах.

О з н а ч е н н я 6. Мережа, що має одне джерело й один стік, називається двополюсною.

О з н а ч е н н я 7. Мережа, у котрої кожна пара вершин може розглядатися як джерело і стік, називається багатополюсною.

О з н а ч е н н я 8. Якщо в мережі є декілька джерел і декілька стоків і потік може йти з будь-якого джерела в будь-який стік, то такий потік називається однопродуктовим (наприклад, мережі газопроводів, нафтопроводів, енергомережа тощо).

О з н а ч е н н я 9. Якщо в мережі з декількома джерелами і стоками потік має йти з певних виокремлених джерел в певні фіксовані стоки, то такий потік називається багатопродуктовим (наприклад, мережі інформаційного зв'язку, перевезень поштових відправлень тощо).

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

Для оцінки пропускної здатності зв´язуючої мережі досить визначити розмір максирисьного потоку, що вона може пропустити, причому обчислення його дугових компонентів, віднайдення шляхів передавання може стати зовсім необов'язковим. Згідно з теоремою про максимальний потік і мінімальний розріз вказана задача може бути зведена до визначення пропускної здатності мінімального перерізу. Найбільше простим засобом віднайдення такого перерізу для двухполюсной мережі є перегляд усіх можливих перерізів, що розділяють множину вершин N  мережі на дві незв'язаних підмножини: N1, що включає джерело, і N2,. включающего стік, і вибір серед них перерізу, який має мінімальну пропускну здатність. Єдину складність, що при цьому виникає, становить визначення множини самих перерізів. Нижче наводиться алгоритм, котрий дає змогу перебороти зазначену складність, і має високу ефективність з погляду реалізації на ЕОМ. Основна ідея, покладена в його основу полягає в наступному.

Вершинам підмножин N1 і N2, на які черговий переріз розділяє мережу, надаються певні позначки, наприклад,: 0. N1; 1. N2.

Нехай джерело s належить до N1,а стік t належить до N2. Отже, вершина s буде позначена нулем, а t – одиницею. Залишається розподілити позначки поміж рештою (n – 2) вершин для кожного можливого перерізу мережі.

Для цього слід задатися правилом, котре породжує різні комбінації нулів та одиниць, що можна використовувати для того, щоб розсортувати решту (n – 2) вершин на дві підмножини N1 та N2. За таке правило можна використовувати принцип подання чисел натурального ряду в двійковому виді. Розрядність двоичного числа в такому разі визначається значенням (n – 2) й, отже, максимальна кількість двійкових чисел складе 2^(n-2). Ця сама величина відповідає максимально можливій кількості перерізів, котрі розділяють мережу на дві підмножини – N1 та N2 несполучених вершин. Кожної позиції двоичного числа слід поставити у відповідність номер вершини (порядок не має значення). Нагадаємо, що вершини s та t тут не беруть участі, оскільки вони вже набули позначок і відповідно до них розподілені в підмножини: s  N1, t  N2.

Алгоритм формулюється в такий спосіб.

Крок 0. Надамо джерелу (вершині s) позначку “0”, а стокові (вершині t) –позначку “1”. Думаємо значення лічильника перерізів дорівнюваним С = 0.

Крок 1. Утворимо двійкове подання числа С і сортуємо вершини у відповідності з позначками. Визначаємо пропускну здатність перерізу для дістаного варіанта розподілу вершин як суму пропускних здатностей дуг (ребер), що складають розглядуваний переріз.

Крок 2. Збільшуємо значення змінної С на одиницю. Якщо С=2^(n-2), перехід до кроку 3, в противному разі – до кроку 1.

Крок 3. Серед дістанох значень {Mi (N1, N2)} обираємо найменше.

Роздивимося приклад, що ілюструє роботу алгоритму.

1	1	2	3	4	5	6
1	0	10	5	3	0	1
2	10	0	0	2	4	0
3	5	0	0	3	6	0
4	3	2	3	0	0	0
5	0	4	6	0	0	4
6	1	0	0	0	4	0

 Нехай потрібно оцінити пропускну здатність поміж джерелом s та стоком t в неорієнтованій мережі, модель і матриця пропускних здатностей ребер, якої показані на рис. 2.11

 Рисунок 2.11

 

Покладемо S:=>0; t:=>1.

Комбінація позначок вершин для всіх можливих перерізів і величини їхніх пропускних здатностей зведено в таблицю 2.1.

Таблиця 2.1

Номери Перерізів	Двійкові комбінації				Мi(N1N2)	Так, наприклад, нульовій по
	Номери вершин					порядку переріз буде
	3	4	5	6		характеризуватися у
0	0	0	0	0	16	відповідності із символікою,
1	0	0	0	1	21	наведеною в таблиці 2.1,
2	0	0	1	0	22	наступним поділом вершин
3	0	0	1	1	19	на підмножини:
4	0	1	0	0	20	N1 =(1,3,4,5,6); N2 =(2)
5	0	1	0	1	25	Цей переріз становлять
6	0	1	1	0	30	ребра: (1,2), (4,2), (5,2).
7	0	1	1	1	23	Сумарна пропускна
8	1	0	0	0	30	здатність цих ребер дорівнює 16.
9	1	0	0	1	35	Наступний переріз характери-
10	1	0	1	0	24	зуется поділом
11	1	0	1	1	21	N1=(1,3,4,5); N2 =(2,6)
12	1	1	0	0	21	Він містить ребра: (1,2), (1,6),
13	1	1	0	1	33	(4,2), (5,2), (5,6) котрі визначають
14	1	1	1	0	23	пропускну здатність перерізу
15	1	1	1	1	19	відповідно дорівнюючу 21.

 

Як очевидно з таблиці 2.1 найменшу величину пропускної здатності має переріз під номером 0. Він і визначає пропускну здатність заданої мережі.

Примітка. Слід зазначити, що вищевикладений спосіб дістання сукупності ребер що входять в певний переріз породжує ребра, які можуть бути відсутніми у фізичному графі. Ці ребра можна або вилучити з розгляду, або враховувати з нульовими пропускними здатностями.

 

Комплексне завдання