Page 104 - 4204
P. 104
ЛЕКЦІЯ 8. ЗАДАЧІ МЕРЕЖЕВОГО АНАЛІЗУ З ЕЛЕМЕНТАМИ ТЕОРІЇ ГРАФІВ
ЛЕКЦІЯ 8. ЗАДАЧІ МЕРЕЖЕВОГО АНАЛІЗУ З
ЕЛЕМЕНТАМИ ТЕОРІЇ ГРАФІВ
8.1. Основні поняття
11
Теорія графів – розділ математики, що вивчає властивості
графів (сукупність об’єктів із зв’язками між ними). Визначення
графу є настільки загальним, що цим терміном можна описувати
безліч подій та об’єктів для вирішення зовнішньо несхожих задач
повсякденного життя.
За останні десятиліття теорія графів, як і вся дискретна мате-
матика загалом, набула значного розвитку. Це пов’язано з тим,
що теорія графів, народившись під час розв’язання головоломок і
цікавих задач розважального характеру, стала простим, доступ-
ним і потужним засобом вирішення задач, що відносяться до ши-
рокого кола питань. У вигляді графів можна інтерпретувати, на-
приклад, схеми дорожньо-транспортних чи електричних мереж,
географічні карти і молекули хімічних сполук, зв’язки між людь-
ми та організаціями і багато що інше. Це привело до широкого
використання теорії графів у фізиці і кібернетиці, хімії і біології,
економіці і статистиці та інших науках. Особлива важлива роль
теорії графів у сучасному програмуванні, зокрема у задачах, що
вирішуються в ГІС.
11
Граф (лат. graph) – у дослівному перекладі графік, діаграма, схема.
103