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

ВОРОНЕЖСКИЙ ИНСТИТУТ ВЫСОКИХ ТЕХНОЛОГИЙ

Факультет заочного и послевузовского обучения

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

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

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

Воронеж 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. Историческая справка.

 

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

Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задачи о перевозках, задача о кругосветном путешествии и другие). Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторе­ний, полученный Л. Эйлером при реше­нии задачи о Кенигсбергских мостах. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ” Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может“. Кенигсбергские мосты схематически можно изобразить так:

 

 

 

Правило Эйлера:

1.       В графе, не имеющем вершин нечетных степеней, существует обход всех рёбер (причем каждое ребро проходится в точности один раз) с началом в любой вершине графа.

2.       В графе, имеющем две и только две вершины с нечетными степенями, существует обход с началом в одной вершине с нечетной степенью и концом в другой.

3.       В графе, имеющим более двух вершин с нечетной степенью, такого обхода не существует.

Существует еще один вид задач, связанных с путешествиями вдоль графов. Речь идёт о задачах, в которых требуется отыскать путь, проходящий через все вершины, причем не более одного раза через каждую. Цикл, проходящий через каждую вершину один и только один раз, носит название гамильтоновой линии( в честь Уильяма Роуэна Гамильтона, знаменитого ирландского математика прошлого века, который первым начал изучать такие линии). К сожалению, пока еще не найден общий критерий, с помощью которого можно было бы решить, является ли данный граф гамильтоновым, и если да, то найти на нём все гамильтоновы линии.

Сформули­рованная в середине 19 в. проблема четырех красок также выглядит как развле­кательная задача, однако попытки ее решения привели к появлению некоторых исследований графов, имеющих теоретическое и прикладное значение. Проблема четырех красок формулируется так: ”Можно ли область любой плоской карты раскрасить четырьмя цветами так, чтобы любые две соседние области были раскрашены в различные цвета?”. Гипотеза о том, что ответ утвердительный, была сформулирована в середине 19в. В 1890 году было доказано более слабое утверждение, а именно, что любая плоская карта раскрашивается в пять цветов. Сопоставляя любой плоской карте двойственный ей плоский граф, получают эквивалентную формулировку задачи в терминах графов: Верно ли, что хроматическое число любого плоского графа меньше либо равно четырёх? Многочисленные попытки решения задачи оказали влияние на развитие ряда направлений теории графов. В 1976 году анонсировано положительное решение задачи с использованием ЭВМ.

Другая старая топологическая задача, которая особенно долго не поддавалась решению и будоражила умы любителей головоломок, известна как “задача об электро -, газо - и водоснабжении”. В 1917 году Генри Э.Дьюдени дал ей такую формулировку. В каждый из трёх домов, изображенных на рисунке, необходимо провести газ, свет и воду.

Свет вода газ

Можно ли так проложить коммуникации, чтобы они, нигде не пересекаясь друг с другом, соединяли каждый дом с источниками электричества, газа и воды? Иначе говоря, можно построить плоский граф с вершинами в шести указанных точках? Оказывается, такой граф построить нельзя. Об этом говорится в одной очень важной теореме – так называемой теореме Куратовского. Теорема утверждает, что каждый граф, не являющийся плоским, содержит в качестве подграфа один из двух простейших пространственных графов:

 

 

В середине 19 в. появились работы, в которых при решении практических задач были получены результаты, относящиеся к теории графов. Так, например, Г. Кирхгоф при составлении полной системы уравнений для токов и напряжений в электрической схеме предложил по существу представлять такую схему графом и находить в этом графе остовные де­ревья, с помощью которых выделяются линейно независи­мые системы контуров. А. Кэли, исходя из задач подсчета числа изомеров предельных углеводородов, пришел к задачам перечисления и описания деревьев, обладающих заданными свойствами, и решил некоторые из них.

В 20 в. задачи, связанные с графами, начали возникать не только в физике, химии, электротехнике биологии, экономике, социологии и т.д., но и внутри математики, в таких разделах, как топология, алгебра, теория вероятностей, теория чисел. В начале 20 в. графы стали использоваться для представления некоторых математических объектов и формальной постановки различных дискретных задач; при этом наряду с термином «граф» употреблялись и другие термины, например, карта, ком­плекс, диаграмма, сеть, лабиринт. После выхода в свет в 1936 году монографии Д. Кёнига термин «граф» стал более употребительным, чем другие. В этой работе были систематизированы известные к тому времени факты. В 1936 году вышла небольшая брошюра Ойстена Оре, содержащая блестящее элементарное введение в теорию графов. В 1962 году в Англии была издана книга французского математика Клода Бержа “Теория графов и её приложение”. Обе книги, безусловно, представляют интерес для любителей занимательной математики. Сотни известных головоломок, на первый взгляд не имеющих ничего общего друг с другом, легко решаются с помощью теории графов.

