ВВЕДЕНИЕ 3
1. НАЧАЛЬНЫЕ ЭТАПЫ РАЗВИТИЯ ГРАФОВ 6
1.1 Историческая справка 6
1.2 Основные термины и теоремы теории графов 14
2. СПОСОБЫ ПОИСКА КРАТЧАЙШЕГО ПУТИ В ГРАФАХ 21
2.1 Описание элементов интерфейса программы 21
2.2 Алгоритмы поиска в ширину 31
3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ГОТОВОГО ПРОДУКТА 38
3.1 Использование теории графов в учебной программе 38
3.2 Реализация программного кода 39
ЗАКЛЮЧЕНИЕ 43
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ 44
ПРИЛОЖЕНИЕ А MainForm 49
ПРИЛОЖЕНИЕ Б SmegGrafForm 60
ПРИЛОЖЕНИЕ В SetarcWeightForm 63
Когда людей спрашивают, что такое граф, большинство людей представляют график, или диаграмму, которая показывает производственную деятельность какого-нибудь предприятия, или свойства какой-нибудь математической формулы.
Но для людей, которые имеют дело и математикой, слово «граф» имеет совсем другое значение.
Начало теории графов как математической дисциплине было положено Эйлером в его знаменитом рассуждении о Кёнигсбергских мостах. Однако, эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен, главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это, благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. Развития формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок поддавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач - проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая другая проблема не вызывала столь многочисленных и остроумных работ в области теории графов. Благодаря своей простой формулировке и раздражающей неуловимости она до сих пор остается мощным стимулом исследований различных свойств графов.
Настоящее столетие было свидетелем неуклонного развития теории графов, которая за последние десять лет и даже двадцать вступила в новый период интенсивных разработок. В этом процессе явно заметно влияние
запросов новых областей приложений: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем биологии и психологии.
Данная работа состоит из трех глав.
В первой главе демонстрируется начальные этапы развития графов.
Вторая глава включает в себя описание алгоритмов и их применение.
Третья глава содержит код программы с детальным описание функций и формул, которые были использованы.
Для реализации программного комплекса использовался язык высокого уровня Delphi и среда разработки Borland Delphi 2007. Этот выбор обусловлен исходя из следующих критериев:
1. Среда разработки и язык позволяют быстро и качественно создавать пользовательский интерфейс высокого уровня, используя дизайнер форм, сводя к минимуму труд программиста.
2. Язык Delphi так же обладает рядом преимуществ по сравнению с Object Pascal, т.к. является более новым и более развитым языком.
3. В нём на очень высоком уровне реализованы механизмы безопасности кода.
4. Ещё одним несомненным плюсом является наличие русскоязычной развитой справочной системы, что значительно упрощает процесс программирования.
Цель работы: разработать приложение для решения задач с
использованием теории графов.
Достижение поставленной цели предполагает выполнение следующих
задач:
• изучить предметную область;
• проанализировать методы решения поставленной задачи;
• осуществить проектирование программного продукта;
• выбрать средства и технологии разработки;
• разработать программный продукт;
• провести комплексное тестирование программного продукта;
Объект исследования - решения задач с использованием теории
графов.
Предмет исследования - приложение для решения задач с использованием теории графов
Теория графов в настоящее время является интенсивно развивающимся разделом дискретной математики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации: коммуникационные сети, схемы электрических и электронных приборов, химических молекул, отношение между людьми и многое другое.
Т.е. учащиеся, добыв первоначальные знания с помощью занимательных задач, переходят к закреплению и развитию этих знаний на базе решения более сложных задач.
Теория графов привлекательна еще и тем, что в ней наряду с решенными задачами и проблемами существуют задачи нерешенные.
А это является малой долей изученного в данной теории и до сих пор остается мощным стимулом для дальнейших исследований различных свойств графов.
Современная теория графов находит ряд интересных и важных приложений в других разделах математики, физики, в теории жидких кристаллов, в молекулярной биологии, кибернетике, вычислительной технике и т.д.
