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

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

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


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


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


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


Воронеж 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 году анонсировано положительное решение задачи с использованием ЭВМ.

/> <td/> />
/>  Другая старая топологическая задача, которая особеннодолго не поддавалась решению и будоражила умы любителей головоломок, известнакак “задача об электро -, газо — и водоснабжении”. В 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(V1,E1) графа G(V, E) называется граф с множеством вершин V1ÍV и множеством ребер (дуг) E1Í E, — такими, что каждое ребро (дуга) из E1 инцидентно(инцидентна) только вершинам из V1. Иначе говоря,подграф содержит некоторые вершины исходного графа и некоторые рёбра (толькоте, оба конца которых входят в подграф).

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

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

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

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

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

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

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

Данноепонятие грани, по — существу, совпадает с понятием грани многогранника. Вкачестве поверхности в этом случае выступает поверхность многогранника. Если многогранниквыпуклый, его можно изобразить на плоскости, сохранив все грани. Это можнонаглядно представить следующим образом: одну из граней многогранника растягиваем,а сам многогранник «расплющиваем» так, чтобы он весь поместился внутри этой грани.В результате получим плоский граф. Грань, которую мы растягивали «исчезнет», ноей будет соответствовать грань, состоящая из части плоскости, ограничивающейграф.

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

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

16.   Конечная последовательностьнеобязательно различных рёбер E1,E2,...En называетсямаршрутом длины n, если существует последовательность V1,V2,… Vn необязательно различных вершин, таких, что Ei= (Vi-1,Vi ).

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

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

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

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

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

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

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

24.   Граф называется kсвязным (k — реберно- связным), если удаление не менееk вершин (ребер)приводит к потере свойства связности.

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

26.   Длина маршрута (цепи, простой цепи) равна количествуребер а порядке их прохождения. Длина кратчайшей простой цепи, соединяющейвершины vi и vjв графе G, называется расстояниемd (vi, vj) между vi и vj.

27.   Степень вершины — число  ребер, которым инцидентнавершина V, обозначается D(V).

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

Средиодноместныхопераций наиболее употребительны: удаление и добавление ребра или вершины,стягивание ребра (отождествление пары смежных вершин), подразбиение ребра (т.е.замена ребра(u, v) на пару (u, w), (w,v), где w — новая вершина) и др.

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

28.   Два графа 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).

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

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

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

/>

 

 

 

 

 

 

 

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

 

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

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

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

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

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

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

 

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

 

Раскраскойграфа G = (V,E) называется отображение D: V® N.Раскраска называется правильной, еслиобразы любых двух смежных вершин различны: D (U)≠ D (V), если (U,V) ÎI. Хроматическим числом графа называетсяминимальное количество красок, необходимое для правильной раскраски графа.

 Теорема 5.

Граф является планарным тогда и только тогда, когда онне содержит подграфа, изоморфного одному из следующих (графы Понтрягина — Куратовского).

                                       

/> /> /> /> /> /> <td/> /> />
                  ГрафК33                                                            Граф К5

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

 

Способы задания графов:

 

/>1. Геометрический:

2.Матрица смежности:

a В c d A 1 1 B 1 1 C 1 1 1 D 1

                               

 

Матрица смежности  — квадратная  матрица, размерности,равной количеству вершин. При этом  а[ i, j ]-целое число, равное количествурёбер, связывающих

i-ю,j-ю вершину. Если в графе нет петель, то диагональные элементы равны 0 .

Если рёбра не повторяются, то все элементы 0 или 1.Если граф неориентированный, то матрица симметрична.

3.Матрица инцидентности:

a В с d A 1 1 B 1 1 C 1 1 D 1 1

4. Явное заданиеграфа как алгебраической системы:

<{a,b,c,d},{u,v,w,x}; {(u,a),(u,b),(v,b),(v,c),(w,c),(w,a),(x,c),(x,d)}>.

Так как мы рассматриваем только простые графы, граф нам прощеопределять как модель, носителем которой является множество вершин, а отношение– бинарное отношение смежности вершин. Тогда данный граф запишется как <{a,b,c,d};{(a,b), (b,a),(b,c),(c,b),(a,c),(c,a),(c,d),(d,c)}>.В таком представлении ребру соответствуют две пары вершин (v1,v2)и (v2,v1), инцидентных данному ребру. Чтобызадать такое представление, достаточно для каждого ребра указать двухэлементноемножество вершин – его мы и будем отождествлять с ребром. Для данного графарёбра задаются множеством {{a,b},{b,c},{a,c},{c,d}}и граф мы будем записывать как пару (V,E), где V – множествовершин, а E – множество рёбер.

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

