Автор работы: Пользователь скрыл имя, 01 Марта 2014 в 02:19, курсовая работа
Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждении о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса.
Введение…………………………………………………………………………3
Теоретическая часть……………………………………………........……....4
История возникновения теории графов…………………………….….4
Основные понятия теории графов……………………………………...6
Основные теоремы теории графов……………………………………..9
Способы предоставления графов в компьютере…………………......13
Требования к предоставлению графов………………….......…..13
Матрица смежности……………………………………………...13
Матрица инциденций…………………………………………….14
Списки смежности………………………………………………..14
Массив дуг……………………………………………………......14
1.5. Обзор задач теории графов……………………………………………15
1.6. Программа определения кратчайшего пути в графах…………….…17
1.6.1. Язык программирования Delphi……………………………....…17
1.6.2. Программа «Определения кратчайшего пути в графе»……......19
Заключение……………………………………………………………………..24
Практическая часть………………………………………………………....27
Общая характеристика задачи………………………………………....
Описание алгоритма решения задачи………………………………....