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

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

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

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

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

ТЕОРИЯ ГРАФОВ - это область дискретной математики, особенностью

которой является геометрический подход к изучению объектов. Теория графов

находится сейчас в самом расцвете. Обычно её относят к топологии (потому

что во многих случаях рассматриваются лишь топологические свойства графов),

однако она пересекается со многими разделами теории множеств, комбинаторной

математики, алгебры, геометрии, теории матриц, теории игр, математической

логики и многих других математических дисциплин. Основной объект теории

графов-граф и его обобщения.

Первые задачи теории графов были связаны с решением математических

развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача

о расстановке ферзей на шахматной доске, задачи о перевозках, задача о

кругосветном путешествии и другие). Одним из первых результатов в теории

графов явился критерий существования обхода всех ребер графа без

повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских

мостах. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ” Мне

была предложена задача об острове, расположенном в городе Кенигсберге и

окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли

кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост.

И тут же мне было сообщено, что никто еще до сих пор не смог это проделать,

но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный,

показался мне, однако, достойным внимания тем, что для его решения

недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После

долгих размышлений я нашел лёгкое правило, основанное на вполне

убедительном доказательстве, с помощью которого можно во всех задачах

такого рода тотчас же определить, может ли быть совершен такой обход через

какое угодно число и как угодно расположенных мостов или не может“.

Кенигсбергские мосты схематически можно изобразить так:

[pic]

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

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

всех рёбер (причем каждое ребро проходится в точности один раз)

с началом в любой вершине графа.

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

существует обход с началом в одной вершине с нечетной степенью и

концом в другой.

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

обхода не существует.

Существует еще один вид задач, связанных с путешествиями вдоль

графов. Речь идёт о задачах, в которых требуется отыскать путь, проходящий

через все вершины, причем не более одного раза через каждую. Цикл,

проходящий через каждую вершину один и только один раз, носит название

гамильтоновой линии( в честь Уильяма Роуэна Гамильтона, знаменитого

ирландского математика прошлого века, который первым начал изучать такие

линии). К сожалению, пока еще не найден общий критерий, с помощью которого

можно было бы решить, является ли данный граф гамильтоновым, и если да, то

найти на нём все гамильтоновы линии.

Сформулированная в середине 19 в. проблема четырех красок также

выглядит как развлекательная задача, однако попытки ее решения привели к

появлению некоторых исследований графов, имеющих теоретическое и

прикладное значение. Проблема четырех красок формулируется так: ”Можно ли

область любой плоской карты раскрасить четырьмя цветами так, чтобы любые

две соседние области были раскрашены в различные цвета?”. Гипотеза о том,

что ответ утвердительный, была сформулирована в середине 19в. В 1890 году

было доказано более слабое утверждение, а именно, что любая плоская карта

раскрашивается в пять цветов. Сопоставляя любой плоской карте двойственный

ей плоский граф, получают эквивалентную формулировку задачи в терминах

графов: Верно ли, что хроматическое число любого плоского графа меньше либо

равно четырёх? Многочисленные попытки решения задачи оказали влияние на

развитие ряда направлений теории графов. В 1976 году анонсировано

положительное решение задачи с использованием ЭВМ.

Другая старая топологическая задача, которая особенно долго не

поддавалась решению и будоражила умы любителей головоломок, известна как

“задача об электро -, газо - и водоснабжении”. В 1917 году Генри Э.Дьюдени

дал ей такую формулировку. В каждый из трёх домов, изображенных на рисунке,

необходимо провести газ, свет и воду.

Свет вода газ

Можно ли так проложить коммуникации, чтобы они, нигде не пересекаясь

друг с другом, соединяли каждый дом с источниками электричества, газа и

воды? Иначе говоря, можно построить плоский граф с вершинами в шести

указанных точках? Оказывается, такой граф построить нельзя. Об этом

говорится в одной очень важной теореме – так называемой теореме

Куратовского. Теорема утверждает, что каждый граф, не являющийся плоским,

содержит в качестве подграфа один из двух простейших пространственных

графов:

[pic]

В середине 19 в. появились работы, в которых при решении

практических задач были получены результаты, относящиеся к теории графов.

Так, например, Г. Кирхгоф при составлении полной системы уравнений для

токов и напряжений в электрической схеме предложил по существу представлять

такую схему графом и находить в этом графе остовные деревья, с помощью

которых выделяются линейно независимые системы контуров. А. Кэли, исходя

из задач подсчета числа изомеров предельных углеводородов, пришел к задачам

перечисления и описания деревьев, обладающих заданными свойствами, и решил

некоторые из них.

В 20 в. задачи, связанные с графами, начали возникать не только в

физике, химии, электротехнике биологии, экономике, социологии и т.д., но и

внутри математики, в таких разделах, как топология, алгебра, теория

вероятностей, теория чисел. В начале 20 в. графы стали использоваться для

представления некоторых математических объектов и формальной постановки

различных дискретных задач; при этом наряду с термином «граф» употреблялись

и другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт.

После выхода в свет в 1936 году монографии Д. Кёнига термин «граф» стал

более употребительным, чем другие. В этой работе были систематизированы

известные к тому времени факты. В 1936 году вышла небольшая брошюра Ойстена

Оре, содержащая блестящее элементарное введение в теорию графов. В 1962

году в Англии была издана книга французского математика Клода Бержа “Теория

графов и её приложение”. Обе книги, безусловно, представляют интерес для

любителей занимательной математики. Сотни известных головоломок, на первый

взгляд не имеющих ничего общего друг с другом, легко решаются с помощью

теории графов.

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

изучению свойств связности, планарности, симметрии графов, которые привели

к формированию ряда новых направлений в теории графов.

Значительно расширились исследования по теории графов в конце 40-х

- начале 50-х годов, прежде всего в силу развития кибернетики и

вычислительной техники. Благодаря развитию вычислительной техники, изучению

сложных кибернетических систем, интерес к теории графов возрос, а

проблематика теории графов существенным образом обогатилась. Кроме того,

использование ЭВМ позволило решать возникающие на практике конкретные

задачи, связанные с большим объемом вычислений, прежде не поддававшиеся

решению. Для ряда экстремальных задач теории графов были разработаны методы

их решения, например, один из таких методов позволяет решать задачи о

построении максимального потока через сеть. Для отдельных классов графов

(деревья, плоские графы и т. д.), которые изучались и ранее, было показано,

что решения некоторых задач для графов из этих классов находятся проще, чем

для произвольных графов (нахождение условий существования графов с

заданными свойствами, установление изоморфизма графов и др.).

Характеризуя проблематику теории графов, можно отметить, что

некоторые направления носят более комбинаторный характер, другие - более

геометрический. К первым относятся, например, задачи о подсчете и

перечислении графов с фиксированными свойствами, задачи о построении графов

с заданными свойствами. Геометрический (топологический) характер носят

многие циклы задач теории графов, например, графов обходы, графов укладки.

Существуют направления, связанные с различными классификациями графов,

например, по свойствам их разложения.

Примером результата о существовании графов с фиксированными

свойствами может служить критерий реализуемости чисел степенями вершин

некоторого графа: набор целых чисел, [pic] сумма которых четна, можно

реализовать степенями вершин графа без петель и кратных ребер тогда и

только тогда, когда для любого r выполняется условие [pic]

Примерами задач о подсчете графов с заданными свойствами являются