Например:

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

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


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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

Будем рассматриватьориентированные графы G = <V, E>, дугамкоторых приписаны веса. Это означает, что каждой дуге <u, v>ÎE поставлено в соответствие некоторое вещественное числоa (u, v), называемое весом данной дуги.

Нас будет интересоватьнахождение кратчайшего пути между фиксированными вершинами s, t ÎV. Длинутакого кратчайшего пути мы будем обозначать d (s, t) и называтьрасстоянием от s до t (расстояние, определенное такимобразом, может быть отрицательным). Если не существует ни одного пути из sв t, то полагаем d (s, t) = ╔. Если каждый контур нашего графа имеет положительнуюдлину, то кратчайший путь будет всегдаэлементарным путем, т.е. впоследовательности v1,..., vpне будетповторов.

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

Можно дать многопрактических интерпретаций задачи о кратчайших путях. Например, вершинымогут соответствовать городам, а каждая дуга — некоторому пути, длина которогопредставлена весом дуги. Мы ищем затем кратчайшие пути между городами. Вес дугитакже может соответствовать стоимости (или времени) передачи информациимежду вершинами. В таком случае мы ищем самый дешевый (или самый скорый) путьпередачи информации. Еще одну ситуацию получаем, когда вес дуги <u, v>равен вероятности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, E>-ориентированныйграф, | V|  = n, | E|  = m.Если выбор вершины u происходит в результате просмотра всех вершин, тосложность нашего алгоритма — O(n2). Если мы просматриваемтолько список ПРЕДШ[v], содержащий все вершины u, такиечто u (r)v, то вэтом случае сложность будет O(m).

Отметим, что в случаеположительных весов ребер задача о кратчайшем пути в неориентированномграфе легко сводится к аналогичной задаче для некоторого ориентированного графа.С этой целью достаточно заменить каждое ребро {u, v}двумя дугами á u, vñи áv, uñ, каждая стаким же весом, что и {u, v}. Однако в случае неположительных весовэто приводит к возникновению контуров с неположительной длиной.

Далее будем всегда предполагать,что G = < V, E>являетсяориентированным графом, |V|  = n, |E|  = m.В целях упрощения изложения и избежания вырожденных случаев при оценкесложности алгоритмов будем исключать ситуации, при которых «большинство» вершинизолированные.

Будем также предполагать, что веса дуг запоминаются вмассиве A[u, v], u, Î 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. Программаопределения кратчайшего пути в графе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 связано сболее тесными отношениями между объектами и реальным программным кодом. Объектыпомещаются в вашу форму, при этом код, отвечающий объектам, автоматическизаписывается в исходный файл. Этот код компилируется, обеспечивая существенноболее высокую производительность, чем визуальная среда, которая интерпретируетинформацию лишь в ходе исполнения программы.

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

Программа«Определение кратчайшего пути в графе» разработана в среде «Delphi», работаетпод ОС «Windows»-95,98,2000,NT.

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

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

/>

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

Кнопка«Загрузить» /> предназначенадля загрузки ранее сохраненного графа из файла.

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

Кнопка «Переместить» /> предназначена для перемещениявершин графа.

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

При нажатии на кнопку «Новый» /> рабочее поле программы будет очищенои появится возможность ввода нового графа.

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

Для очистки результатов работы алгоритма определениякратчайшего пути в графе необходимо нажать кнопку «Обновить» />.

При нажатии на кнопку «Настройки» /> на экране появится окно,в котором можно настроить параметры сетки рабочего поля программы и цветавводимого графа.

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

/>

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

При включенной кнопке «Показывать сетку» /> отображаетсясетка для удобства ввода вершин.

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

При включенной кнопке «Выравнивать по сетке» /> новые вершиныбудут автоматически выравниваться по координатной сетке.

Если выбрать две различные вершины (щелчком левойкнопки мыши) и нажать на кнопку />, то программа найдет кратчайшийпуть между вершинами.

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

unit MinLength;

interface

uses

  Windows, Messages, SysUtils, Classes, Graphics, Controls, Dialogs,

  StdCtrls,IO,Data,AbstractAlgorithmUnit;

type

  TMinLength = class(TAbstractAlgorithm)

  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]thenFlag:=True;

               inc(j);

             until(j>Dimension)or(Flag);

             inc(i);

           until(i>Dimension)or(Flag);

           Result:=not Flag;

           end;

         end;

end.

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

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

/>
ЗАКЛЮЧЕНИЕ

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

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

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