В 20-30-х годах 20 в. появились первые резуль­таты, относящиеся к изучению свойств связности, планарности, симметрии графов, которые привели к форми­рованию ряда новых направлений в теории графов.

Значительно расширились исследования по теории графов в конце 40-х - начале 50-х годов, прежде всего в силу развития кибернетики и вычислительной техники. Благодаря развитию вычислительной техники, изучению сложных кибернетических систем, интерес к теории графов возрос, а проблематика теории графов существенным образом обогатилась. Кроме того, использование ЭВМ позволило решать возникающие на практике конкретные задачи, связанные с большим объемом вычислений, прежде не поддававшиеся ре­шению. Для ряда экстремальных задач теории графов были раз­работаны методы их решения, например, один из таких методов позволяет решать задачи о построении макси­мального потока через сеть. Для отдельных классов графов (деревья, плоские графы и т. д.), которые изучались и ранее, было показано, что решения некоторых задач для графов из этих классов находятся проще, чем для произвольных графов (на­хождение условий существования графов с заданными свойствами, установление изоморфизма графов и др.).

Характеризуя проблематику теории графов, можно отметить, что некоторые направления носят более комбинаторный характер, другие - более геометрический. К первым относятся, например, задачи о подсчете и перечислении графов с фиксированными свойствами, задачи о пост­роении графов с заданными свойствами. Геометриче­ский (топологический) характер носят многие циклы задач теории графов, например, графов обходы, графов укладки. Су­ществуют направления, связанные с различными клас­сификациями графов, например, по свойствам их разложе­ния.

Примером результата о существовании графов с фиксированными свойствами может служить крите­рий реализуемости чисел степенями вершин некоторого графа: набор целых чисел,  сумма которых четна, можно реализовать степенями вершин гра­фа без петель и кратных ребер тогда и только тогда, когда для любого r выполняется условие

Примерами задач о подсчете графов с заданными свойствами являются задачи о нахождении количеств неизоморфных графов с одинаковым числом вершин и (или) ребер. Для числа неизоморфных деревьев с n вершинами была получена асимптотическая формула  где C== 0,534948..., e== 2,95576...

Для числа Gn не­изоморфных графов без петель и кратных ребер с n вершинами было показано, что

Наряду с проблемами, носящими общий характер, в теории графов имеются специфические циклы задач. В одном из них изучаются различные свойства связности графов, исследуется строение графов по свойствам связности. При анализе надежности сетей связи, электронных схем, коммуникационных сетей возникает задача о нахождении количеств непересекаю­щихся цепей, соединяющих различные вершины графа. Здесь получен ряд результатов. Например, наименьшее число вершин, разделяющих две несмежные вершины графа, равно наибольшему числу непересекающихся (по вершинам) простых цепей, соединяющих эту пару вершин. Найдены критерии и построены эффективные алгоритмы установления меры связности графа (наи­меньшего числа вершин или ребер, удаление которых нарушает связность графа).

В другом направлении исследований теории графов изучаются маршруты, содержащие все вершины или ребра графа. Известен простой критерий сущест­вования маршрута, содержащего все ребра графа: в связном графе цикл, содержащий все ребра и проходя­щий по каждому ребру один раз, существует тогда и только тогда, когда все вершины графа имеют четные степени. В случае обхода множества вершин графа имеется только ряд достаточных условий существова­ния цикла, проходящего по всем вершинам графа по одному разу. Характерным специфическим направлением теории графов является цикл задач, связанный с раскрасками графов, в котором изучаются разбиения множества вершин (ребер), обладающие определенными свойствами, например, смежные вершины (ребра) должны принадлежать раз­личным множествам (вершины или ребра из одного множества окрашиваются одним цветом). Было доказано, что наименьшее число цве­тов, достаточное для раскраски ребер любого графа без петель с максимальной степенью a, равно Зa/2, а для раскраски вершин любого графа без петель и кратных ребер достаточно a+1 цветов.