задачи о нахождении количеств неизоморфных графов с одинаковым числом

вершин и (или) ребер. Для числа неизоморфных деревьев с n вершинами была

получена асимптотическая формула [pic] где C== 0,534948..., e== 2,95576...

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

вершинами было показано, что [pic]

Наряду с проблемами, носящими общий характер, в теории графов

имеются специфические циклы задач. В одном из них изучаются различные

свойства связности графов, исследуется строение графов по свойствам

связности. При анализе надежности сетей связи, электронных схем,

коммуникационных сетей возникает задача о нахождении количеств

непересекающихся цепей, соединяющих различные вершины графа. Здесь получен

ряд результатов. Например, наименьшее число вершин, разделяющих две

несмежные вершины графа, равно наибольшему числу непересекающихся (по

вершинам) простых цепей, соединяющих эту пару вершин. Найдены критерии и

построены эффективные алгоритмы установления меры связности графа

(наименьшего числа вершин или ребер, удаление которых нарушает связность

графа).

В другом направлении исследований теории графов изучаются маршруты,

содержащие все вершины или ребра графа. Известен простой критерий

существования маршрута, содержащего все ребра графа: в связном графе цикл,

содержащий все ребра и проходящий по каждому ребру один раз, существует

тогда и только тогда, когда все вершины графа имеют четные степени. В

случае обхода множества вершин графа имеется только ряд достаточных условий

существования цикла, проходящего по всем вершинам графа по одному разу.

Характерным специфическим направлением теории графов является цикл задач,

связанный с раскрасками графов, в котором изучаются разбиения множества

вершин (ребер), обладающие определенными свойствами, например, смежные

вершины (ребра) должны принадлежать различным множествам (вершины или ребра

из одного множества окрашиваются одним цветом). Было доказано, что

наименьшее число цветов, достаточное для раскраски ребер любого графа без

петель с максимальной степенью a, равно Зa/2, а для раскраски вершин любого

графа без петель и кратных ребер достаточно a+1 цветов.

Существуют и другие циклы задач, некоторые из них сложились под

влиянием различных разделов математики. Так, под влиянием топологии

производится изучение вложений графов в различные поверхности. Например,

было получено необходимое и достаточное условие вложения графа в плоскость

(критерий Понтрягина - Куратовского см. выше): граф является плоским тогда

и только тогда, когда он не содержит подграфов, получаемых с помощью

подразбиения ребер из полного 5-вершинного графа и полного двудольного

графа с тремя вершинами в каждой доле. Под влиянием алгебры стали изучаться

группы автоморфизмов графов. В частности, было доказано, что каждая

конечная группа изоморфна группе автоморфизмов некоторого графа. Влияние

теории вероятностей сказалось на исследовании графов случайных. Многие

свойства были изучены для «почти всех» графов; например, было показано, что

почти все графы с n вершинами связаны, имеют диаметр 2, обладают

гамильтоновым циклом (циклом, проходящим через все вершины графа по одному

разу).

В теории графов существуют специфические методы решения

экстремальных задач. Один из них основан на теореме о максимальном потоке и

минимальном разрезе, утверждающей, что максимальный поток, который можно

пропустить через сеть из вершины U в вершину V, равен минимальной

пропускной способности разрезов, разделяющих вершины U и V. Были построены

различные эффективные алгоритмы нахождения максимального потока.

Большое значение в теории графов имеют алгоритмические вопросы. Для

конечных графов, т. е. для графов с конечным множеством вершин и ребер, как

правило, проблема существования алгоритма решения задач, в том числе

экстремальных, решается положительно. Решение многих задач, связанных с

конечными графами, может быть выполнено с помощью полного перебора всех

допустимых вариантов. Однако таким способом удается решить задачу только

для графов с небольшим числом вершин и ребер. Поэтому существенное значение

для теории графов имеет построение эффективных алгоритмов, находящих точное

или приближенное решение. Для некоторых задач такие алгоритмы построены,

например, для установления планарности графов, определения изоморфизма

деревьев, нахождения максимального потока.

Результаты и методы теории графов применяются при решении

транспортных задач о перевозках, для нахождения оптимальных решений задачи

о назначениях, для выделения «узких мест» при планировании и управлении

разработок проектов, при составлении оптимальных маршрутов доставки грузов,

а также при моделировании сложных технология, процессов, в построении

различных дискретных устройств, в программировании и т. д.

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

Граф - Пара объектов G = ( X , Г ) ,где Х - конечное множество ,а Г

–конечное подмножество прямого произведения Х*Х . При этом Х

называется множеством вершин , а Г - множеством дуг графа G .

Любое конечное множество точек (вершин), некоторые из которых попарно

соединены стрелками , (в теории графов эти стрелки называются дугами),

можно рассматривать как граф.

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

ориентированным .

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

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

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

вершину с какой-либо другой вершиной.

Подграфом G(V1, E1) графа G(V, E) называется граф с множеством вершин V1 ?V

и множеством ребер (дуг) E1? E, - такими, что каждое ребро (дуга) из E1

инцидентно (инцидентна) только вершинам из V1 . Иначе говоря, подграф

содержит некоторые вершины исходного графа и некоторые рёбра (только те,

оба конца которых входят в подграф).

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

вершин которого – U, содержащий те и только те рёбра, оба конца которых

входят в U.

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

с множеством вершин самого графа.

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

Два ребра G1 и G2 называются смежными, если существует вершина, инцидентная

одновременно G1 и G2.

Каждый граф можно представить в пространстве множеством точек,

соответствующих вершинам, которые соединены линиями, соответствующими

ребрам (или дугам - в последнем случае направление обычно указывается

стрелочками). - такое представление называется укладкой графа.

Доказано, что в 3-мерном пространстве любой граф можно представить в виде

укладки таким образом, что линии, соответствующие ребрам (дугам) не будут

пересекаться во внутренних точках. Для 2-мерного пространства это, вообще

говоря, неверно. Допускающие представление в виде укладки в 2-мерном

пространстве графы называют плоскими (планарным).

Другими словами, планарным называется граф, который может быть изображен

на плоскости так, что его рёбра не будут пересекаться.

Гранью графа, изображенного на некоторой поверхности, называется часть

поверхности, ограниченная рёбрами графа.

Данное понятие грани, по - существу, совпадает с понятием грани

многогранника. В качестве поверхности в этом случае выступает поверхность

многогранника. Если многогранник выпуклый, его можно изобразить на

плоскости, сохранив все грани. Это можно наглядно представить следующим

образом: одну из граней многогранника растягиваем, а сам многогранник

«расплющиваем» так, чтобы он весь поместился внутри этой грани. В

результате получим плоский граф. Грань, которую мы растягивали «исчезнет»,

но ей будет соответствовать грань, состоящая из части плоскости,

ограничивающей граф.

Таким образом, можно говорить о вершинах, рёбрах и гранях

многогранника, а оперировать соответствующими понятиями для плоского графа.

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

две вершины смежные.

Конечная последовательность необязательно различных рёбер E1,E2,...En

называется маршрутом длины n, если существует последовательность V1, V2,

... Vn необязательно различных вершин, таких, что Ei = (Vi-1,Vi ).

Если совпадают, то маршрут замкнутый.

Маршрут, в котором все рёбра попарно различны, называется цепью.

Замкнутый маршрут, все рёбра которого различны, называется циклом. Если все

вершины цепи или цикла различны, то такая цепь или цикл называются

простыми.