Двоичные кодовые деревья допускают интерпретацию врамках теории поиска. Каждой вершине при этом сопоставляется вопрос, ответитьна который можно либо «да», либо «нет». Утвердительному иотрицательному ответу соответствуют два ребра, выходящие из вершины.«Опрос» завершается, когда удается установить то, что требовалось.

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

Графы и химия

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

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


ПРИЛОЖЕНИЕТекстпрограммы определения кратчайшего пути в графе

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

unit MainUnit;

interface

uses

  Windows,Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

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

  ActnList,ExtCtrls;

const

  crMyCursor = 5;

type

  TForm1 =class(TForm)

    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;

    procedureFormMouseDown(Sender: TObject; Button: TMouseButton;

      Shift:TShiftState; X, Y: Integer);

    procedureFormCreate(Sender: TObject);

    procedureFormMouseMove(Sender: TObject; Shift: TShiftState; X,

      Y: Integer);

    procedureFormPaint(Sender: TObject);

    procedureFormKeyDown(Sender: TObject; var Key: Word;

      Shift:TShiftState);

    procedureClearButtonClick(Sender: TObject);

    procedureKommiToolButtonClick(Sender: TObject);

    procedurePaintingToolButtonClick(Sender: TObject);

    procedureSnapToGridButtonClick(Sender: TObject);

    procedureHelpButtonClick(Sender: TObject);

    procedureAutoLengthButtonClick(Sender: TObject);

    procedureSettingButtonClick(Sender: TObject);

    procedureNotFarButtonClick(Sender: TObject);

    procedureMinLengthButtonClick(Sender: TObject);

    procedureMovePointButtonClick(Sender: TObject);

    procedureRemovePointButtonClick(Sender: TObject);

    procedureTimer1Timer(Sender: TObject);

    procedureALoadExecute(Sender: TObject);

    procedureAShowGrigExecute(Sender: TObject);

    procedureASaveExecute(Sender: TObject);

    procedurePaintBox1Paint(Sender: TObject);

    procedureUpdateButtonClick(Sender: TObject);

    procedureEilerButtonClick(Sender: TObject);

    procedureClockClick(Sender: TObject);

  private

    procedureMyPopupHandler(Sender: TObject);

    { Private declarations}

  public

    { Publicdeclarations }

  end;

var

  Form1: TForm1;

implementation

usesIO,Data,Commercial,DrawingObject,Setting,NotFar,MinLength, Eiler,

  SplashScreen;

{$R *.DFM}

procedureTForm1.FormMouseDown(Sender: TObject; Button: TMouseButton;

  Shift:TShiftState; X, Y: Integer);

begin

if Button=mbLeftthen  begin

 MyIO.FormMouseDown( X, Y);

  if(MyIO.State=msMove)then

      ifMyIO.FirstPointActive then

         Cursor :=crMyCursor

      else begin

         Repaint;

         Cursor :=crDefault;

      end;  

    end

else

  MyIO.MakeLine(X,Y);

end;

procedureTForm1.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;

procedureTForm1.FormMouseMove(Sender: TObject; Shift: TShiftState; X,

  Y: Integer);

begin

MyIO.DrawLine(x,y);

end;

procedureTForm1.FormPaint(Sender: TObject);

begin

PaintBox1Paint(Sender);

end;

procedureTForm1.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;

procedureTForm1.MyPopupHandler(Sender: TObject);

var s:string;

begin

  with Sender asTMenuItem do begin

      s:=Caption;

     MyData.Load(s);

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

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

  end;

Repaint;

end;

procedureTForm1.ClearButtonClick(Sender: TObject);

begin

MyData.Clear;

MyDraw.Clear;

Repaint;

end;

procedureTForm1.KommiToolButtonClick(Sender: TObject);

begin

 IfMyData.Dimension<2 then Exit;

 MyCommercial:=TCommercial.Create;

 MyCommercial.Make;

 MyCommercial.Free;

end;

procedureTForm1.EilerButtonClick(Sender: TObject);

begin

 IfMyData.Dimension<2 then Exit;

 EilerC:=TEiler.Create;

 EilerC.Make;

 EilerC.Free;

 MyIO.DrawAll;

 RePaint;

end;

procedureTForm1.PaintingToolButtonClick(Sender: TObject);

begin

 IfMyData.Dimension<2 then Exit;

MyPaint:=TPaintingGraphClass.Create;

MyPaint.Make;

RePaint;

MyPaint.Free;

end;

procedureTForm1.SnapToGridButtonClick(Sender: TObject);

begin

MyIO.FSnapToGrid:=SnapToGridButton.Down;

end;

procedureTForm1.HelpButtonClick(Sender: TObject);

begin

Application.HelpContext(10);

end;

