Нахождение кратчайшего пути

  • 16 янв. 2011 г.
  • 5783 Слова
ВОРОНЕЖСКИЙ ИНСТИТУТ ВЫСОКИХ ТЕХНОЛОГИЙ
Факультет заочного и послевузовского обучения

1 Курсовой проект

По дисциплине: «Технология программирования»

Тема: «Определение кратчайшего пути в графе»

2

Воронеж 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

2 1.1. Историческая справка.

ТЕОРИЯ ГРАФОВ - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теорияграфов находится сейчас в самом расцвете. Обычно её относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов-граф и егообобщения.
Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и другие). Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без...