Реферат: Нахождение кратчайшего пути
/>/>/>/>ВОРОНЕЖСКИЙ ИНСТИТУТ ВЫСОКИХТЕХНОЛОГИЙ
Факультет заочного и послевузовскогообучения
Курсовой проект
Подисциплине: «Технологияпрограммирования»
Тема: «Определение кратчайшего пути в графе»
Воронеж 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 14. Явное заданиеграфа как алгебраической системы:
<{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 Î 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.