Дипломная (вкр): Алгоритми на графах та їх практичне застосування

Алгоритми на графах та їх практичне застосування

ЗМІСТ

ВСТУП

. Загальний огляд проблеми та обґрунтування вибору програмних засобів

.1 Значення алгоритмів на графах

.2 Визначення та способи представлення графів

.3 Огляд програмних засобів

. Основні алгоритми на графах

.1 Пошук завширшки

.2 Пошук в глибину

.3 Побудова мінімального остового дерева. Алгоритм Прима

.4 Алгоритм Дейкстри

.5 Модель Флойда-Уоршалла

. Програмна реалізація алгоритмів

.1 Огляд можливостей мови програмування

.2 Опис функцій програмної моделі

.3 Інтерфейс програми

ВИСНОВКИ

ПЕРЕЛІК ВИКОРИСТАНИХ ДЖЕРЕЛ

ВСТУП

Спробуйте намалювати „заклеєний конверт” одним розчерком пера, тобто не відриваючи ручки від паперу й не проводячи двічі один і той самий відрізок. Такого роду запитання з давніх-давен цікавили математиків.

Зрозуміло, часто трапляється, що потреби практики підштовхують розвиток математики. Яскраві приклади цього - теорії, створені М. Келдишем для авіаконструкторів. Досить часто поняття математики виникали з необхідності - так було з векторами, логарифмами, тригонометрією... Проте, нерідко математика є відірваною від реального життя, а тоді раптом виявляється, що в хащі неправдоподібності її все таки не занесло. Хрестоматійним прикладом є вчення про графи.

Декілька століть тому математиків, які досліджували дану проблему називали диваками і мрійниками. А сьогодні сучасні досягнення теорії графів використовуються у різних галузях знань, що підкреслює наукову та практичну значимість цієї проблеми.

В наш час теорія графів є дуже актуальною. Вона використовується у багатьох сферах людського життя для опису взаємозв’яків між об’єктами, процесами чи подіями. Граф - це досить чітка модель для вивчення окремих явищ навколишньої дійсності. Тому темою моєї роботи є „Алгоритми на графах та їх практичне застосування”, адже теорія графів має не тільки наукову, а й практичну цінність. Останнім часом зв’язані з графами методи досліджень використовуються не тільки в математиці, але і у фізиці, хімії, біології, географії та інших науках.

Метою дослідження є розробка програмного продукту, що дозволяє автоматизувати процес створення та збереження графів а також виконувати основні алгоритми на графах.

Для досягнення поставленої мети в роботі вирішені наступні задачі:

розглянуті і проаналізовані підходи до рішення задачі;

обґрунтовано вибір технічних засобів для рішень завдань;

визначені основні поняття теорії графів та засоби їх представлення у комп’ютерних програмах;

визначена структура даних для вирішення поставленої задачі;

розроблено програмний засіб побудови, відображення та використання графів за допомогою середовища Microsoft Visual Studio 2010 а також намічені шляхи його подальшого розвитку.

Об’єктом дослідження в даній дипломній роботі виступає теорія графів, основні алгоритми теорії графів та їх застосування при розв’язуванні задач.

Предметом дослідження є застосування теорії графів при розв’язанні завдань різних видів та вивчення елементів теорії графів.

Структура роботи визначається логікою проведеного дослідження і відображено в змісті, який складається з вступу, трьох основних розділів, висновків і списку використаних джерел.

У першому розділі розглянуто коло питань пов'язаних з формальним визначенням, способами подання графів та обґрунтовується вибір програмних засобів.

У другому розділі дипломної роботи наведені основні алгоритми на графах та можливості їх практичного застосування.

У третьому розділі наведено програмну реалізацію алгоритмів та можливості мови програмування Visual Basic .Net, які є вирішальними при програмуванні алгоритмів.

Отримані результати можуть бути впроваджені в практику Горлівського регіонального інституту під час вивчення змістовного модуля «Теорія графів».

1. Загальний огляд проблеми та обґрунтування вибору програмних засобів

.1 Значення алгоритмів на графах

Передусім, декілька слів про те, як виникає поняття графа з природних умов завдань. Наведемо декілька прикладів.

Нехай ми маємо карту доріг, в якій для кожного міста вказана відстань до усіх сусідніх з ним. Тут два міста називаються сусідніми, якщо існує дорога, що сполучає безпосередньо ці два міста.

Аналогічно, можна розглянути вулиці і перехрестя усередині одного міста. Помітимо, що можуть бути вулиці з одностороннім рухом.

Мережа комп'ютерів, сполучених дротяними лініями зв'язку.

Набір слів, кожне з яких починається на певну букву і закінчується на цю ж або іншу букву.

Множина кісток доміно. Кожна кістка має 2 числа: ліву і праву половину кістки.

Пристрій, що складається з мікросхем, сполучених один з одним наборами провідників.

Генеалогічні дерева, що вказують споріднені стосунки між людьми.