Маршрут, в котором все вершины попарно различны, называется простой цепью.

Цикл, в котором все вершины, кроме первой и последней, попарно различны,

называется простым циклом.

Граф называется связным, если для любых двух вершин существует путь,

соединяющий эти вершины.

Любой максимальный связный подграф (то есть, не содержащийся в других

связных подграфах) графа G называется компонентой связности. Несвязный граф

имеет, по крайней мере, две компоненты связности.

Граф называется k - связным (k - реберно - связным), если удаление не менее

k вершин (ребер) приводит к потере свойства связности.

Маршрут, содержащий все вершины или ребра графа и обладающий определенными

свойствами, называется обходом графа.

Длина маршрута (цепи, простой цепи) равна количеству ребер а порядке их

прохождения. Длина кратчайшей простой цепи, соединяющей вершины vi и vj в

графе G, называется расстоянием d (vi, vj) между vi и vj.

Степень вершины - число ребер, которым инцидентна вершина V, обозначается

D(V).

С помощью различных операций можно строить графы из более простых,

переходить от графа к более простому, разбивать графы на более простые и

т.д.

Среди одноместных операций наиболее употребительны: удаление и

добавление ребра или вершины, стягивание ребра (отождествление пары смежных

вершин), подразбиение ребра (т.е. замена ребра (u, v) на пару (u, w), (w,

v), где w - новая вершина) и др.

Известны двуместные операции: соединение, сложение, различные виды

умножений графов и др. Такие операции используются для анализа и синтеза

графов с заданными свойствами.

Два графа G1=(V1;E1), G2=(V2;E2),называются изоморфными, если существует

взаимнооднозначное соответствие между множествами вершин V1 и V2 и между

множествами рёбер Е1 и Е2, такое, чтобы сохранялось отношение

инцидентности.

Понятие изоморфизма для графов имеет наглядное толкование.

Представим рёбра графов эластичными нитями, связывающими узлы – вершины.

Тогда, изоморфизм можно представить как перемещение узлов и растяжение

нитей.

Теорема 1.

Пусть задан граф G=(V;E),где V - множество вершин, E - множество

рёбер, тогда 2[E]=?(V), т.е. удвоенное количество рёбер равно сумме

степеней вершин.

Теорема 2. (Лемма о рукопожатиях)

В конечном графе число вершин нечетной степени чётно.

Теорема 3.

Граф связен тогда и только тогда, когда множество его вершин нельзя

разбить на два непустых подмножества так, чтобы обе граничные точки каждого

ребра находились в одном и том же множестве.

Расстоянием между двумя вершинами связного графа называется

длина кратчайшей цепи, связывающей эти вершины (в количестве рёбер).

Свойства связных графов.

1. Связный граф остается связным после удаления ребра тогда

и только тогда, когда это ребро содержится в цикле.

2. Связный граф , имеющий К вершин , содержит по крайней мере К-1

ребро.

3. В связном графе любые две простые цепи максимальной длины имеет

по крайней мере одну общую вершину.

4. В графе с N вершинами и К компонентами связности число рёбер не

превышает 1/2(N-K)(N-K+1).

5. Пусть у графа G есть N вершин . Пусть D(G)- минимальная из

степеней вершин этого графа . Тогда D(G) > 1/2 (N-1).

Связный граф без циклов называется деревом.

Деревья особенно часто возникают на практике при изображении

различных иерархий. Например, популярные генеалогические деревья.

Пример(генеалогическое дерево): На рисунке показано библейское

генеалогическое дерево.

Эквивалентные определения дерева.

1. Связный граф называется деревом, если он не имеет циклов.

2. Содержит N-1 ребро и не имеет циклов.

3. Связный и содержит N-1 ребро.

4. Связный и удаление одного любого ребра делает его несвязным.

5. Любая пара вершин соединяется единственной цепью.

6. Не имеет циклов и добавление одного ребра между любыми двумя

вершинами приводит к появлению одного и только одного цикла.

1

Раскраска графов