procedureTForm1.AutoLengthButtonClick(Sender: TObject);

begin

MyIo.AutoLength:=AutoLengthButton.Down;

end;

procedureTForm1.SettingButtonClick(Sender: TObject);

begin

 SettingForm.Show;

end;

procedureTForm1.NotFarButtonClick(Sender: TObject);

begin

IfMyData.Dimension<2 then Exit;

MyNotFar:=TNotFar.Create;

MyNotFar.Make;

MyNotFar.Free;

end;

procedureTForm1.MinLengthButtonClick(Sender: TObject);

begin

IfMyData.Dimension<2 then Exit;

MyMinLength:=TMinLength.Create;

MyMinLength.Make;

MyMinLength.Free;

end;

procedureTForm1.MovePointButtonClick(Sender: TObject);

begin

if MovePointButton.Downthen MyIO.State:=msMove else

 MyIO.State:=msNewPoint;

ifMovePointButton.Down=false then

  Cursor :=crDefault;

end;

procedureTForm1.RemovePointButtonClick(Sender: TObject);

begin

ifReMovePointButton.Down then MyIO.State:=msDelete else

 MyIO.State:=msNewPoint;

  Repaint;

end;

procedureTForm1.Timer1Timer(Sender: TObject);

begin

 Clock.Caption:=TimeToStr(Time);

end;

procedureTForm1.ALoadExecute(Sender: TObject);

var s:string;

begin

  ifOpenDialog1.Execute then

    try

      s:=OpenDialog1.Filename;

     MyData.Load(s);

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

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

    finally

    end;

Repaint;

end;

procedureTForm1.AShowGrigExecute(Sender: TObject);

begin

MyIO.FDrawGrid:=ShowGridButton.Down;

Repaint;

end;

procedure TForm1.ASaveExecute(Sender:TObject);

var s:string;

    m:TMenuItem;

begin

  ifSaveDialog1.Execute then

    try

     s:=SaveDialog1.Filename;

     MyData.Save(s);

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

     MyDraw.Save(s+'.Pos')

    finally

    end;

  m:=TMenuItem.Create(Self);

 m.Caption:=SaveDialog1.Filename;

  m.OnClick :=MyPopUpHandler;

 LoadMenu.Items.Add(m);

end;

procedureTForm1.PaintBox1Paint(Sender: TObject);

begin

 MyIO.DrawCoordGrid(16,16,ClientWidth-30,ClientHeight-140);

MyIO.DrawAll;

end;

procedureTForm1.UpdateButtonClick(Sender: TObject);

begin

MyDraw.SetAllUnActive;

MyIO.DrawAll;

MyIO.FirstPointActive:=false;

end;

procedureTForm1.ClockClick(Sender: TObject);

begin

Splash.Show;

end;

end.

Модуль управления окномнастроек:

unit Setting;

interface

uses

  Windows,Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

  Buttons,StdCtrls, Spin,IO,MainUnit, ExtCtrls;

type

  TSettingForm =class(TForm)

    GridGroupBox:TGroupBox;

    Label1:TLabel;

    Label2:TLabel;

    ColorDialog1:TColorDialog;

    Label3:TLabel;

    OkBitBtn:TBitBtn;

    CancelBitBtn:TBitBtn;

    ColorButton:TPanel;

    Label4:TLabel;

    Label5:TLabel;

    CoordCheckBox:TCheckBox;

    GridCheckBox:TCheckBox;

    StepSpinEdit:TSpinEdit;

   MashtabSpinEdit: TSpinEdit;

    Colors:TGroupBox;

    Panel1:TPanel;

    Panel2:TPanel;

    Panel3:TPanel;

    Label6:TLabel;

    Label7:TLabel;

    Label8:TLabel;

    procedureColorButtonClick(Sender: TObject);

    procedureOkBitBtnClick(Sender: TObject);

    procedureFormShow(Sender: TObject);

    procedureFormClose(Sender: TObject; var Action: TCloseAction);

    procedureCoordCheckBoxClick(Sender: TObject);

    procedureGridCheckBoxClick(Sender: TObject);

    procedureCancelBitBtnClick(Sender: TObject);

    procedurePanel2Click(Sender: TObject);

  private

    { Privatedeclarations }

  public

    { Publicdeclarations }

  end;

var

  SettingForm:TSettingForm;

implementation

{$R *.DFM}

procedureTSettingForm.ColorButtonClick(Sender: TObject);

begin

  ifColorDialog1.Execute then begin

   ColorButton.Color:=ColorDialog1.Color;

   MyIO.GridColor:=Color;

    Form1.Repaint;

  end;

end;

