о-економічних проблем.
Розвиток теорії графів в основному зобов'язана великому числу всіляких додатків. Мабуть, з усіх математичних об'єктів графи займають одне з перших місць в якості формальних моделей реальних систем.
Графи знайшли застосування практично у всіх галузях наукових знань: фізиці, біології, хімії, математики, історії, лінгвістиці, соціальних науках, техніці і т.п. Найбільшою популярністю теоретико-графові моделі використовуються при дослідженні комунікаційних мереж, систем інформатики, хімічних і генетичних структур, електричних ланцюгів і інших систем мережевої структури.
Мета курсового проекту полягає в закріпленні практичних умінь і навичок у знаходженні остова мінімальної ваги за допомогою алгоритму Краскала, у розробці програми мовою Delphi для аналітичного і графічного рішень нашої поставленого завдання. Використання комп'ютерних технологій для вирішення даних завдань скорочує зусилля і час людини, а це не мало важливо в справжні час.
У курсовому проекті в розділі В«Постановка завданняВ» розглядається теоретичний матеріал за темою В«графового моделі. Остов мінімальної ваги В», у розділіВ« Алгоритм знаходження В» розглядаються алгоритми знаходження В«Остов мінімальної вагиВ», у розділі В«Інструментальні програмні засобиВ» вибираються інструментальні засоби для розробки програмного продукту, в розділі В«Операційна середу моделювання В»визначаться інтерфейс програмного продукту, в розділі В«Контрольна завдання моделюванняВ» формулюється завдання для її вирішення вручну і за допомогою програмного продукту.
1 Постановка задачі моделювання
1.1Основние поняття теорії графів
Графом називається алгоритмічна модель, що складається з безлічі вершин (вузлів) v і з'єднують їх ребер e . Ребро - невпорядкована пара вершин графа.
Ребра називаються суміжними, якщо вони мають спільну вершину. Вершини називаються суміжними, якщо є ребро їх з'єднуюче. Ребро, яке з'єднує вершини, називається інцідентним цим вершин, а вершини - інцідентние цьому ребру.
Граф G '(v', e ') є остовом мінімальної ваги графа G (v, e), якщо v '= v і e' - є підмножина ребер мінімальної ваги і кількості, що з'єднують всі вершини. Кістяком мінімальної ваги може бути мережа мінімальної вартості, в матриці з'єднання якої cij = cji.
Граф G = називається орієнтованим (орграфом), якщо знайдеться дуга (a, b) ГЋR така, що (b, a) ГЏR.
Якщо ж відношення R симетрично, тобто з (a, b) ГЋR слід (b, a) ГЋR, то граф G називається неорієнтованим (Неорграфом). p> Зв'язний граф - граф, у якого для будь-яких двох різних вершин існує ланцюг (Послідовність суміжних вершин), що з'єднує їх. p> Для вирішення даної задачі моделювання буде використаний неорієнтоване зв'язний граф.
1.2 Представлення графів
Існує чотири базових уявлень графів в пам'ят...
