Введення
Визначення досяжності населеного пункту в системі односторонніх доріг розглядається за допомогою деякого математичного об'єкта, званого графом.
Граф - це сукупність непорожньої безлічі вершин і наборів пар вершин (зв'язків між вершинами).
Найбільш ефективним алгоритмом знаходження найкоротшого шляху є алгоритм Дейкстри.
Основне завдання даного курсового проекту: визначення досяжності населеного пункту в системі односторонніх доріг. Вирішити завдання можна засобом програмування. У цій роботі завдання було вирішено в середовищі C + + Builder.
1. Технічне завдання
Програма визначення досяжності населеного пункту в системі односторонніх доріг. Опис: дано кілька населених пунктів, з'єднаних між собою (довільним чином) односторонніми дорогами деякої довжини. Визначити, чи є населений пункт, з якого можна дістатися до кожного з решти пунктів, проїжджаючи не більше 100 км. Відобразити рішення графічно, виділивши кольором знайдений результат.
.1 Підстави для розробки
Підставою для розробки програми є завдання до курсового проекту з предмету «Програмування».
1.2 Функціональне та експлуатаційне призначення вироби
Перелік вимог користувача до програмного виробу.
Програма повинна забезпечувати:
зручний інтерфейс;
легкість у використанні;
оптимальність при використанні фізичних ресурсів комп'ютера.
1.3 Методологічні обмеження
програма алгоритм технічний
Часто трапляються завдання, в умовах яких задані деякі об'єкти і між деякими їх парами є певні зв'язки. Якщо об'єкти зобразити точками (вершинами), а зв'язки - лініями (ребрами), що з'єднують відповідні пари точок, то вийде малюнок, званий графом. Історію теорії графів прийнято обчислювати з 1736 р., коли Ейлер досліджував «завдання про кенігсберзькими мостах»: побудувати в графі циклічний шлях, що проходить по одному разу через кожне ребро. У середині 19-го століття Гамільтон зацікавився завданням побудови циклічного шляху, що проходить по одному разу через кожну вершину графа. В цей же час графи використовували для аналізу електричних ланцюгів (Кірхгоф) і хімічних молекул (Келі). Розвиток сучасної теорії графів відноситься до 30-м рокам 20-го сторіччя. Вони знайшли численні застосування в електротехніці, електроніці, біології, економіці, програмуванні і в інших областях.
Загальні відомості про графах
Граф G (рис. 1.1) задається множиною точок (вершин) х 1, х 2, ..., х n. (Яке позначається через Х) і безліччю ліній (ребер) а 1, а 2, ..., а m. (Яке позначається символом А), що з'єднують між собою всі або частину цих точок. Таким чином, граф G повністю задається (і позначається) парою (Х, А). Якщо ребра з безлічі А орієнтовані, що зазвичай показується стрілкою, то вони називаються дугами, і граф з такими ребрами називається орієнтованим графом.
Рис. 1.1 Граф G
Рис. 1.2 Шляхи і послідовності дуг