procedureTSettingForm.OkBitBtnClick(Sender: TObject);

begin

 MyIO.GridColor:=ColorButton.Color;

  MyIO.GrigStep:=StepSpinEdit.Value;

 MyIO.Mashtab:=MashtabSpinEdit.Value;

  Close;

end;

procedureTSettingForm.FormShow(Sender: TObject);

begin

with MyIO do begin

 ColorButton.Color:=MyIO.GridColor;

 StepSpinEdit.Value:=MyIO.GrigStep;

 MashtabSpinEdit.Value:=MyIO.Mashtab;

 CoordCheckBox.Checked:=MyIO.FDrawCoord;

 GridCheckBox.Checked:=MyIO.FDrawGrid;

 Panel2.Color:=RebroColor ;

 Panel3.Color:=TextColor ;

 Panel1.Color:=MovingColor ;

end;

end;

procedureTSettingForm.FormClose(Sender: TObject;

  var Action:TCloseAction);

begin

with MyIO do begin

 GridColor:=ColorButton.Color;

 GrigStep:=StepSpinEdit.Value;

 Mashtab:=MashtabSpinEdit.Value;

 FDrawCoord:=CoordCheckBox.Checked;

 FDrawGrid:=GridCheckBox.Checked;

 Form1.ShowGridButton.Down:=GridCheckBox.Checked;

 RebroColor:=Panel2.Color ;

 TextColor:=Panel3.Color ;

 MovingColor:=Panel1.Color ;

  end;

  Form1.Repaint;

end;

procedureTSettingForm.CoordCheckBoxClick(Sender: TObject);

begin

MyIO.FDrawCoord:=CoordCheckBox.Checked;

//Form1.Repaint;

end;

procedureTSettingForm.GridCheckBoxClick(Sender: TObject);

begin

MyIO.FDrawGrid:=GridCheckBox.Checked;

//Form1.Repaint;

end;

procedureTSettingForm.CancelBitBtnClick(Sender: TObject);

begin

Close;

end;

procedureTSettingForm.Panel2Click(Sender: TObject);

begin

with Sender asTPanel do

  ifColorDialog1.Execute then begin

   Color:=ColorDialog1.Color;

  end;

end;

end.

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

unit IO;

interface

uses Data,DrawingObject,Graphics,windows,Math,Controls,Dialogs,SysUtils;

type

MouseState=(msNewPoint,msLining,msMove,msDelete);

TIO=class

   private

     xt,yt,xs,ys:integer;

//        FLining: boolean;

     ActivePoint:integer;

        MyCanvas:TCanvas;

   public

       GridColor:TColor;

      RebroColor:TColor;

       TextColor:TColor;

     MovingColor:TColor;

           State:MouseState;

       FDrawGrid:boolean;

      FDrawCoord:boolean;

     FSnapToGrid:boolean;

        GrigStep:integer;

      FirstPoint:integer;

FirstPointActive:boolean;

       LastPoint:integer;

      AutoLength:boolean;

         Mashtab:integer;

 procedureMakeLine(X, Y: Integer);

 procedureDrawPath(First,Last:integer;Light:boolean=false);

 procedureIONewPoint(xPos,yPos:integer);

 procedureDrawAll;

 procedureFormMouseDown(  X, Y: Integer);

 procedureSelect(FirstPoint,LastPoint:integer);

 procedureDrawCoordGrid(x,y,x1,y1:integer);

 procedureDrawLine(x1,y1:Integer);

 procedureRemovePoint(Num:integer);

 constructorCreate(Canvas:TCanvas);

end;

var MyIO:TIO;

implementation

procedureTIO.MakeLine(X, Y: Integer);

var i:integer;

  V1,V2:TPoint;

begin

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

  if i<>-1then

    ifState=msLining then begin

      MyData.Rebro(ActivePoint,i);

      ifAutoLength 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;

procedureTIO.DrawLine(x1,y1:Integer);

begin

if State=msLiningthen

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=msMovethen

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);

 varMini,Maxi,i,j,Temp,Te:integer;

          b,k:real;

          Flag:Boolean;

   functionStepRound(Num,Step:integer):integer;

     begin

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

         elseResult:=(Num div Step)*Step;

     end;

         begin

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

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

           withMyData,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);

                     ifMini<>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<Maxi) and

                       ( Y>=(k*X+b-8) )and ( Y<=(k*X+b+8))

                       then begin

                         Flag:=true;

                         Select(i,j);

                         Exit;

                       end;

                end;

                inc(i);

              until(Flag)or(i>Dimension);

              inc(j);

              i:=1;

            until(Flag)or(j>Dimension);

           end

            elsebegin

              ifFirstPointActive then begin

                ifState=msMove then  begin

                 flag:=true;

                 MyDraw.move(FirstPoint,x,y);

                 MyDraw.SetUnActive(FirstPoint);

                 DrawAll;

                 FirstPointActive:=False;

               end;

                LastPoint:=Te

              end

              elsebegin

                 FirstPoint:=Te;

                 FirstPointActive:=True;

              end;

             MyDraw.SetActive(Te);

              ifState=msDelete then

                 RemovePoint(Te);

             Exit;

            end;

             ifnot flag then begin

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

                 elseIONewPoint(x,y);end;

         end;