І, нарешті, власне графи, що вказують стосунки між якими або абстрактними поняттями, наприклад, числами.

Отже, неформально, граф можна визначити як набір вершин (міста, перехрестя, комп'ютери, букви, цифри кости доміно, мікросхеми, люди) і зв'язків між ними: дороги між містами; вулиці між перехрестями; дротяні лінії зв'язку між комп'ютерами; слова, що починаються на одну букву і закачуються на іншу або цю ж букву; провідники, що сполучають мікросхеми; споріднені стосунки, наприклад, Олексій - син Петра. Двонаправлені зв'язки, наприклад, дороги з двостороннім рухом, прийнято називати ребрами графа; а однонапрямлені зв'язки, наприклад, дороги з одностороннім рухом, прийнято називати дугами графа.

З розвитком комп’ютерної техніки та комп’ютеризацією виробництва і інших галузей людської діяльності, неперервно зростає роль дискретної математики як теоретичної основи для побудови алгоритмів і написання комп’ютерних програм. Теорія графів - дуже важливий розділ дискретної математики, особливістю якого є геометричний підхід до вивчення об’єктів. Діаграми графа подібно до геометричних рисунків дозволяють одержати наочне представлення до різного роду задач.

Родоначальником теорії графів прийнято вважати Леонарда Ейлера, який у 1736 році розв’язавши життєву задачу про Кенігсберзькі мости, встановив властивості зв’язаного графа та зробив деякі загальні висновки.

На сьогоднішній час графи дуже зручно використовувати для розв’язання задач різних видів. Теорія графів є дуже актуальною, її широко застосовують не тільки у самій математиці, а й в інших природничих науках, зокрема, у фізиці, хімії, географії, біології, картографії та в багатьох інших науках. Так, наприклад, для побудови структурних формул хімічних елементів, для складання найбільш вигідних транспортних маршрутів, при моделюванні складних технологічних процесів, у програмуванні, в електротехніці - для конструювання друкованих схем, а також при вивчені послідовного і паралельного з’єднання провідників.

Граф є математичною моделлю найрізноманітніших об’єктів, явищ і процесів, що досліджуються і використовуються в науці, техніці та на практиці. Графи дозволяють будувати математичну модель зв’язків між заданими елементами.

Наприклад, у вигляді графа можуть бути зображені електричні, транспортні, інформаційні і комп’ютерні та інші мережі, карти автомобільних, залізничних, повітряних шляхів, лабіринти, моделі кристалів, структури молекул хімічних речовин і т.д.

Прикладами застосування теорії графів є пошук зв’язних компонентів та пошук найкоротших, „найдешевших” та „найдорожчих” шляхів у комунікаційних мережах. Для побудови таких шляхів використовуються різноманітні алгоритми на графах.

Процес розробки будь-яких алгоритмів супроводжується зображенням його в схематичному вигляді: блок-схема, дерево рішень, та інше. Останнім часом значно збільшилась кількість засобів, які дозволяють суттєво полегшити процес схематичного зображення алгоритмів. Деякі з них здатні не тільки зображати алгоритм в одному з перечислених вище виглядів, а й генерувати вихідних код на одній з відомих мов високого рівня.

Цей процес не рідко може супроводжуватися попереднім проведенням синтаксичного аналізу коду, для виявлення і виправлення помилок. Також деякі із засобів дозволяють виконувати зворотну генерацію, тобто програма отримує вихідний код, на деякій мові високого рівня, аналізує його і дозволяє зобразити алгоритм у схематичному вигляді.

Алгоритм - це однозначна кінцева послідовність точно визначених кроків або дій які забезпечують вирішення завдання при наявності вихідних даних за кінцевий проміжок часу.

Основні властивості алгоритму:

. Масовість - алгоритм повинен бути застосований для цілого класу однотипних задач ;

. Закінченість - алгоритм повинен складатися з кінцевого числа кроків, кожен з яких виконується за кінцевий проміжок часу.

. Результативність - по закінченні роботи алгоритму повинен бути отриманий певний результат.

. Однозначність - застосування алгоритму до одних і тих же вихідних даних завжди повинно давати один і той же результат.

. Правильність - застосування алгоритму до правильних вихідних даних або допустимих вихідних даних повинно приводити до отримання необхідних результатів. Доказ правильності алгоритму - один із найбільш складних етапів його створення. Найбільш поширена процедура правильності алгоритму - це обґрунтування правомірності і перевірка правильності виконання кожного з кроків на наборі тестів, підібраних так, щоб охопити всі допустимі вхідні дані і всі допустимі вихідні дані.

. Ефективність - алгоритм повинен забезпечувати рішення завдання за мінімальний проміжок часу з мінімальними витратами пам'яті. Для оцінки алгоритмів існує багато критеріїв. Найчастіше оцінка алгоритму полягає в оцінці часових витрат на вирішення завдання в залежності від «розміру» вихідних даних. Використовується також термін, тимчасова здатність і «трудомісткість алгоритму». Фактично ця оцінка зводиться до оцінки кількості основних операцій, які виконуються алгоритмами, оскільки кожна конкретна операція виконується за кінцевий заздалегідь відомий час.

Алгоритм вирішення задачі виходить більш ефективним, якщо користуватися методами покрокової розробки, суть якого полягає в тому, що алгоритм розробляється «зверху вниз». Спочатку визначається загальний підхід до вирішення завдання, потім виділяються окремі самостійні частини, які виконують якусь кінцеву обробку даних. Кожна із виділених частин у свою чергу може розбиватися на окремі частини. Такий підхід дозволяє розбити алгоритм на частини (модулі), кожна з яких вирішує самостійну підзадачу. Кожен з модулів реалізується у вигляді окремої процедуру або функції. Тоді рішення задачі складається з послідовного виклику процедур. Програма, що реалізує такий алгоритм, називається структурованою програмою.

.2 Визначення та способи представлення графів

граф алгоритм мова програмування

Перш за все, дамо формальне визначення та способи представлення графів. З формальної точки зору граф є впорядкованою парою

= (V, Е)                                    (1.1)

Як правило, дві вершини, пов'язані між собою ребром, рівноправні, і саме тому такі графи називаються неорієнтованими: немає ніякої різниці між "початком" і "кінцем" ребра. Ребра неорієнтованого графа, частіше усього званого просто графом, можна проходити в обох напрямах. В цьому випадку ребро - це неврегульована пара вершин, його кінців. У орієнтованому графові, або орграфі, ребра є впорядкованими парами вершин : перша вершина - це початок ребра, а друга - його кінець. Далі ми скорочено говоритимемо просто про ребра, а орієнтовані вони або ні буде зрозуміле з контексту. Приклади існування графів в оточуючому нас середовищі наведено у таблиці 1.1

Таблиця 1.1 - Приклади неорієнтованих графів

Для візуального представлення графа його малюють, а не задають їх множинами. Вершини зображуватимемо кружечками, а ребра - відрізками ліній. Усередині кружечків записані мітки вершин. Ребра орієнтованого графа забезпечуються стрілками, що вказують допустимий напрям руху по ребру. На рисунку 1.1 зображено графічне представлення неорієнтованого (а), орієнтованого (б) і взваженного (в) графу.

а)б)

