Введення
В останні роки особливу важливість придбали ті розділи математики, які мають відношення до розвитку цифрових пристроїв, цифрового зв'язку і цифрових обчислювальних машин. Базою для викладання цих дисциплін поряд з класичними методами аналізу безперервних фізичних моделей стали алгебраїчні, логічні та комбінаторні методи дослідження різних моделей дискретної математики.
Значно зросла популярність теорії графів - гілки дискретної математики. Графи зустрічаються в багатьох областях під різними назвами: «структури» в цивільному будівництві, «мережі» - в електроніці, «соціограма» - у соціології та економіці, «молекулярні структури» - в хімії, «дорожні карти», електричні чи газові розподільні мережі і т.д.
Народившись при вирішенні головоломок та ігор, таких, наприклад, як задача про кенігсберзькими мостах і гра Гамільтона, теорія графів стала потужним засобом дослідження і вирішення багатьох завдань, що виникають при вивченні великих і складних систем. Для фахівців з обчислювальної техніки, інформаційних систем і систем цифрового зв'язку теорія графів - це зручний мову вираження понять з цієї області; багато результати теорії графів мають безпосередній зв'язок з завданнями, з якими їм доводиться стикатися. Графічна інтерпретація різних моделей графів дана на Рис. 1.1 б . Так у вигляді орієнтованих графів можна уявити будь-яку логічну або функціонально - логічну схему. На таких графових моделях можна, наприклад, оцінити швидкодію схеми. Блок-схема алгоритму може бути представлена ??імовірнісним графом, який дозволяє оцінити часові характеристики алгоритму, витрати процесорного часу, трудомісткість та інші. Графом типу «дерево» можна відобразити практично будь-яку структуру організації чи підприємства.
Широке застосування теорія графів одержала при дослідженні так званої проблеми оптимізації, що виникає при конструюванні великих систем як технічних, так і програмних, наприклад, таких, як компілятори.
У рамках цих досліджень були розроблені багато, невідомі раніше теоретико-графові поняття. Теорія графів має велику привабливість для фахівців в області проектування для побудови ефективних алгоритмів і аналізу їх складності. Використання апарату теорії графів зробило істотний вплив на розробку алгоритмів конструкторського проектування схем. Безпосереднє та детальне уявлення практичних систем, таких, як розподільні мережі, системи зв'язку, призводить до графів великого розміру, успішний аналіз яких залежить в рівній мірі, як від ефективних алгоритмів, так і від можливостей комп'ютерної техніки. Тому в даний час основна увага зосереджена на розробці та описі комп'ютерних алгоритмів аналізу графів. У зв'язку з цим основний упор в даному навчальному посібнику робиться на машинні способи представлення графів та алгоритми розв'язання задач на графах, легко реалізованих на ЕОМ.
1. Визначення графа і основні поняття
Для опису будови різних систем, що складаються з пов'язаних між собою елементів, часто використовують графічні схеми, зображуючи елементи точками (кружками, прямокутниками і т.д.), а зв'язки між ними - лініями або стрілками, що з'єднують елементи. При цьому виходять діаграми зразок тих, що показані на рис. 1.1. На даних діаграмах ні спосіб зображення...