procedureTIO.Select(FirstPoint,LastPoint:integer);

         vars:string;

         begin

           withMyData do  begin

            DrawPath(FirstPoint,LastPoint,true);

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

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

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

              exit;

             end;

     {      ifOriented then

             ifMatrix[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;

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

          vars:string;

          begin

          withMyDraw,MyCanvas do

            begin

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

            Pen.Width:=2;

            brush.Style:=bsClear;

            Font.Color:=TextColor;

            PenPos:=FindByNumber(First);

             if Lightthen 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;

procedureTIO.DrawAll;

var i,j:byte;

          begin

            for i:=1  to MyData.Dimension do

            for j:=1  to MyData.Dimension do

               ifMyData.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;

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

vari,j,nx,ny,nx1,ny1:integer;

begin

   if FDrawGridthen begin

     nx:=x divGrigStep;

     nx1:=x1 divGrigStep;

     ny:=y divGrigStep;

     ny1:=y1 divGrigStep;

    MyCanvas.Brush.Style:=bsClear;

    MyCanvas.Pen.Color:=GridColor;

     for  i:=1  tonx1-nx do

        for  j:=1 to ny1-ny do

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

     end;

   if FDrawCoordthen

    with MyCanvasdo begin

     Pen.Width:=1;

    MoveTo(nx+GrigStep,y-5);

    LineTo(nx+GrigStep,y1+2);

    LineTo(x1-4,y1+2);

                          {horizontal}

     for  i:=1  tonx1-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 tony1-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;

constructorTIO.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;

procedureTIO.RemovePoint(Num: integer);

varj:integer;N,MPenPos:TPoint;

begin

  {with MyCanvasdo begin

     Pen.Width:=2;

     Pen.Color:=RebroColor;

     Pen.Mode:=pmXor;

     Pen.Style:=psSolid;

     MPenPos:=MyDraw.FindByNumber(Num);

  for  j:=1  toMyData.Dimension do

   ifMyData.Matrix[Num,j]=1 then begin

     N:=MyDraw.FindByNumber(j);

     PolyLine([MPenPos,N]);

    end;}

{     Pen.Mode:=pmNot;

    for  j:=1  toMyData.Dimension do

   ifMyData.Matrix[Num,j]=1 then begin

     N:=MyDraw.FindByNumber(j);

      PolyLine([MPenPos,N]);

    end;

  end;}

                 MyData.Remove(Num);

                  MyDraw.Remove(Num);

end;

end.

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

unitDrawingObject;

interface

uses

  Classes,Windows, Graphics,dialogs,SysUtils;

type

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

    Obj=record

      Place         :TRect;

      PlaceX,PlaceY :integer;

      Color         :Colors ;

    end;

  TDrawingObject =class(TObject)

  protected

   MyCanvas:TCanvas;

  public

    Dim:integer;

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

    Arr:array ofObj;

    constructorCreate(Canvas:TCanvas);

    procedureRemove(Num:integer);

    procedureNewPoint(x,y:integer);

    procedureDrawSelf(Num:integer);

    procedureDrawSelfXY(X,Y:integer);

    functionHasPoint(Num,X,Y:integer): Boolean;

    destructorDestroy ;

    procedureDrawAll;

    procedureClear;

    procedureSave(FileName:string);

    procedureLoad(FileName:string);

    procedure SetActive(Num:integer);

    procedureSetUnActive(Num:integer);

    procedureSetAllUnActive;

    procedureMove(number,x,y:integer);

    procedureSetColor(Num:integer;NewColor:byte);

    functionFindByNumber(Num:integer): TPoint;

    functionFindNumberByXY(X,Y:integer):integer ;

  end;

var MyDraw:TDrawingObject;

implementation

procedureTDrawingObject.Clear;

begin

  Dim:=0;

  Arr:=nil;

end;

procedureTDrawingObject.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;

procedureTDrawingObject.DrawSelfXY(X,Y:integer);

begin

 DrawSelf(FindNumberByXY(X,Y));

end;

procedureTDrawingObject.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;

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

begin

 with Arr[Num] do

    if(X >=Place.Left) and (X <= Place.Right)

      and (Y >=Place.Top) and (Y <= Place.Bottom)then

      Result :=True

    else

      Result :=False;

end;

procedureTDrawingObject.DrawAll;

var

  i: Integer;

begin

  for i :=1  toDim do

    DrawSelf(i);

end;

functionTDrawingObject.FindByNumber(Num:integer): TPoint;

begin

      Result.x :=Arr[Num].PlaceX;

      Result.y :=Arr[Num].PlaceY;

end;

functionTDrawingObject.FindNumberByXY(X,Y:integer):integer ;

var

  i: Integer;

begin

Result:=-1;

  for i :=1 to Dimdo

    ifHasPoint(i,X,Y) then

      begin

       Result:=i;

       Exit;

      end;

  end;

procedureTDrawingObject.SetUnActive(Num:integer);

begin

   Arr[Num].Color:=Red;

    DrawSelf(Num);

end;

destructorTDrawingObject.Destroy ;

var i:byte;

begin

  for i:=1 to 6 do

    Bitmaps[i].Free;

end;

procedureTDrawingObject.Save(FileName:string);

var stream:TWriter;

   st:TFileStream;

    i:integer;

begin

  try

  st:=TFileStream.Create(FileName,fmCreate);

   stream :=TWriter.Create(st,256);

  stream.WriteInteger(Dim);

  for  i:=1  toDim do

       begin

      stream.WriteBoolean(true);

      stream.WriteInteger(Arr[i].Place.Left);

      stream.WriteInteger(Arr[i].Place.Top);

      stream.WriteInteger(Arr[i].Place.Right);

      stream.WriteInteger(Arr[i].Place.Bottom);

      stream.WriteInteger(Arr[i].PlaceX);

      stream.WriteInteger(Arr[i].PlaceY);

       end;

  finally

   stream.Free;

   st.Free;

  end;

end;

procedureTDrawingObject.Load(FileName:string);

var stream:TReader;

    i:integer;

   st:TFileStream;

    s:boolean;

begin

  try

  st:=TFileStream.Create(FileName,fmOpenRead);

   stream := TReader.Create(st,256);

  Dim:=stream.ReadInteger;

  SetLength(Arr,Dim+1);

  for  i:=1  toDim do

       begin

      Arr[i].Color:=Red;

      s:=stream.ReadBoolean;

      Arr[i].Place.Left:=stream.ReadInteger;

      Arr[i].Place.Top:=stream.ReadInteger;

      Arr[i].Place.Right:=stream.ReadInteger;

      Arr[i].Place.Bottom:=stream.ReadInteger;

      Arr[i].PlaceX:=stream.ReadInteger;

      Arr[i].PlaceY:=stream.ReadInteger;

       end;

  finally

   stream.Free;

   st.Free;

  end;

end;

procedureTDrawingObject.Remove(Num:integer);

var    i:integer;

begin

        for i:=Num to Dim-1 do

            Arr[i]:=Arr[i+1];

        Dec(Dim);

 SetLength(Arr,Dim+1);

  DrawAll;

end;

procedureTDrawingObject.SetActive(Num:integer);

begin

Arr[Num].Color:=RedLight;

DrawSelf(Num);

end;

procedure TDrawingObject.SetAllUnActive;

var i:byte;

begin

for  i:=1  to Dimdo

  Arr[i].Color:=Red;

end;

procedureTDrawingObject.SetColor(Num:integer;NewColor:Byte);

begin

case NewColor of

   1:Arr[Num].Color:=Red;

   2:Arr[Num].Color:=RedLight;

   3: Arr[Num].Color:=Blue;

   4:Arr[Num].Color:=Green;

   5:Arr[Num].Color:=Yellow;

   6:Arr[Num].Color:=Purple;

  end;

    DrawSelf(Num);

end;

{$Rbitmaps\shar.res}

procedureTDrawingObject.Move(number, x, y:integer);

begin

  with Arr[number]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;

 DrawSelf(number);

end;

end.

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

unit Data;

interface

usesDialogs,Classes,SysUtils;

type TData=class

 public

 LengthActive:boolean;

  Dimension:   integer;

 Oriented:boolean;

  Matrix:      array of array of Integer;

  MatrixLength: arrayof array of Integer;

    procedureClear;

    procedureNewPoint;

    procedureRebro(First,Second:integer);

    procedureSetRebroLength(First,Second,Length:integer);

    procedureSave(FileName:string);

    procedureLoad(FileName:string);

    procedureRemove(Num:integer);

    constructorCreate;

    end;

var MyData:TData;

implementation

constructorTData.Create;

begin  Clear;

end;

procedureTData.Clear;

begin           Oriented:=false;

                LengthActive:=True;

                Matrix:=nil;

                MatrixLength:=nil;

                Dimension:=0;

end;

procedureTData.NewPoint;

begin

   inc(Dimension);

 SetLength(Matrix,Dimension+1,Dimension+1);

  if LengthActivethen

    SetLength(MatrixLength,Dimension+1,Dimension+1);

end;

procedureTData.Rebro(First,Second:integer);

begin

  Matrix[First,Second]:=1;

  Matrix[Second,First]:=1;

end;

procedureTData.Save(FileName:string);

var stream:TWriter;

   st:TFileStream;

    i,j:integer;

begin

  try

  st:=TFileStream.Create(FileName,fmCreate);

   stream :=TWriter.Create(st,256);

  stream.WriteInteger(Dimension);

  stream.WriteBoolean(LengthActive);

  stream.WriteBoolean(Oriented);

  for  i:=1  toDimension do

    for  j:=1  toDimension do

       stream.WriteInteger(Matrix[i,j]);

  for  i:=1  toDimension do

    for  j:=1  toDimension do

      stream.WriteInteger(MatrixLength[i,j]);

  finally

   stream.Free;

   st.Free;

  end;

end;

procedureTData.Load(FileName:string);

var stream:TReader;

    i,j:integer;

   st:TFileStream;

begin

  try

  st:=TFileStream.Create(FileName,fmOpenRead);

   stream :=TReader.Create(st,256);

  Dimension:=stream.ReadInteger;

  SetLength(Matrix,Dimension+1,Dimension+1);

  SetLength(MatrixLength,Dimension+1,Dimension+1);

  LengthActive:=stream.ReadBoolean;

  Oriented:=stream.ReadBoolean;

  for  i:=1  toDimension do

    for  j:=1  toDimension do

      Matrix[i,j]:=stream.ReadInteger;

  for  i:=1  toDimension do

    for  j:=1  toDimension do

      MatrixLength[i,j]:=stream.ReadInteger;

  finally

   stream.Free;

   st.Free;

  end;

end;

procedureTData.Remove(Num:integer);

var   i,j:integer;

begin

        for i:=Num to Dimension-1 do

          for j:=1 to Dimension do

             begin

            Matrix[j,i]:=Matrix[j,i+1];

            MatrixLength[j,i]:=MatrixLength[j,i+1];

             end;

        for i:=Num  to Dimension-1 do

          for j:=1  to Dimension-1 do

             begin

            Matrix[i,j]:=Matrix[i+1,j];

            MatrixLength[i,j]:=MatrixLength[i+1,j];

             end;

       Dec(Dimension);

  SetLength(Matrix,Dimension+1,Dimension+1);

  SetLength(MatrixLength,Dimension+1,Dimension+1);

end;

procedure TData.SetRebroLength(First,Second,Length:integer);

begin

    MatrixLength[First,Second]:=Length ;

    MatrixLength[Second,First]:=Length ;

end;

end.

Модуль определениякратчайшего пути в графе:

unit MinLength;

interface

uses

  Windows,Messages, SysUtils, Classes, Graphics, Controls, Dialogs,

 StdCtrls,IO,Data,AbstractAlgorithmUnit;

type

  TMinLength =class(TAbstractAlgorithm)

  private

    StartPoint:integer;

    EndPoint:integer;

    First:Boolean;

     Lymbda:arrayof integer;

     functionProverka:Boolean;

  public

     procedureMake;

  end;

var

  MyMinLength:TMinLength;

implementation

uses MainUnit,Setting;

procedureTMinLength.Make;

         var i ,j : integer;

           PathPlace,TempPoint:Integer;

           flag:boolean;

         begin

           withMyData do begin

    StartPoint:=MyIO.FirstPoint;

    EndPoint:=MyIO.LastPoint;

                    SetLength(Lymbda,Dimension+1);

           SetLength(Path,Dimension+1);

           fori:=1 to Dimension do

             Lymbda[i]:=100000;

          Lymbda[StartPoint]:=0;

           repeat

             fori:=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];

           untilProverka ;

          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 );

             untilFlag;

             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;

functionTMinLength.Proverka:Boolean;

         vari,j:integer;

            Flag:boolean;

         begin

           i:=1;

          Flag:=False;

           WithMyData do begin

           repeat

             j:=1;

            repeat

               ifMatrix[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.

еще рефераты
Еще работы по информатике, программированию