Page 90 - 2589

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

вершини з найбільш коротким з’єднуючим ребром u . На
i
кожному з наступних кроків додаємо найкоротше з ребер u , при
i
приєднанні якого до вже наявних ребер не утворюється ніякого

циклу. Якщо є декілька ребер однакової довжини, вибираємо
будь-яке з них. Кожне дерево Q, побудоване таким чином,
називатимемо економічним деревом. Його довжина дорівнює

сумі довжин окремих ребер :
l (Q )  l (u )  ... l (u )
1 n 1 
Можна показати, що ніяке інше дерево, що сполучає ті ж

вершини, не може мати довжини, меншої довжини економічного

Рисунок 4.8 - До побудови дерева найменшої довжини

5.8 Транспортні мережі

5.8.1 Основні поняття
Транспортною мережею називається кінцевий граф без

петель, у якого :
1
1) існує одна і тільки одна така вершина що  x   (ця
0
вершина називається входом мережі);
2) існує одна і тільки одна така вершина z, що z  ;
3) кожній дузі графа u віднесено ціле число с (u )яке

називається пропускною спроможністю дуги u .
З поняттям транспортної мережі тісно пов'язано поняття

потоку. Нехай х - довільна вершина. Позначимо U  – множина
x
дуг, які входять в х, а через U  – множина дуг, які виходять із х.
x
Потоком по транспортній мережі називається функція (u ),
яка задовольняє умовам:

0  ( u ) c( u), u U ; (4.1)

90