Раскраской графа G = (V,E) называется отображение D: V( N . Раскраска

называется правильной, если образы любых двух смежных вершин различны: D

(U) ? D (V), если (U,V) ( I. Хроматическим числом графа называется

минимальное количество красок, необходимое для правильной раскраски графа.

Теорема 5.

Граф является планарным тогда и только тогда, когда он не содержит

подграфа, изоморфного одному из следующих (графы Понтрягина -

Куратовского).

Граф К33

Граф К5

Свойство: В любом планарном графе существует вершина, степень

которой.

Так как мы рассматриваем только простые графы, граф нам проще

определять как модель, носителем которой является множество вершин, а

отношение – бинарное отношение смежности вершин. Тогда данный граф

запишется как . В таком представлении ребру

соответствуют две пары вершин (v1,v2) и (v2,v1), инцидентных данному ребру.

Чтобы задать такое представление, достаточно для каждого ребра указать

двухэлементное множество вершин – его мы и будем отождествлять с ребром.

Для данного графа рёбра задаются множеством {{a,b},{b,c},{a,c},{c,d}} и

граф мы будем записывать как пару (V,E), где V – множество вершин, а E –

множество рёбер.

5. Наконец, граф можно задать посредством списков.

Например:

вариант 1: списком пар вершин, соединенных ребрами (или дугами);

вариант 2: списком списков для каждой вершины множества смежных с ней

вершин.

2. Задачи на графах.

1

2 2.1. Описание различных задач на графах.

Развитие теории графов в основном обязано большому числу всевозможных

приложений. По-видимому, из всех математических объектов графы занимают

одно из первых мест в качестве формальных моделей реальных систем.

Графы нашли применение практически во всех отраслях научных знаний:

физике, биологии, химии, математике, истории, лингвистике, социальных

науках, технике и т.п. Наибольшей популярностью теоретико-графовые модели

используются при исследовании коммуникационных сетей, систем информатики,

химических и генетических структур, электрических цепей и других систем

сетевой структуры.

Далее перечислим некоторые типовые задачи теории графов и их

приложения:

- Задача о кратчайшей цепи

замена оборудования

составление расписания движения транспортных средств

размещение пунктов скорой помощи

размещение телефонных станций

- Задача о максимальном потоке

анализ пропускной способности коммуникационной сети

организация движения в динамической сети

оптимальный подбор интенсивностей выполнения работ

синтез двухполюсной сети с заданной структурной надежностью

задача о распределении работ

- Задача об упаковках и покрытиях

оптимизация структуры ПЗУ

размещение диспетчерских пунктов городской транспортной сети

- Раскраска в графах

распределение памяти в ЭВМ

проектирование сетей телевизионного вещания

- Связность графов и сетей

проектирование кратчайшей коммуникационной сети

синтез структурно-надежной сети циркуляционной связи

анализ надежности стохастических сетей связи

- Изоморфизм графов и сетей

структурный синтез линейных избирательных цепей

автоматизация контроля при проектировании БИС

- Изоморфное вхождение и пересечение графов

локализация неисправности с помощью алгоритмов поиска МИПГ

покрытие схемы заданным набором типовых подсхем

- Автоморфизм графов

конструктивное перечисление структурных изомеров для

производных органических соединений

синтез тестов цифровых устройств

3 2.2. Нахождение кратчайших путей в графе

Начальные понятия

Будем рассматривать ориентированные графы G = , дугам которых

приписаны веса. Это означает, что каждой дуге ?E поставлено в

соответствие некоторое вещественное число a (u, v), называемое весом данной

дуги.

Нас будет интересовать нахождение кратчайшего пути между

фиксированными вершинами s, t ?V. Длину такого кратчайшего пути мы будем

обозначать d (s, t) и называть расстоянием от s до t (расстояние,

определенное таким образом, может быть отрицательным). Если не существует

ни одного пути из s в t, то полагаем d (s, t) = + . Если каждый контур

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

элементарным путем, т.е. в последовательности v1,..., vp не будет повторов.

С другой стороны, если в графе существует контур отрицательной длины,

то расстояние между некоторыми парами вершин становится неопределенным,

потому что, обходя этот контур достаточное число раз, мы можем показать

путь между этими вершинами с длиной, меньшей произвольного вещественного

числа. В таком случае, можно было бы говорить о длине кратчайшего

элементарного пути, однако задача, поставленная таким образом, вероятно

будет значительно более сложной, так как, в частности, она содержит в себе

задачу существования гамильтонова пути.

Можно дать много практических интерпретаций задачи о кратчайших

путях. Например, вершины могут соответствовать городам, а каждая дуга -

некоторому пути, длина которого представлена весом дуги. Мы ищем затем

кратчайшие пути между городами. Вес дуги также может соответствовать

стоимости (или времени) передачи информации между вершинами. В таком случае

мы ищем самый дешевый (или самый скорый) путь передачи информации. Еще одну

ситуацию получаем, когда вес дуги равен вероятности p(u, v)

безаварийной работы канала передачи информации. Если предположить, что

аварии каналов не зависят друг от друга, то вероятность исправности пути

передачи информации равна произведению вероятностей составляющих его дуг.

Задачу нахождения наиболее надежного пути легко можно свести к задаче о

кратчайшем пути, заменяя веса p(u, v) на a (u, v) = - lg p(u, v).

Сначала рассмотрим алгоритмы нахождения расстояния между вершинами, а

не самих путей. Однако, зная расстояние, мы можем при условии положительной

длины всех контуров легко определить кратчайшие пути. Для этого достаточно

отметить, что для произвольных s, t ? V (s , t) существует вершина v, такая

что d (s, t) = d (s, v) + a (v, t).

Действительно, таким свойством обладает предпоследняя вершина

произвольного кратчайшего пути из s в t.

Далее мы можем найти вершину u, для которой d (s, v) = d (s, u) + a

(u, v), и т.д.

Из положительности длины всех контуров легко следует, что созданная

таким образом последовательность t, v, u, ... не сожержит повторений и

оканчивается вершиной s.

Очевидно, что она определяет (при обращении очередности) кратчайший

путь из s в t.

Таким образом, мы получаем следующий алгоритм:

Алгоритм нахождения кратчайшего пути

Данные: Расстояния D[v] от фиксированной вершины s до всех остальных

вершин v ? V, фиксированная вершина t, матрица весов ребер, A[u, v], u, v

?V.

Результаты: СТЕК содержит последовательность вершин, определяющую

кратчайший путь из s в t.

begin

CTEK := ? ; CTEK ? t; v:= t;

while v ? s do

begin

u := вершина, для которой D[v] = D[u] + A[u, v];

CTEK ? u;

v:= u

end

end.

Пусть -ориентированный граф, | V| = n, | E| = m. Если выбор

вершины u происходит в результате просмотра всех вершин, то сложность

нашего алгоритма - O(n2). Если мы просматриваем только список ПРЕДШ[v],

содержащий все вершины u, такие что u (?) v, то в этом случае сложность

будет O(m).

Отметим, что в случае положительных весов ребер задача о кратчайшем

пути в неориентированном графе легко сводится к аналогичной задаче для

некоторого ориентированного графа. С этой целью достаточно заменить каждое

ребро {u, v}двумя дугами ? u, v?и ?v, u? , каждая с таким же весом, что и

{u, v}. Однако в случае неположительных весов это приводит к возникновению

контуров с неположительной длиной.

Далее будем всегда предполагать, что G = < V, E>является

ориентированным графом, |V| = n, |E| = m. В целях упрощения изложения и

избежания вырожденных случаев при оценке сложности алгоритмов будем

исключать ситуации, при которых «большинство» вершин изолированные.

Будем также предполагать, что веса дуг запоминаются в массиве A[u,

v], u, v ? V (A[u, v] содержит вес a (u, v)).

Кратчайшие пути от фиксированной вершины

Большинство известных алгоритмов нахождения расстояния между двумя

фиксированными вершинами s и t опирается на действия, которые в общих

чертах можно представить следующим образом: при данной матрице весов дуг

A[u, v], u, v ? V, вычисляются некоторые верхние ограничения D[v] на

расстояния от s до всех вершин v ?V. Каждый раз, когда мы устанавливаем,

что

D[u] + A[u, v] < D[v], оценку D[v] улучшаем: D[v] = D[u] + A[u, v].

Процесс прерывается, когда дальнейшее улучшение ни одного из

ограничений невозможно.

Легко можно показать, что значение каждой из переменных D[v] равно

тогда d (s, v) - расстоянию от s до v.

Заметим, что для того чтобы определить расстояние от s до t, мы

вычисляем здесь расстояния от s до всех вершин графа.

Не известен ни один алгоритм нахождения расстояния между двумя

фиксированными вершинами, который был бы существенным образом более

эффективным, нежели известные алгоритмы определения расстояния от

фиксированной вершины до всех остальных.

Описанная общая схема является неполной, так как она не определяет

очередности, в которой выбираются вершины u и v для проверки условия

минимальности расстояния. Эта очередности, как будет показано ниже, очень

сильно влияет на эффективность алгоритма. Опишем теперь более детально

методы нахождения расстояния от фиксированной вершины, называемой

источником, его всегда будем обозначать через s, до всех остальных вершин

графа.

Сначала представим алгоритм для общего случая, в котором

предполагается только отсутствие контуров с отрицательной длиной. С эти

алгоритмом обычно связывают имена Л.Р. Форда и Р.Е. Беллмана.

3. Программа определения кратчайшего пути в графе

1 3.1. Язык программирования Delphi.

Delphi - язык и среда программирования, относящаяся к классу RAD-

(Rapid Application Development - «Средство быстрой разработки приложений»)

средств CASE - технологии. Delphi сделала разработку мощных приложений

Windows быстрым процессом, доставляющим вам удовольствие. Приложения

Windows, для создания которых требовалось большое количество человеческих

усилий например в С++, теперь могут быть написаны одним человеком,

использующим Delphi.

Интерфейс Windows обеспечивает полное перенесение CASE-технологий в

интегрированную систему поддержки работ по созданию прикладной системы на

всех фазах жизненного цикла работы и проектирования системы.

Delphi обладает широким набором возможностей, начиная от

проектировщика форм и кончая поддержкой всех форматов популярных баз

данных. Среда устраняет необходимость программировать такие компоненты

Windows общего назначения, как метки, пиктограммы и даже диалоговые панели.

Работая в Windows , вы неоднократно видели одинаковые «объекты» во многих

разнообразных приложениях. Диалоговые панели (например Choose File и Save

File) являются примерами многократно используемых компонентов, встроенных

непосредственно в Delphi, который позволяет приспособить эти компоненты к

имеющийся задаче, чтобы они работали именно так, как требуется создаваемому

приложению. Также здесь имеются предварительно определенные визуальные и не

визуальные объекты, включая кнопки, объекты с данными, меню и уже

построенные диалоговые панели. С помощью этих объектов можно, например,

обеспечить ввод данных просто несколькими нажатиями кнопок мыши, не

прибегая к программированию. Это наглядная реализация применений CASE-

технологий в современном программировании приложений. Та часть, которая

непосредственно связана с программированием интерфейса пользователя

системой получила название визуальное программирование

Визуальное программирование как бы добавляет новое измерение при

создании создании приложений, давая возможность изображать эти объекты на

экране монитора до выполнения самой программы. Без визуального

программирования процесс отображения требует написания фрагмента кода,

создающего и настающего объект «по месту». Увидеть закодированные объекты

было возможно только в ходе исполнения программы. При таком подходе

достижение того, чтобы объекты выглядели и вели себя заданным образом,

становится утомительным процессом, который требует неоднократных

исправлений программного кода с последующей прогонкой программы и

наблюдения за тем, что в итоге получилось.

Благодаря средствам визуальной разработки можно работать с объектами,

держа их перед глазами и получая результаты практически сразу. Способность

видеть объекты такими, какими они появляются в ходе исполнения программы,

снимает необходимость проведения множества операций вручную, что характерно

для работы в среде не обладающей визуальными средствами — вне зависимости

от того, является она объектно-ориентированной или нет. После того, как

объект помещен в форму среды визуального программирования, все его атрибуты

сразу отображаются в виде кода, который соответствует объекту как единице,

исполняемой в ходе работы программы.

Размещение объектов в Delphi связано с более тесными отношениями

между объектами и реальным программным кодом. Объекты помещаются в вашу

форму, при этом код, отвечающий объектам, автоматически записывается в

исходный файл. Этот код компилируется, обеспечивая существенно более

высокую производительность, чем визуальная среда, которая интерпретирует

информацию лишь в ходе исполнения программы.

1 3.2. Программа «Определение кратчайшего пути в графе»

Программа «Определение кратчайшего пути в графе» разработана в среде

«Delphi», работает под ОС «Windows»-95,98,2000,NT.

Программа позволяет вводить, редактировать, сохранять графы в файл,

загружать из файла. Также реализован алгоритм нахождения кратчайшего пути.

Интерфейс программы имеет следующий вид:

[pic]

Верхняя панель кнопок предназначена для редактирования графа.

Кнопка «Загрузить» [pic] предназначена для загрузки ранее

сохраненного графа из файла.

Кнопка «Сохранить» [pic] предназначена для сохранения графа в файл.

Кнопка «Переместить» [pic] предназначена для перемещения вершин

графа.

Кнопка «Удалить» [pic] предназначена для удаления вершин графа.

При нажатии на кнопку «Новый» [pic] рабочее поле программы будет

очищено и появится возможность ввода нового графа.

Кнопка «Помощь» [pic] вызывает помощь программы.

Для очистки результатов работы алгоритма определения кратчайшего пути

в графе необходимо нажать кнопку «Обновить» [pic].

При нажатии на кнопку «Настройки» [pic] на экране появится окно, в

котором можно настроить параметры сетки рабочего поля программы и цвета

вводимого графа.

Окно настроек выглядит следующим образом:

[pic]

Нижняя панель кнопок предназначена для установки параметров ввода и

запуска алгоритма определения кратчайшего пути в графе. Данная панель

состоит из четырех кнопок:

При включенной кнопке «Показывать сетку» [pic] отображается сетка для

удобства ввода вершин.

Для автоматического ввода длины ребра графа необходимо нажать кнопку

[pic].

При включенной кнопке «Выравнивать по сетке» [pic] новые вершины

будут автоматически выравниваться по координатной сетке.

Если выбрать две различные вершины (щелчком левой кнопки мыши) и

нажать на кнопку [pic], то программа найдет кратчайший путь между

вершинами.

Алгоритм определения кратчайшего пути между вершинами графа описан

следующим модулем программы:

unit MinLength;

interface

uses

Windows, Messages, SysUtils,>

StdCtrls,IO,Data,AbstractAlgorithmUnit;

type

TMinLength =>

private

StartPoint:integer;

EndPoint:integer;

First:Boolean;

Lymbda:array of integer;

function Proverka:Boolean;

public

procedure Make;

end;

var

MyMinLength: TMinLength;

implementation

uses MainUnit, Setting;

procedure TMinLength.Make;

var i ,j : integer;

PathPlace,TempPoint:Integer;

flag:boolean;

begin

with MyData do begin

StartPoint:=MyIO.FirstPoint;

EndPoint:=MyIO.LastPoint;

SetLength(Lymbda,Dimension+1);

SetLength(Path,Dimension+1);

for i:=1 to Dimension do

Lymbda[i]:=100000;

Lymbda[StartPoint]:=0;

repeat

for i:=1 to Dimension do

for j:=1 to Dimension do

if Matrix[i,j]=1 then

if ( ( Lymbda[j]-Lymbda[i] ) >

MatrixLength[j,i] )

then Lymbda[j]:=Lymbda[i] + MatrixLength[j,i];

until Proverka ;

Path[1]:= EndPoint ;

j:=1;

PathPlace:=2;

repeat

TempPoint:=1;

Flag:=False;

repeat

if ( Matrix[ Path[ PathPlace-1 ],TempPoint] =1 )and (

Lymbda[ Path[ PathPlace-1] ] =

( Lymbda[TempPoint] + MatrixLength[ Path[PathPlace-

1 ], TempPoint] ) )

then Flag:=True

else Inc( TempPoint );

until Flag;

Path[ PathPlace ]:=TempPoint;

inc( PathPlace );

MyIO.DrawPath(Path[ PathPlace-2 ],Path[ PathPlace

-1],true);

// ShowMessage('f');

until(Path[ PathPlace - 1 ] = StartPoint);

// MyIO.DrawPath(Path[ PathPlace-1 ],Path[ PathPlace

],true);

