Page 106 - 4204

ЛЕКЦІЯ 8. ЗАДАЧІ МЕРЕЖЕВОГО АНАЛІЗУ З ЕЛЕМЕНТАМИ ТЕОРІЇ ГРАФІВ

Класичні задачі мережного аналізу – це оптимізація марш-

рутів (знаходження найкоротшого чи найбільш вигідного марш-

руту), а також обчислення “зон досяжності” в мережі.

Математично мережі описуються теорією графів, а рішення

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

ня. Наведемо елементарні поняття теорії графів.

Граф – це множина об’єктів довільної природи, що назива-

ються вершинами графа, і позв’язаних між собою відношеннями

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

формі схеми, що складається з вершин, вузлів, ребер, дуг. 

Вершини (англ. Vertex) – це об’єкти графа. На схемі їх зазви-

чай зображають точками або кружками.

Ребро (англ. Edge) – це лінія, що зв’язує точки (об’єкти гра-

фа). Ребра представляють відношення між об’єктами.

Дуга (англ. Arc) – це ребро з певною орієнтацією (напрям-

ком) відносно її кінцевих вершин.

Вузол (англ. Node) – це вершина, загальна для двох і більшо-

го числа дуг. У вузлах сходяться дуги.

Кількість вершин графа називають його порядком.

Наприклад, якщо глянути на карту, то зразу кидається в очі мережа

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

фа.

Вершини, що мають спільне ребро, називаються суміжними.

105