8.2. Засоби завдання графів. Зважені графи та мережі

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

Якщо наявність зв’язку між парою точок відображати через „1” а відсутність – через „0”, то у такому випадку граф можна задавати матрицею суміжності рис.8.4.

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

Рис.8.4

У декотрих випадках зручно зв’язки елементів зображувати у вигляді зваженого графа. Це граф, в якого кожному ребру відповідає деяке число , яке називається вагою цього ребра. Іноді вага зображується деякою функцією. Така матриця суміжності у зважених графах називається матрицею ваги.

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

8.3. Потоки на мережах. Поняття розрізу

Якщо у мережі задані пропускні спроможності усіх дуг , то потоком називається функція, що відображує -дугу числом , що відповідає властивостям

, (8.1)

, (8.2)

. (8.3)

Умова (8.1) означає, що потік не повинен перебільшувати величину для – дуги; умова (8.2) означає, що для будь-якої проміжної вершини мережі обсяг продукту (ресурсу), який входить до цієї вершини, має дорівнювати обсягу продукту, який виходить з цієї вершини; умова (8.3) означає, що загальна кількість продукту , яка виходить з початкової вершини мережі, дорівнює загальній кількості продукту, яка входить у кінцеву вершину . Ця кількість є величиною потоку мережі і називається потужністю потоку.

Визначимо поняття розрізу мережі.

Розглянемо мережу з одним джерелом та одним стоком . У такій мережі множину її вершин можна розбити на дві півмножини так:

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

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

.

Для будь-якого розрізу загальна величина потоку дорівнює

і не повинна перебільшувати пропускної спроможності, тобто величини розрізу

,

тому що

Приклад наведено на рис. 8.5.

5 До означеного розрізу з

4 2 та входить

3 множина дуг

2 2 ,

6 при цьому пропускна спромож-

ність дорівнює

Рис.8.5 .