Page 104 - 4204

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

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

ЕЛЕМЕНТАМИ ТЕОРІЇ ГРАФІВ

8.1. Основні поняття

11
Теорія графів – розділ математики, що вивчає властивості

графів (сукупність об’єктів із зв’язками між ними). Визначення

графу є настільки загальним, що цим терміном можна описувати

безліч подій та об’єктів для вирішення зовнішньо несхожих задач

повсякденного життя.

За останні десятиліття теорія графів, як і вся дискретна мате-

матика загалом, набула значного розвитку. Це пов’язано з тим,

що теорія графів, народившись під час розв’язання головоломок і

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

ним і потужним засобом вирішення задач, що відносяться до ши-

рокого кола питань. У вигляді графів можна інтерпретувати, на-

приклад, схеми дорожньо-транспортних чи електричних мереж,

географічні карти і молекули хімічних сполук, зв’язки між людь-

ми та організаціями і багато що інше. Це привело до широкого

використання теорії графів у фізиці і кібернетиці, хімії і біології,

економіці і статистиці та інших науках. Особлива важлива роль

теорії графів у сучасному програмуванні, зокрема у задачах, що

вирішуються в ГІС.

11
Граф (лат. graph) – у дослівному перекладі графік, діаграма, схема.

103