end;

end;

function TMinLength.Proverka:Boolean;

var i,j:integer;

Flag:boolean;

begin

i:=1;

Flag:=False;

With MyData do begin

repeat

j:=1;

repeat

if Matrix[i,j]=1 then

if ( Lymbda[j]-Lymbda[i] )>MatrixLength[j,i]then

Flag:=True;

inc(j);

until(j>Dimension)or(Flag);

inc(i);

until(i>Dimension)or(Flag);

Result:=not Flag;

end;

end;

end.

Рабочее поле программы предназначено для визуального ввода графов.

Рабочее поле с введенным графом выглядит следующим образом:

[pic]

ЗАКЛЮЧЕНИЕ

Теория графов находит широкое применение в различных областях науки и

техники:

Графы и информация

Двоичные деревья играют весьма важную роль в теории информации.

Предположим, что определенное число сообщений требуется закодировать в виде

конечных последовательностей различной длины, состоящих из нулей и единиц.

Если вероятности кодовых слов заданы, то наилучшим считается код, в котором

средняя длина слов минимальна по сравнению с прочими распределениями

вероятности. Задачу о построении такого оптимального кода позволяет решить

алгоритм Хаффмана.

Двоичные кодовые деревья допускают интерпретацию в рамках теории

поиска. Каждой вершине при этом сопоставляется вопрос, ответить на который

можно либо "да", либо "нет". Утвердительному и отрицательному ответу

соответствуют два ребра, выходящие из вершины. "Опрос" завершается, когда

удается установить то, что требовалось.

Таким образом, если кому-то понадобится взять интервью у различных

людей, и ответ на очередной вопрос будет зависеть от заранее неизвестного

ответа на предыдущий вопрос, то план такого интервью можно представить в

виде двоичного дерева.

Графы и химия

Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных (или

предельных) углеводородов, молекулы которых задаются формулой:

CnH2n+2

Молекула каждого предельного углеводорода представляет собой дерево.

Если удалить все атомы водорода, то оставшиеся атомы углеводорода также

будут образовывать дерево, каждая вершина которого имеет степень не выше 4.

Следовательно, число возможных структур предельных углеводородов, т. е.

число гомологов данного вещества, равно числу деревьев с вершинами степени

не больше четырех.

Таким образом, подсчет числа гомологов предельных углеводородов также

приводит к задаче о перечислении деревьев определенного типа. Эту задачу и

ее обобщения рассмотрел Д. Пойа.

Графы и биология

Деревья играют большую роль в биологической теории ветвящихся

процессов. Для простоты мы рассмотрим только одну разновидность ветвящихся

процессов – размножение бактерий. Предположим, что через определенный

промежуток времени каждая бактерия либо делится на две новые, либо

погибает. Тогда для потомства одной бактерии мы получим двоичное дерево.

Нас будет интересовать лишь один вопрос: в скольких случаях n-е

поколение одной бактерии насчитывает ровно k потомков? Рекуррентное

соотношение, обозначающее число необходимых случаев, известно в биологии

под названием процесса Гальтона-Ватсона. Его можно рассматривать как

частный случай многих общих формул.

Графы и физика

Еще недавно одной из наиболее сложных и утомительных задач для

радиолюбителей было конструирование печатных схем.

Печатной схемой называют пластинку из какого-либо диэлектрика

(изолирующего материала), на которой в виде металлических полосок

вытравлены дорожки. Пересекаться дорожки могут только в определенных

точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы

и другие), их пересечение в других местах вызовет замыкание электрической

цепи.

В ходе решения этой задачи необходимо вычертить плоский граф, с

вершинами в указанных точках.

Итак, из всего вышесказанного неопровержимо следует практическая

ценность теории графов.

СПИСОК ЛИТЕРАТУРЫ

1. Белов Теория Графов, Москва, «Наука»,1968.

2. Новые педагогические и информационные технологии Е.С.Полат, Москва,

«Akademia» 1999 г.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для

инженера. – М.: Энергоатомиздат, 1988.

4. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990.

5. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.:

Издательство МАИ, 1992.

6. Оре О. Теория графов. – М.: Наука, 1980.

7. Исмагилов Р.С., Калинкин А.В. Матеpиалы к пpактическим занятиям по

куpсу: Дискpетная математика по теме: Алгоpитмы на гpафах. - М.: МГТУ,

1995

8. Смольяков Э.Р. Введение в теоpию гpафов. М.: МГТУ, 1992

9. Hечепуpенко М.И. Алгоpитмы и пpогpаммы pешения задач на гpафах и сетях.

- Hовосибиpск: Hаука, 1990

10. Романовский И.В. Алгоpитмы pешения экстpемальных задач. - М.: Hаука,

1977

11. Писсанецки С. Технология разреженных матриц. - М.: Мир, 1988

12. Севастьянов Б.А. Вероятностные модели. - М.: Наука, 1992

13. Бочаров П.П., Печинкин А.В. Теория вероятностей. - М.: Изд-во РУДН,

1994

ПРИЛОЖЕНИЕ

1 Текст программы определения кратчайшего пути в графе

Модуль управления интерфейсом программы:

unit MainUnit;

interface

uses

Windows, Messages, SysUtils,>

StdCtrls,PaintingGraph, ComCtrls, ToolWin, ImgList, Menus,

ActnList, ExtCtrls;

const

crMyCursor = 5;

type

TForm1 =>

SaveDialog1: TSaveDialog;

OpenDialog1: TOpenDialog;

ImageList1: TImageList;

ImageList2: TImageList;

LoadMenu: TPopupMenu;

ControlBar1: TControlBar;

ToolBar3: TToolBar;

OpenButton: TToolButton;

SaveButton: TToolButton;

ToolButton15: TToolButton;

ClearButton: TToolButton;

UpdateButton: TToolButton;

HelpButton: TToolButton;

ToolButton26: TToolButton;

RemovePointButton: TToolButton;

ToolButton28: TToolButton;

ToolButton32: TToolButton;

SettingButton: TToolButton;

ControlBar2: TControlBar;

AlgoritmToolBar: TToolBar;

KommiTool: TToolButton;

ToolButton: TToolButton;

NotFarButton: TToolButton;

MinLengthButton: TToolButton;

ToolButton5: TToolButton;

MovePointButton: TToolButton;

ActionList1: TActionList;

AShowGrig: TAction;

ASnapToGrid: TAction;

ASave: TAction;

ALoad: TAction;

ADelete: TAction;

GridToolBar: TToolBar;

Clock: TLabel;

Timer1: TTimer;

ShowGridButton: TToolButton;

AutoLengthButton: TToolButton;

SnapToGridButton: TToolButton;

PaintBox1: TPaintBox;

procedure FormMouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure FormCreate(Sender: TObject);

procedure FormMouseMove(Sender: TObject; Shift: TShiftState; X,

Y: Integer);

procedure FormPaint(Sender: TObject);

procedure FormKeyDown(Sender: TObject; var Key: Word;

Shift: TShiftState);

procedure ClearButtonClick(Sender: TObject);

procedure KommiToolButtonClick(Sender: TObject);

procedure PaintingToolButtonClick(Sender: TObject);

procedure SnapToGridButtonClick(Sender: TObject);

procedure HelpButtonClick(Sender: TObject);

procedure AutoLengthButtonClick(Sender: TObject);

procedure SettingButtonClick(Sender: TObject);

procedure NotFarButtonClick(Sender: TObject);

procedure MinLengthButtonClick(Sender: TObject);

procedure MovePointButtonClick(Sender: TObject);

procedure RemovePointButtonClick(Sender: TObject);

procedure Timer1Timer(Sender: TObject);

procedure ALoadExecute(Sender: TObject);

procedure AShowGrigExecute(Sender: TObject);

procedure ASaveExecute(Sender: TObject);

procedure PaintBox1Paint(Sender: TObject);

procedure UpdateButtonClick(Sender: TObject);

procedure EilerButtonClick(Sender: TObject);

procedure ClockClick(Sender: TObject);

private

procedure MyPopupHandler(Sender: TObject);

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

uses IO,Data,Commercial,DrawingObject,Setting,NotFar,MinLength, Eiler,

SplashScreen;

{$R *.DFM}

procedure TForm1.FormMouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

begin

if Button=mbLeft then begin

MyIO.FormMouseDown( X, Y);

if (MyIO.State=msMove)then

if MyIO.FirstPointActive then

Cursor := crMyCursor

else begin

Repaint;

Cursor := crDefault;

end;

end

else

MyIO.MakeLine(X, Y);

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

Screen.Cursors[crMyCursor] := LoadCursor(HInstance, 'Shar');

MyIO:=TIO.Create(PaintBox1.Canvas);

MyData:=TData.Create;

MyDraw:=TDrawingObject.Create(PaintBox1.Canvas);

SaveDialog1.InitialDir:=ExtractFilePath(Application.ExeName)+'Grafs';