Существуют и другие циклы задач, некоторые из них сложились под влиянием различных разделов математики. Так, под влиянием топологии производится изучение вложений графов в различные поверхности. Например, было получено необ­ходимое и достаточное условие вложения графа в пло­скость (критерий Понтрягина - Куратовского см. выше): граф является плоским тогда и только тогда, когда он не содержит подграфов, получаемых с помощью подразбиения ребер из полного 5-вершинного графа и полного двудольного графа с тремя вершинами в каждой доле. Под влиянием алгебры стали изучаться группы автоморфизмов графов. В частности, было доказано, что каждая конечная группа изоморфна группе автоморфизмов некоторого графа. Влияние теории вероятностей сказалось на ис­следовании графов случайных. Многие свойства были изучены для «почти всех» графов; например, было показано, что почти все графы с n вершинами связаны, имеют диаметр 2, обладают гамильтоновым циклом (циклом, проходящим через все вершины графа по одному разу).

В теории графов существуют специфические методы решения экстре­мальных задач. Один из них основан на теореме о мак­симальном потоке и минимальном разрезе, утверждаю­щей, что максимальный поток, который можно пропустить через сеть из вершины U в вершину V, равен минималь­ной пропускной способности разрезов, разделяющих вершины U и V. Были построены различные эффективные алгоритмы нахождения макси­мального потока.

Большое значение в теории графов имеют алгоритмические вопросы. Для конечных графов, т. е. для графов с конеч­ным множеством вершин и ребер, как правило, пробле­ма существования алгоритма решения задач, в том числе экстремальных, решается положительно. Решение мно­гих задач, связанных с конечными графами, может быть выполнено с помощью полного перебора всех допусти­мых вариантов. Однако таким способом удается ре­шить задачу только для графов с небольшим числом вершин и ребер. Поэтому существенное значение для теории графов имеет построение эффективных алгоритмов, на­ходящих точное или приближенное решение. Для некоторых задач такие алгоритмы построены, например, для установления планарности графов, определения изоморфизма деревьев, нахождения максимального потока.

Результаты и методы теории графов применяются при реше­нии транспортных задач о перевозках, для нахож­дения оптимальных решений задачи о назначениях, для выделения «узких мест» при планировании и управ­лении разработок проектов, при составлении оптимальных маршрутов доставки грузов, а также при моделировании сложных технология, процессов, в пост­роении различных дискретных устройств, в програм­мировании и т. д.

1.2. Основные термины и теоремы теории графов.

1.       Граф - Пара объектов G = ( X , Г ) ,где Х - конечное множество ,а Г –конечное подмножество прямого произведения Х*Х . При этом Х называется множеством вершин , а Г - множеством дуг графа G .

2.       Любое конечное множество точек (вершин), некоторые из которых попарно соединены стрелками , (в теории графов эти стрелки называются дугами), можно рассматривать как граф.

3.       Если в множестве Г все пары упорядочены, то такой граф называют ориентированным .

4.       Дуга- ребро ориентированного графа.

5.       Граф называется вырожденным, если у него нет рёбер.

6.       Вершина Х называется инцидентной ребру G , если ребро соединяет эту вершину с какой-либо другой вершиной.

7.       Подграфом G(V₁, E₁) графа G(V, E) называется граф с множеством вершин V₁ ÍV и множеством ребер (дуг) E₁Í E, - такими, что каждое ребро (дуга) из E₁ инцидентно (инцидентна) только вершинам из V₁ . Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).

8.       Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого – U, содержащий те и только те рёбра, оба конца которых входят в U.

9.       Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

10.    Вершины называются смежными , если существует ребро , их соединяющее.

11.    Два ребра G₁ и G₂ называются смежными, если существует вершина, инцидентная одновременно G₁ и G₂.

12.    Каждый граф можно представить в пространстве множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам (или дугам - в последнем случае направление обычно указывается стрелочками). - такое представление называется укладкой графа.

13.    Доказано, что в 3-мерном пространстве любой граф можно представить в виде укладки таким образом, что линии, соответствующие ребрам (дугам) не будут пересекаться во внутренних точках. Для 2-мерного пространства это, вообще говоря, неверно. Допускающие представление в виде укладки в 2-мерном пространстве графы называют плоскими (планарным).
 Другими словами, планарным называется граф, который может быть изображен на плоскости так, что его рёбра не будут пересекаться.