в)

Рисунок 1.1 - Приклад зображення графів

У графі важливий тільки факт наявності зв'язку між двома вершинами. Від способу зображення цього зв'язку структура графа не залежить. Наприклад, три графи на рис. 1.2 співпадають, а два графи на рис. 1.3 - різні.

Рисунок 1.2 - Три способу зображення одного графа

Рисунок 1.3 - Приклад двох різних графів

З приведеного вище визначення витікає, що в класичних графах не буває петель - ребер, що сполучають деяку вершину саму з собою (рис. 1.4). Крім того, в класичному графові не буває двох різних ребер, що сполучають одну і ту ж пару вершин.

Рисунок 1.4 -Псевдограф

Ребро е і вершина v називаються інцидентними один одному, якщо вершина v є одним з кінців ребра е.тБудь-якому ребру інцидентно рівно дві вершини, а ось вершині може бути інцидентно довільна кількість ребер, це кількість і визначає міра вершини. Ізольована вершина взагалі не має інцидентних нею ребер (її міра дорівнює 0 ).

Дві вершини називаються суміжними, якщо вони є різними кінцями одного ребра(іншими словами, ці вершини інцидентні одному ребру). Аналогічно, два ребра називаються суміжними, якщо вони інцидентні одній вершині.

Шлях в графі це послідовність вершин (без повторень), в які будь-які дві сусідні вершини суміжні. Наприклад, в графові, зображеному на рисунку 1.2, є два різні шляхи з вершини a в вершину с: adbc та abc. Вершина v досяжна з вершини u, якщо існує шлях, що починається в u та що закінчується в v. Граф називається зв'язним, якщо усі його вершини взаємно досяжні.

Компонента зв’язності - це максимальний зв'язний підграф. У загальному випадку граф може складатися з довільної кількості компонент зв'язності. Помітимо, що будь-яка изолированнаявершина є окремою компонентою зв'язності. На рисунку 1.5 зображений граф, що складається з чотирьох компонент зв'язності: [abhk], [gd], [c]і [f].

Довжина шляху - кількість ребер, з яких цей шлях складається. Наприклад, довжина вже згаданих шляхів adbc і abc (див. рис. 1.2) - 3 і 2 відповідно.

Рисунок 1.5 - Незв’язний граф

Говорять, що вершина v належить k -му рівню відносно вершини u, якщо існує шлях з u в v довжиною рівно k ребер. Одна і та ж вершина може відноситися до різних рівнів. Наприклад, в графові, зображеному на рисунку 1.2, відносно вершини a існує 4 рівні: