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

Рисунок 3.3 - Головне вікно програми після виконання алгоритму Прима

Як можна відмітити, окрім текстової інформації з переліком ребер, остове дерево відмічено також і на графі.

Файл з графом з технічної точки зору є текстовим файлом з розширенням *.grf та мае певну структуру. Для побудованого вище графу вміст файлу наведено на рисунку 3.4

Рисунок 3.4 - Приклад файлу, що зберігає побудований граф

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

перше число: індекс вершини графа;

друге та третє числа: координати X та Y для зображення вершини на площині;

трете число: кількість суміжних вершин;

останні числа: пари чисел вигляду <індекс суміжної вершини> <вага ребра>, кількість пар відповідає кількості суміжних вершин.

Усі числа в рядках відділені один від одного одним пробілом.

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

ВИСНОВКИ

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

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

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

В якості подальшого розвитку системи можна запропонувати візуалізацію роботи алгоритмів для підвищення дидактичної цінності розробленої програми. Результати роботи можуть бути використані під час викладання курсу «Дискретна математика».

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

1.           Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клиффорд. Алгоритмы: Построение и анализ, 2-е издание.: Пер. с англ. - М.: ИД «Вильямс», 2005. - 1296 с.

.             Берж К. Теорія графів і її застосування. - М.: МУЛ, 1962.

.             Зиков А. А. Теорія кінцевих графів. - Новосибірськ: Наука, 1969.

.             Касаткін В. Н. Незвичайні задачі математики. - К.: Радянська школа, 1987.

.             Оре О. Графи і їх застосування. - М.: Світ, 1965.

.             Реньє А. Трилогія про математика. - М.: Світ , 1980.

.             Роббинс Джон. Отладка приложений для Microsoft.NET и Microsoft Windows - М. Русская Редакция, 2004. - 736 с.

.             Нортрап Тони, Вилдермьюс Шон, Райан Билл. Основы разработки приложений на платформе Microsoft.NET Framework - Питер, Русская Редакция, 2007. - 864 с.

.             Кристиан Гросс. C# 2008 и платформа.NET 3.5 Framework: от новичка до профессионала, 2-е издание - Вильямс, 2009. - 897 с.

.             Джимми Нильссон. Применение DDD и шаблонов проектирования: проблемно-ориентированное проектирование приложений с примерами на C# и.NET - Вильямс, 2007. - 429 с.

.             Дон Бокс, Крис Селлз. Основы платформы.NET, том 1. Обще языковая исполняющая среда. - Вильямс, 2003. - 288 с.

.             Роберт Седжвик. Фундаметальные алгоритмы на С++. Часть 5. Алгоритмы на графах - ДиаСофтЮП, 2002. - 496 с.

.             Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. Изд.2, испр. - 2009. 392 с.

.             Харари Фрэнк. Теория графов - Едиториал УРСС, 2003. - 297 с.

.             Кристофидес Н. Теория графов. Алгоритмический подход. Перевод на русский язык. - Наука, 1989. 241 с.

.             Камерон П. Теория графов. Теория кодирования и блок-схемы. Перевод на русский язык. - Наука, 1980. 140 с.

.             Акимов О.Е. Дискретная математика: логика, группы, графы, фракталы. - Едиториал УРСС, 2005. - 655 с.

.             Харари Ф. Теория графов: Перевод с английского. - Едиториал УРСС, 2006. - 300 с.

.             Скакунов Александр. Алгоритмы и структуры данных. - Едиториал УРСС, 1996. 357 с.

.             Уоррен Генри С. Алгоритмические трюки для программистов. - Диалектика-Вильямс, 2003. - 288 с.

.             Visual Studio .NET: разработка приложений баз данных. -СПб.: БХВ-Петербург, 2003. - 544 с.: ил.

.             Visual Basic .Net: учебный курс / В.Долженков, М.Мозговой. - СПб.: Питер, 2003. - 264 с.