ВОРОНЕЖСКИЙ ИНСТИТУТ ВЫСОКИХ ТЕХНОЛОГИЙ Факультет заочного и послевузовского обучения Курсовой проект
    По дисциплине: "Технология программирования"
    
     Тема: "Определение кратчайшего пути в графе" Воронеж 2004 г. СОДЕРЖАНИЕ ВВЕДЕНИЕ 3 1. ТЕОРИЯ ГРАФОВ. 4 1.1. Историческая справка. 4 1.2. Основные термины и теоремы теории графов. 9 2. ЗАДАЧИ НА ГРАФАХ. 15 2.1. Описание различных задач на графах. 15 2.2. Нахождение кратчайших путей в графе 16 3. ПРОГРАММА ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ В ГРАФЕ 19 3.1. Язык программирования Delphi. 19 3.2. Программа "Определение кратчайшего пути в графе" 20 ЗАКЛЮЧЕНИЕ 25 СПИСОК ЛИТЕРАТУРЫ 27 ПРИЛОЖЕНИЕ 28 Текст программы определения кратчайшего пути в графе 28 ВВЕДЕНИЕ
    Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждение о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач-проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая проблема не вызывала столь многочисленных и остроумных работ в области теории графов. Благодаря своей простой формулировке и раздражающей неуловимости она до сих пор остается мощным стимулом исследований различных свойств графов.
    Настоящее столетие было свидетелем неуклонного развития теории графов, которая за последние десять - двадцать лет вступила в новый период интенсивных разработок. В этом процессе явно заметно влияние запросов новых областей: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем психологии и биологии.
    Вследствие этого развития предмет теории графов является уже обширным, что все его основные направления невозможно изложить в одном томе. В настоящем первом томе предлагаемого двухтомного труда сделан акцепт на основные понятия и на результаты, вызывающие особый систематический интерес.
    По теории графов имеется очень мало книг; основной была книга Д. Кёнига (1936), которая для своего времени давала превосходнейшее введение в предмет. Довольно странно, что таких книг на английском языке до сих пор не было, несмотря на то, что многие важнейшие результаты были получены американскими и английскими авторами. 1. Теория Графов. 1.1. Историческая справка.
    
    ТЕОРИЯ ГРАФОВ - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Обычно её относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. ............