Основні поняття теорії графів. Інструментальні програмні засоби. Блок-схема алгоритму моделювання. Операційна середу моделювання. Контрольна задача моделювання
Введення
В даний час дослідження в областях, що традиційно відносяться до математики, займають усе більш помітне місце. Проблема вибору оптимального варіанта розв'язання відноситься до числа найбільш актуальних техніко-економічних проблем.
Розвиток теорії графів в основному зобов'язана великому числу всіляких додатків. Мабуть, з усіх математичних об'єктів графи займають одне з перших місць в якості формальних моделей реальних систем.
Графи знайшли застосування практично у всіх галузях наукових знань: фізики, біології, хімії, математики, історії, лінгвістиці, соціальних науках, техніці і т.п. Найбільшою популярністю теоретико-Графова моделі використовуються при дослідженні комунікаційних мереж, систем інформатики, хімічних і генетичних структур, електричних ланцюгів і інших систем мережевої структури.
Мета курсового проекту полягає в закріпленні практичних умінь і навичок в знаходженні остову мінімальної ваги за допомогою алгоритму Краскала, в розробці програми на мові 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 називається неорієнтованим (неорграфом).
Зв'язний граф - граф, у якого для будь-яких двох різних вершин існує ланцюг (послідовність суміжних вершин), з'єднує їх.
Для вирішення даної задачі моделювання буде використаний неорієнтований зв'язний граф.
1.2 Представлення графів
Існує чотири базових уявлень графів в пам'яті машини: матриця інцидентності, матриця суміжності, матриця списків суміжності і зв'язані списки суміжності. Вони розрізняються швидкістю виконання операцій над елементами вистави і об'ємом займаної пам'яті.
Для вирішення поставленого завдання моделювання більше всього підходить уявлення графів в пам'яті машини у вигляді матриці суміжності, а саме матриця ваг.
Матриця суміжності - матриця розміром, елементи якої рівні 1, якщо i-а вершина суміжно з j-ой, і 0 у противному випадку.
Матриця суміжності є симетричною і досить просто може використовуватися для введення та обробки на ЕОМ. Для випадку зваженого графа замість 1 використовується значення вагової функції, і така матриця називається матрицею ваг. У поставленому завданню будемо використовувати матрицю ваг.
1.3 Алгоритм знаходження остова мінімального
ваги у зваженому графі
Для знаходження остову мінімальної ваги за допомогою методу Краскала потрібно виконати наступні кроки:
1.Помечают вершину початку побудови кістяка. Серед ребер, інцидентних поміченої вершині, знаходять ребро мінімальної ваги для остову. Позначають нову вершину, інцидентності цього ребру. Вершина нова, якщо до ній раніше не зверталися.
2.Смотрят, чи всі вершини помічені. Якщо так, то закінчують пошук, якщо ні, то переходять до кроку 3.
3.Среді ребер, інцидентних поміченим вершин, за винятком ребер остова і ребер, що утворюють в остові цикл, знаходять ребро мінімальної ваги для остова. Позначають нову вершину, інцидентності цього ребру, і переходять до кроку 2.
4.При зміні вершини початку конфігурація остову мінімальної ваги не змінитися. Вона може змінитися при наявності в графі ребер однакового мінімальної ваги.
2 Інструментальні програмні засоби
2.1 Обгрунтування вибору інструментальних засобів
При виборі програмних засобів для розробки програми В«Пошук остову мінімальної ваги у зваженому графіВ» ​​необхідно враховувати можливості графічного відображення графа і остову в програмі, визначення модулів в програмі і зв'язки між ними, оцінки розвиненості апарату структур і типів даних, наявність спеціальних функцій здійснення обчислень, можливість збереження проміжних результатів. Крім того, програма повинна дозволяти користувачеві повертатися до попередніх етапів обчислень і зберігати вихідні дані на жорсткому диску.
Облік цих можливостей дозволить реалізувати основні функції розроблюваної програми, зробити її легкодоступною для використання, попередити виникнення логічних помилок, забезпечити надійність програмного забезпечення та його кодифікованість.
Вибір того чи іншого програмного засобу визначається як специфікою розробки програмного забезпечення та його популярністю, так і фінансовими можливостями розробника.
В даний час найбільш поширеною середовищем є Delphi.
Delphi - пакет засобів швидкої розробки додатків. До достоїнств відносяться зручний інтерфейс, висока швидкість роботи, велика кількість бібліотек компонентів, ефективність створюваних програм. Крім того, сувора тіпізірованность мови Object Pascal дозволяє компілятору вже на етапі компіляції виявити багато помилок, а також можливість працювати з покажчиками.
У порівнянні з іншими системами візуального проектування середу Delphi проста і ефективна, а написані за допомогою неї програми мають невеликі розміри і високу продуктивність. Так само в Delphi існує велика бібліотека компонентів (командні кнопки, поля редагування, перемикачі і т.д.). За допомогою компонентів забезпечуються зручність інтерфейсу, наочність роботи програм, робота зі створення інтерфейсу скорочується до розстановки компонентів на формі.
Крім того, в Delphi є розвинені засоби для роботи з графічними можливостями Windows. У стандартному графічному інтерфейсі Windows основою для малювання служить дескриптор контексту пристрою ніс і пов'язані з ним шрифт, перо і кисть. До складу входять об'єктно-орієнтовані надбудови над останніми, призначенням яких є зручний доступ до властивостей інструментів і прозора для користувача обробка всіх їх змін. Тому використання класу TCanvas, що є основою графічної системи Delphi, дозволяє виконати одну з основних функцій розроблюваної програми - наочне уявлення графа. Delphi також дає можливість використовувати традиційний набір функцій роботи з файлами, успадкований від Turbo Pascal. Що дозволяє зберігати результати роботи програми в файли на жорсткому диску. Крім того, в даному середовищі є можливість, поряд зі звичайними масивами, створювати динамічні масиви, які гратимуть роль матриці ваг ребер граф...
