Федеральне державне бюджетне освітня установа вищої професійної освіти «Сибірська державна автомобільно-дорожня академія
Факультет Інформаційні системи в управлінні
Спеціальність Інформаційна безпека
Кафедра Інформаційна безпека
Пояснювальна записка до курсової роботи
«Розробка програми для пошуку максимально віддалених вершин у графі» ??
Виконав: Галкін Кирило Андрійович
Перевірив Толкачова Олена Вікторівна
Омськ - 2013
Зміст
Введення
. Теорія графів
. 1 Орієнтований граф
. 2 Змішаний граф
. 3 Ізоморфні графи
. 4 Інші пов'язані визначення
. 5 Додаткові характеристики графів
. 6 Узагальнення поняття графа
. 7 Способи представлення графа в інформатиці
. Технічна реалізація
. 1 Алгоритм пошуку шляху
. 2 Класи і Діаграма класів
. 3 Методи класу GraphEdge
. 4 Методи класу GraphNode
. 5 Функції класу Graph
. 6 Методи класу GraphMaxDistanceFinder
. 7 Графічний інтерфейс
Висновок
Список літератури
Введення
Поява комп'ютерів стало проривом для всього людства. В даний час за допомогою них можливо проводити розрахунки з величезною швидкістю. Вони дозволяють вирішувати різноманітні завдання, однією з яких є пошук і складання шляхів від пункту А в пункт Б. Для таких завдань найбільш застосовна теорія графів.
Метою даної курсової роботи є розробка програмного продукту для пошуку максимально віддалених вершин у графі. Програмний продукт повинен мати графічний інтерфейс і підтримувати будь-які типи графів.
Додаток розроблений за допомогою мови програмування Microsoft Visual C #, так як функціонал даної мови програмування дозволяє максимально швидко вирішити завдання такого типу. Обраний нами мова програмування працює з бібліотекою Microsoft framework, яка включає в себе величезну кількість засобів для роботи з даними такого роду і дозволяє значно прискорити процес створення додатку.
В якості середовища розробки, була використана середу Microsoft Visual Studio версії 12, так як дана середу включає в себе широкий набір інструментів для управління і створення різних компонентів програмного продукту (графічний інтерфейс, Діаграма класів і т.п.)
1. Теорія графів
Граф - це сукупність непорожнього безлічі вершин і наборів пар вершин (зв'язків між вершинами). Об'єкти представляються як вершини, або вузли графа, а зв'язки - як дуги, або ребра. Для різних областей застосування види графів можуть відрізнятися спрямованістю, обмеженнями на кількість зв'язків і додатковими даними про вершини або ребрах. Багато структури, що представляють практичний інтерес в математики та інформатики, можуть бути представлені графами. Наприклад, будова Вікіпедії можна змоделювати за допомогою орієнтованого графа (орграф), в якому вершини - це статті, а дуги (орієнтовані ребра) - гіперпосилання.
Теорія графів не володіє усталеною термінологією. У різних статтях під одними і тими ж термінами розуміються різні речі. Нижче наведені найбільш часто зустрічаються визначення.
Граф, або неорієнтовані граф G - це впорядкована пара G:=(V, E), для якої виконані наступні умови: - це непорожнє безліч вершин або вузлів; - це безліч пар (у разі неорієнтованого графа- невпорядкованих) вершин, званих ребрами. (а значить і, E, інакше воно було б Мультімножество) зазвичай вважаються кінцевими множинами. Багато хороші результати, отримані для кінцевих графів, невірні (або яким-небудь чином відрізняються) для нескінченних графів. Це відбувається тому, що ряд міркувань стає помилковим у разі нескінченних множин.
Вершини і ребра графа називаються також елементами графа, число вершин у графі | V | - порядком, число ребер | E | - розміром графа.
Вершини u і v називаються кінцевими вершинами (або просто кінцями) ребра e= {u, v }. Ребро, у свою чергу, з'єднує ці вершини. Дві кінцеві вершини одного і того ж ребра називаються сусідніми.
Два ребра називаються сум...