OpenDialog1.InitialDir:=ExtractFilePath(Application.ExeName)+'Grafs';

end;

procedure TForm1.FormMouseMove(Sender: TObject; Shift: TShiftState; X,

Y: Integer);

begin

MyIO.DrawLine(x,y);

end;

procedure TForm1.FormPaint(Sender: TObject);

begin

PaintBox1Paint(Sender);

end;

procedure TForm1.FormKeyDown(Sender: TObject; var Key: Word;

Shift: TShiftState);

begin

if (Key=vk_Escape) then

begin

MyData.Remove(MyData.Dimension);

MyDraw.Remove(MyData.Dimension);

Repaint;

end;

end;

procedure TForm1.MyPopupHandler(Sender: TObject);

var s:string;

begin

with Sender as TMenuItem do begin

s:=Caption;

MyData.Load(s);

System.Delete(s,length(s)-4,5);

MyDraw.Load(s+'.pos');

end;

Repaint;

end;

procedure TForm1.ClearButtonClick(Sender: TObject);

begin

MyData.Clear;

MyDraw.Clear;

Repaint;

end;

procedure TForm1.KommiToolButtonClick(Sender: TObject);

begin

If MyData.Dimension-1 then

if State=msLining then begin

MyData.Rebro(ActivePoint,i);

if AutoLength then begin

V1:=MyDraw.FindByNumber(ActivePoint);

V2:=MyDraw.FindByNumber(i);

MyData.SetRebroLength(ActivePoint,i,Round(

sqrt(sqr(Mashtab*(V1.x-V2.x)/ GrigStep)+

sqr(Mashtab*(V1.y-V2.y)/ GrigStep))));

end;

MyCanvas.MoveTo(xs,ys);

MyCanvas.LineTo(xt,yt);

DrawPath(ActivePoint,i,false);

State:=msNewPoint;

MyDraw.SetUnActive(ActivePoint);

end

else begin

ActivePoint:=i;

State:=msLining;

xs:=MyDraw.FindByNumber(i).x; xt:=xs;

ys:=MyDraw.FindByNumber(i).y; yt:=ys;

MyDraw.SetActive(i);

end ;

end;

procedure TIO.DrawLine(x1,y1:Integer);

begin

if State=msLining then

with MyCanvas do

begin

Pen.Width:=2;

Pen.Color:=MovingColor;

Pen.Mode:=pmXor;

Pen.Style:=psSolid;

MoveTo(xs,ys);

LineTo(xt,yt);

MoveTo(xs,ys);

LineTo(x1,y1);

xt:=x1;

yt:=y1;

end;

{if State=msMove then

with MyCanvas do

begin

Pen.Width:=2;

Pen.Color:=MovingColor;

Pen.Mode:=pmXor;

Pen.Style:=psSolid;

MoveTo(xs,ys);

LineTo(xt,yt);

MoveTo(xs,ys);

LineTo(x1,y1);

xt:=x1;

yt:=y1;

end;}

end;

procedure TIO.FormMouseDown( X, Y: Integer);

var Mini,Maxi,i,j,Temp,Te:integer;

b,k:real;

Flag:Boolean;

function StepRound(Num,Step:integer):integer;

begin

if (Num mod Step)>(Step/2)then Result:=Num- Num mod Step+Step

else Result:=(Num div Step)*Step;

end;

begin

Te:=MyDraw.FindNumberByXY(X,Y);

if (Te=-1)and(state<>msMove) then

with MyData,MyDraw do begin

i:=1;

j:=1;

Flag:=false;

repeat

repeat

if (Dimension>0)and(Matrix[i,j]=1) then begin

Mini:=Min(FindByNumber(i).x,FindByNumber(j).x);

Maxi:=Max(FindByNumber(i).x,FindByNumber(j).x);

if Mini<>Maxi then

k:=(FindByNumber(i).y-

FindByNumber(j).y)/(FindByNumber(i).x-FindByNumber(j).x)

else k:=0;

b:= FindByNumber(i).y- (k*FindByNumber(i).x) ;

if (X>=Mini)and(X=(k*X+b-8) )and ( YDimension);

inc(j);

i:=1;

until(Flag)or(j>Dimension);

end

else begin

if FirstPointActive then begin

if State=msMove then begin

flag:=true;

MyDraw.move(FirstPoint,x,y);

MyDraw.SetUnActive(FirstPoint);

DrawAll;

FirstPointActive:=False;

end;

LastPoint:=Te

end

else begin

FirstPoint:=Te;

FirstPointActive:=True;

end;

MyDraw.SetActive(Te);

if State=msDelete then

RemovePoint(Te);

Exit;

end;

if not flag then begin

if FSnapToGrid then

IONewPoint(StepRound(x,GrigStep),StepRound(y,GrigStep))

else IONewPoint(x,y);end;

end;

procedure TIO.Select(FirstPoint,LastPoint:integer);

var s:string;

begin

with MyData do begin

DrawPath(FirstPoint,LastPoint,true);

S:=InputBox('Ввод','Введите длину ребра ','');

if(s='')or(not(StrToInt(S) in [1..250]))then begin

ShowMessage('Некорректно введена длина');

exit;

end;

{ if Oriented then

if Matrix[FirstPoint,LastPoint]<>0 then

MatrixLength[FirstPoint,LastPoint]:=StrToInt(S)else

MatrixLength[LastPoint,FirstPoint]:=StrToInt(S)

else

begin }

LengthActive:=True;

SetRebroLength(FirstPoint,LastPoint,StrToInt(S));

// end;

DrawPath(FirstPoint,LastPoint,false);

end;

end;

procedure TIO.DrawPath(First,Last:integer;Light:boolean=false);

var s:string;

begin

with MyDraw,MyCanvas do

begin

{!!pmMerge} Pen.Mode:=pmCopy;

Pen.Width:=2;

brush.Style:=bsClear;

Font.Color:=TextColor;

PenPos:=FindByNumber(First);

if Light then begin

Pen.Color:=clYellow;

SetActive(First);

SetActive(Last);

end

else Pen.Color:=RebroColor;

LineTo(FindByNumber(Last).x,

FindByNumber(Last).y );

if (MyData.LengthActive)and

(MyData.MatrixLength[First,Last]<>0) then

begin

s:=IntToStr(MyData.MatrixLength[First,Last]);

TextOut((FindByNumber(Last).x+FindByNumber(First).x)div 2,

(FindByNumber(Last).y+FindByNumber(First).y)

div 2-13,s);

end;

DrawSelf(First);

DrawSelf(Last);

end;

end;

procedure TIO.DrawAll;

var i,j:byte;

begin

for i:=1 to MyData.Dimension do

for j:=1 to MyData.Dimension do

if MyData.Matrix[i,j]=1 then DrawPath(i,j,false);

MyDraw.DrawAll;

end;

procedure TIO.IONewPoint(xPos,yPos:integer);

begin

MyData.NewPoint;

MyDraw.NewPoint(xPos,yPos);

MyDraw.DrawAll;

end;

procedure TIO.DrawCoordGrid(x,y,x1,y1:integer);

var i,j,nx,ny,nx1,ny1:integer;

begin

if FDrawGrid then begin

nx:=x div GrigStep;

nx1:=x1 div GrigStep;

ny:=y div GrigStep;

ny1:=y1 div GrigStep;

MyCanvas.Brush.Style:=bsClear;

MyCanvas.Pen.Color:=GridColor;

for i:=1 to nx1-nx do

for j:=1 to ny1-ny do

MyCanvas.Pixels[i*GrigStep,y1-j*GrigStep]:=GridColor;

end;

if FDrawCoord then

with MyCanvas do begin

Pen.Width:=1;

MoveTo(nx+GrigStep,y-5);

LineTo(nx+GrigStep,y1+2);

LineTo(x1-4,y1+2);

{horizontal}

for i:=1 to nx1-nx do begin

MoveTo(nx+i*GrigStep,y1-1);

LineTo(nx+i*GrigStep,y1+5);

TextOut(nx+i*GrigStep-5,y1+8,IntToStr((i-1)*Mashtab));

end; {vertical}

for i:=1 to ny1-ny do begin

MoveTo(x+2,y1-GrigStep*i);

LineTo(x+7,y1-GrigStep*i);

TextOut(x-15,y1-i*GrigStep-GrigStep div 2,IntToStr(i*Mashtab));

end;

end;

end;

constructor TIO.Create(Canvas:TCanvas);

begin

GrigStep:=20;

FSnapToGrid:=true;

GridColor:=clBlack;

RebroColor:=clMaroon;

MovingColor:=clBlue;

TextColor:=clBlack;

Mashtab:=1;

MyCanvas:=Canvas;

State:=msNewPoint;

FDrawCoord:=false;

end;

procedure TIO.RemovePoint(Num: integer);

var j:integer;N,MPenPos:TPoint;

begin

{with MyCanvas do begin

Pen.Width:=2;

Pen.Color:=RebroColor;

Pen.Mode:=pmXor;

Pen.Style:=psSolid;

MPenPos:=MyDraw.FindByNumber(Num);

for j:=1 to MyData.Dimension do

if MyData.Matrix[Num,j]=1 then begin

N:=MyDraw.FindByNumber(j);

PolyLine([MPenPos,N]);

end;}

{ Pen.Mode:=pmNot;

for j:=1 to MyData.Dimension do

if MyData.Matrix[Num,j]=1 then begin

N:=MyDraw.FindByNumber(j);

PolyLine([MPenPos,N]);

end;

end;}

MyData.Remove(Num);

MyDraw.Remove(Num);

end;

end.

Модуль визуального отображения графа в окне программы:

unit DrawingObject;

interface

uses

>

type

Colors=(Red,RedLight,Blue,Yellow,Green,Purple);

Obj=record

Place :TRect;

PlaceX,PlaceY :integer;

Color :Colors ;

end;

TDrawingObject =>

protected

MyCanvas:TCanvas;

public

Dim:integer;

Bitmaps:array[1..6]of TBitmap;

Arr:array of Obj;

constructor Create(Canvas:TCanvas);

procedure Remove(Num:integer);

procedure NewPoint(x,y:integer);

procedure DrawSelf(Num:integer);

procedure DrawSelfXY(X,Y:integer);

function HasPoint(Num,X,Y:integer): Boolean;

destructor Destroy ;

procedure DrawAll;

procedure Clear;

procedure Save(FileName:string);

procedure Load(FileName:string);

procedure SetActive(Num:integer);

procedure SetUnActive(Num:integer);

procedure SetAllUnActive;

procedure Move(number,x,y:integer);

procedure SetColor(Num:integer;NewColor:byte);

function FindByNumber(Num:integer): TPoint;

function FindNumberByXY(X,Y:integer):integer ;

end;

var MyDraw:TDrawingObject;

implementation

procedure TDrawingObject.Clear;

begin

Dim:=0;

Arr:=nil;

end;

procedure TDrawingObject.NewPoint(x,y:integer);

begin

inc(Dim);

SetLength(Arr,Dim+1);

with Arr[Dim] do

begin

PlaceX:=x;

PlaceY:=y;

Place.Left:=x-Bitmaps[1].Width div 2;

Place.Top:=y-Bitmaps[1].Width div 2;

Place.Right:=x+Bitmaps[1].Width div 2;

Place.Bottom:=y+Bitmaps[1].Width div 2;

Color :=Red;

end;

end;

constructor TDrawingObject.Create(Canvas:TCanvas);

var i:byte;

begin

MyCanvas:=Canvas;

Dim:=0;

for i:=1 to 6 do

Bitmaps[i]:=TBitmap.Create;

Bitmaps[1].LoadFromResourceName(hInstance,'nBit');

Bitmaps[2].LoadFromResourceName(hInstance,'aBit');

Bitmaps[3].LoadFromResourceName(hInstance,'Blue');

Bitmaps[4].LoadFromResourceName(hInstance,'Yellow');

Bitmaps[5].LoadFromResourceName(hInstance,'Green');

Bitmaps[6].LoadFromResourceName(hInstance,'Purple');

for i:=1 to 6 do

Bitmaps[i].Transparent:=True;

end;

procedure TDrawingObject.DrawSelfXY(X,Y:integer);

begin

DrawSelf(FindNumberByXY(X,Y));

end;

procedure TDrawingObject.DrawSelf(Num:integer);

begin

with Arr[Num] do

case Color of

Red: MyCanvas.Draw(Place.Left,Place.Top,Bitmaps[1]);

RedLight: MyCanvas.Draw(Place.Left,Place.Top,Bitmaps[2]);

Blue: MyCanvas.Draw(Place.Left,Place.Top,Bitmaps[3]);

Green: MyCanvas.Draw(Place.Left,Place.Top,Bitmaps[4]);

Yellow: MyCanvas.Draw(Place.Left,Place.Top,Bitmaps[5]);

Purple: MyCanvas.Draw(Place.Left,Place.Top,Bitmaps[6]);

else

MyCanvas.Draw(Place.Left,Place.Top,Bitmaps[1]);

end;

end;

function TDrawingObject.HasPoint(Num,X,Y:integer): Boolean;

begin

with Arr[Num] do

if(X >= Place.Left) and (X = Place.Top) and (Y MatrixLength[j,i] )

then Lymbda[j]:=Lymbda[i] + MatrixLength[j,i];

until Proverka ;

Path[1]:= EndPoint ;

j:=1;

PathPlace:=2;

repeat

TempPoint:=1;

Flag:=False;

repeat

if ( Matrix[ Path[ PathPlace-1 ],TempPoint] =1 )and (

Lymbda[ Path[ PathPlace-1] ] =

( Lymbda[TempPoint] + MatrixLength[ Path[PathPlace-1 ],

TempPoint] ) )

then Flag:=True

else Inc( TempPoint );

until Flag;

Path[ PathPlace ]:=TempPoint;

inc( PathPlace );

MyIO.DrawPath(Path[ PathPlace-2 ],Path[ PathPlace -1],true);

// ShowMessage('f');

until(Path[ PathPlace - 1 ] = StartPoint);

// MyIO.DrawPath(Path[ PathPlace-1 ],Path[ PathPlace ],true);

end;

end;

function TMinLength.Proverka:Boolean;

var i,j:integer;

Flag:boolean;

begin

i:=1;

Flag:=False;

With MyData do begin

repeat

j:=1;

repeat

if Matrix[i,j]=1 then

if ( Lymbda[j]-Lymbda[i] )>MatrixLength[j,i]then Flag:=True;

inc(j);

until(j>Dimension)or(Flag);

inc(i);

until(i>Dimension)or(Flag);

Result:=not Flag;

end;

end;

end.

-----------------------

[pic]

[pic]

[pic]

[pic]