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

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

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

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

Курсовой

проект

По дисциплине:

Тема:

Воронеж 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 года была единственной в течение практически 100 лет. Энтузиазм к дилеммам теории графов возродился около середины прошедшего столетия и был сосредоточен основным образом в Великобритании. Имелось много обстоятельств для такового оживления исследования графов. Естественные науки оказали свое воздействие на это благодаря исследованиям электронных цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к исследованию бинарных отношений в форме графов. Огромное число фаворитных головоломок подавалось формулировкам конкретно в определениях графов, и это приводило к осознанию, что почти все задачки такового рода содержат некое математическое ядро, значимость которого выходит за рамки определенного вопросца. Более именитая посреди этих задач–неувязка 4 красок, в первый раз поставленная перед математиками Де Морганом около 1850 года. Никакая неувязка не вызывала настолько бессчетных и смышленых работ в области теории графов. Благодаря собственной обычный формулировке и раздражающей неуловимости она до сего времени остается массивным стимулом исследовательских работ разных параметров графов.

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

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

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

1. Теория Графов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

==
2,95576…

Для числа

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

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

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

цветов.

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

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

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

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

1.2. Главные определения и аксиомы теории графов

.

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

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

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

.

— ребро нацеленного графа.

Граф именуется

, если у него нет рёбер.

Верхушка Х именуется

ребру G , если ребро соединяет эту верхушку с какой-нибудь иной верхушкой.

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

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

Подграф именуется

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

Верхушки именуются

, если существует ребро , их соединяющее.

Два ребра G1
и G2
именуются

, если существует верхушка, инцидентная сразу G1
и G2
.

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

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

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

именуется граф без рёбер.

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

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

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

Если совпадают, то маршрут

.

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

.

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

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

.

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

.

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

.

Граф именуется

, если для всех 2-ух вершин существует путь, соединяющий эти верхушки.

Хоть какой наибольший связный подграф (другими словами, не находящийся в остальных связных подграфах) графа G именуется

. Бессвязный граф имеет, по последней мере, две составляющие связности.

Граф именуется
—

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

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

графа.

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

d (vi
, vj
) меж vi
и vj
.

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

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

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

,
) на пару (
,
), (
,
), где
— новенькая верхушка) и др.

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

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

, если существует взаимнооднозначное соответствие меж огромными количествами вершин V1
и V2
и меж огромными количествами рёбер Е1
и Е2
, такое, чтоб сохранялось отношение инцидентности.

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

Пусть задан граф G=(V;E),где V — огромное количество вершин, E — огромное количество рёбер, тогда 2[E]=Σ(V), т.е. двойное количество рёбер равно сумме степеней вершин.

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

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

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

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

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

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

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

4. В графе с N верхушками и К компонентами связности число рёбер не превосходит 1/2(N-K)(N-K+1).

5. Пусть у графа G есть N вершин . Пусть D(G)- малая из степеней вершин этого графа . Тогда D(G) > 1/2 (N-1).

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

.

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

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

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

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

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

4. Связный и удаление 1-го хоть какого ребра делает его бессвязным.

5. Неважно какая пара вершин соединяется единственной цепью.

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

графа G = (V,E) именуется отображение D
® N
. Раскраска именуется

, если образы всех 2-ух смежных вершин различны: D (U) ≠ D (V), если (U
V) Î I.

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

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

Граф К33 Граф К5

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

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

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

a

В

c

d

A

0

1

1

0

B

1

0

1

0

C

1

1

0

1

D

0

0

1

0

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

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

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

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

a

В

с

d

A

1

1

0

0

B

0

1

1

0

C

1

0

1

0

D

0

0

1

1

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

<{
},{
}
{(
),(
),(
),(
),(
),(
),(
), (
)}>.

Потому что мы рассматриваем лишь обыкновенные графы, граф нам проще определять как модель, носителем которой является огромное количество вершин, а отношение – бинарное отношение смежности вершин. Тогда данный граф запишется как <{
}
{(
), (
),(
),(
),(
),(
),(
),(
)}>. В таком представлении ребру соответствуют две пары вершин (
1

2
) и (
2

1
), инцидентных данному ребру. Чтоб задать такое количество вершин, а
– огромное количество рёбер.

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

к примеру:

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

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

2. задачки на графах.

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

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

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

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

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

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

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

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

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

— задачка о наивысшем потоке

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

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

лучший подбор интенсивностей выполнения работ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Будем разглядывать направленные графы
= <
,

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

Î
поставлено в соответствие некое вещественное число
(
,
), называемое
данной дуги.

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

не будет повторов.

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

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

равен

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

Поначалу разглядим
, а не самих путей. Но, зная расстояние, мы можем при условии положительной длины всех контуров просто найти кратчайшие пути. Для этого довольно отметить, что для случайных
,
Î
(
) существует верхушка
, таковая что
(
,
) =
(
,
) +
(
,
).

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

Дальше мы можем отыскать верхушку
, для которой
(
,
) =
(
,
) +
(
,
), и т.д.

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

Разумеется, что она описывает (при воззвании очередности) кратчайший путь из
в
.

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

[
] от фиксированной верхушки
до всех других вершин
Î
, фиксированная верхушка
, матрица весов ребер,
[
,
],
,
Î
.

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

begin

:= Æ ;

;
:=
;

while

╧
do

begin

:= верхушка, для которой
[
] =
[
] +
[
,
];

;

:=

end

end.

Пусть <
,

-ориентированный граф, |

=
, |

=
. Если выбор верхушки
происходит в итоге просмотра всех вершин, то сложность нашего метода — O(
2
). Если мы просматриваем лишь перечень
[
], содержащий все верхушки
, такие что

, то в этом случае сложность будет O(
).

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

и á
,

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

Дальше будем постоянно полагать, что
= <
,

является нацеленным графом, |

=
, |

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

Будем также полагать, что веса дуг запоминаются в массиве
[
,
],
,
Î
(
[
,
] содержит вес
(
,
)).

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

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

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

Просто можно показать, что D
[
] равно тогда
(
,
) — расстоянию от
до
.

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

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

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

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

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.

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

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

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

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

Клавиша «Сохранить» создана для сохранения графа в файл.

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

Клавиша «Удалить» создана для удаления вершин графа.

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

Клавиша «Помощь» вызывает помощь программки.

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

При нажатии на клавишу «Опции» на дисплее покажется окно, в каком можно настроить характеристики сетки рабочего поля программки и цвета вводимого графа.

Окно опций смотрится последующим образом:

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

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

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

При включенной кнопочке «Сглаживать по сетке» новейшие верхушки будут автоматом выравниваться по координатной сетке.

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

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

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

inc(j);

until(j>Dimension)or(Flag);

inc(i);

until(i>Dimension)or(Flag);

Result:=not Flag;

end;

end;

end.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

Cn
H
2

n

+2

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

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

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

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

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

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

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

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

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

1. Белов Теория Графов,
1968.

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

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афах и сетях.
1990

10. Романовский И.В. Алгоpитмы pешения экстpемальных задач.
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;

procedure FormMouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure FormCreate(Sender: TObject);

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

Y: Integer);

procedure FormPaint(Sender: TObject);

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

Shift: TShiftState);

procedure ClearButtonClick(Sender: TObject);

procedure KommiToolButtonClick(Sender: TObject);

procedure PaintingToolButtonClick(Sender: TObject);

procedure SnapToGridButtonClick(Sender: TObject);

procedure HelpButtonClick(Sender: TObject);

procedure AutoLengthButtonClick(Sender: TObject);

procedure SettingButtonClick(Sender: TObject);

procedure NotFarButtonClick(Sender: TObject);

procedure MinLengthButtonClick(Sender: TObject);

procedure MovePointButtonClick(Sender: TObject);

procedure RemovePointButtonClick(Sender: TObject);

procedure Timer1Timer(Sender: TObject);

procedure ALoadExecute(Sender: TObject);

procedure AShowGrigExecute(Sender: TObject);

procedure ASaveExecute(Sender: TObject);

procedure PaintBox1Paint(Sender: TObject);

procedure UpdateButtonClick(Sender: TObject);

procedure EilerButtonClick(Sender: TObject);

procedure ClockClick(Sender: TObject);

private

procedure MyPopupHandler(Sender: TObject);

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

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

SplashScreen;

{$R *.DFM}

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

Shift: TShiftState; X, Y: Integer);

begin

if Button=mbLeft then begin

MyIO.FormMouseDown( X, Y);

if (MyIO.State=msMove)then

if MyIO.FirstPointActive then

Cursor := crMyCursor

else begin

Repaint;

Cursor := crDefault;

end;

end

else

MyIO.MakeLine(X, Y);

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

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

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

MyData:=TData.Create;

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

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

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

end;

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

Y: Integer);

begin

MyIO.DrawLine(x,y);

end;

procedure TForm1.FormPaint(Sender: TObject);

begin

PaintBox1Paint(Sender);

end;

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

Shift: TShiftState);

begin

if (Key=vk_Escape) then

begin

MyData.Remove(MyData.Dimension);

MyDraw.Remove(MyData.Dimension);

Repaint;

end;

end;

procedure TForm1.MyPopupHandler(Sender: TObject);

var s:string;

begin

with Sender as TMenuItem do begin

s:=Caption;

MyData.Load(s);

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

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

end;

Repaint;

end;

procedure TForm1.ClearButtonClick(Sender: TObject);

begin

MyData.Clear;

MyDraw.Clear;

Repaint;

end;

procedure TForm1.KommiToolButtonClick(Sender: TObject);

begin

If MyData.Dimension<2 then Exit;

MyCommercial:=TCommercial.Create;

MyCommercial.Make;

MyCommercial.Free;

end;

procedure TForm1.EilerButtonClick(Sender: TObject);

begin

If MyData.Dimension<2 then Exit;

EilerC:=TEiler.Create;

EilerC.Make;

EilerC.Free;

MyIO.DrawAll;

RePaint;

end;

procedure TForm1.PaintingToolButtonClick(Sender: TObject);

begin

If MyData.Dimension<2 then Exit;

MyPaint:=TPaintingGraphClass.Create;

MyPaint.Make;

RePaint;

MyPaint.Free;

end;

procedure TForm1.SnapToGridButtonClick(Sender: TObject);

begin

MyIO.FSnapToGrid:=SnapToGridButton.Down;

end;

procedure TForm1.HelpButtonClick(Sender: TObject);

begin

Application.HelpContext(10);

end;

procedure TForm1.AutoLengthButtonClick(Sender: TObject);

begin

MyIo.AutoLength:=AutoLengthButton.Down;

end;

procedure TForm1.SettingButtonClick(Sender: TObject);

begin

SettingForm.Show;

end;

procedure TForm1.NotFarButtonClick(Sender: TObject);

begin

If MyData.Dimension<2 then Exit;

MyNotFar:=TNotFar.Create;

MyNotFar.Make;

MyNotFar.Free;

end;

procedure TForm1.MinLengthButtonClick(Sender: TObject);

begin

If MyData.Dimension<2 then Exit;

MyMinLength:=TMinLength.Create;

MyMinLength.Make;

MyMinLength.Free;

end;

procedure TForm1.MovePointButtonClick(Sender: TObject);

begin

if MovePointButton.Down then MyIO.State:=msMove else

MyIO.State:=msNewPoint;

if MovePointButton.Down=false then

Cursor := crDefault;

end;

procedure TForm1.RemovePointButtonClick(Sender: TObject);

begin

if ReMovePointButton.Down then MyIO.State:=msDelete else

MyIO.State:=msNewPoint;

Repaint;

end;

procedure TForm1.Timer1Timer(Sender: TObject);

begin

Clock.Caption:=TimeToStr(Time);

end;

procedure TForm1.ALoadExecute(Sender: TObject);

var s:string;

begin

if OpenDialog1.Execute then

try

s:=OpenDialog1.Filename;

MyData.Load(s);

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

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

finally

end;

Repaint;

end;

procedure TForm1.AShowGrigExecute(Sender: TObject);

begin

MyIO.FDrawGrid:=ShowGridButton.Down ;

Repaint;

end;

procedure TForm1.ASaveExecute(Sender: TObject);

var s:string;

m:TMenuItem;

begin

if SaveDialog1.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;

procedure TForm1.PaintBox1Paint(Sender: TObject);

begin

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

MyIO.DrawAll;

end;

procedure TForm1.UpdateButtonClick(Sender: TObject);

begin

MyDraw.SetAllUnActive;

MyIO.DrawAll;

MyIO.FirstPointActive:=false;

end;

procedure TForm1.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;

procedure ColorButtonClick(Sender: TObject);

procedure OkBitBtnClick(Sender: TObject);

procedure FormShow(Sender: TObject);

procedure FormClose(Sender: TObject; var Action: TCloseAction);

procedure CoordCheckBoxClick(Sender: TObject);

procedure GridCheckBoxClick(Sender: TObject);

procedure CancelBitBtnClick(Sender: TObject);

procedure Panel2Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

SettingForm: TSettingForm;

implementation

{$R *.DFM}

procedure TSettingForm.ColorButtonClick(Sender: TObject);

begin

if ColorDialog1.Execute then begin

ColorButton.Color:=ColorDialog1.Color;

MyIO.GridColor:=Color;

Form1.Repaint;

end;

end;

procedure TSettingForm.OkBitBtnClick(Sender: TObject);

begin

MyIO.GridColor:=ColorButton.Color;

MyIO.GrigStep:=StepSpinEdit.Value;

MyIO.Mashtab:=MashtabSpinEdit.Value;

Close;

end;

procedure TSettingForm.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;

procedure TSettingForm.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;

procedure TSettingForm.CoordCheckBoxClick(Sender: TObject);

begin

MyIO.FDrawCoord:=CoordCheckBox.Checked;

//Form1.Repaint;

end;

procedure TSettingForm.GridCheckBoxClick(Sender: TObject);

begin

MyIO.FDrawGrid:=GridCheckBox.Checked ;

//Form1.Repaint;

end;

procedure TSettingForm.CancelBitBtnClick(Sender: TObject);

begin

Close;

end;

procedure TSettingForm.Panel2Click(Sender: TObject);

begin

with Sender as TPanel do

if ColorDialog1.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;

procedure MakeLine(X, Y: Integer);

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

procedure IONewPoint(xPos,yPos:integer);

procedure DrawAll;

procedure FormMouseDown( X, Y: Integer);

procedure Select(FirstPoint,LastPoint:integer);

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

procedure DrawLine(x1,y1:Integer);

procedure RemovePoint(Num:integer);

constructor Create(Canvas:TCanvas);

end;

var MyIO:TIO;

implementation

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

var i:integer;

V1,V2:TPoint;

begin

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

if i<>-1 then

if State=msLining then begin

MyData.Rebro(ActivePoint,i);

if AutoLength then begin

V1:=MyDraw.FindByNumber(ActivePoint);

V2:=MyDraw.FindByNumber(i);

MyData.SetRebroLength(ActivePoint,i,Round(

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

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

end;

MyCanvas.MoveTo(xs,ys);

MyCanvas.LineTo(xt,yt);

DrawPath(ActivePoint,i,false);

State:=msNewPoint;

MyDraw.SetUnActive(ActivePoint);

end

else begin

ActivePoint:=i;

State:=msLining;

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

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

MyDraw.SetActive(i);

end ;

end;

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

begin

if State=msLining then

with MyCanvas do

begin

Pen.Width:=2;

Pen.Color:=MovingColor;

Pen.Mode:=pmXor;

Pen.Style:=psSolid;

MoveTo(xs,ys);

LineTo(xt,yt);

MoveTo(xs,ys);

LineTo(x1,y1);

xt:=x1;

yt:=y1;

end;

{if State=msMove then

with MyCanvas do

begin

Pen.Width:=2;

Pen.Color:=MovingColor;

Pen.Mode:=pmXor;

Pen.Style:=psSolid;

MoveTo(xs,ys);

LineTo(xt,yt);

MoveTo(xs,ys);

LineTo(x1,y1);

xt:=x1;

yt:=y1;

end;}

end;

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

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

b,k:real;

Flag:Boolean;

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

begin

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

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

end;

begin

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

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

with MyData,MyDraw do begin

i:=1;

j:=1;

Flag:=false;

repeat

repeat

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

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

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

if Mini<>Maxi then

k:=(FindByNumber(i).y-FindByNumber(j).y)/(FindByNumber(i).x-FindByNumber(j).x)

else k:=0;

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

if (X>=Mini)and(X<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

else begin

if FirstPointActive then begin

if State=msMove then begin

flag:=true;

MyDraw.move(FirstPoint,x,y);

MyDraw.SetUnActive(FirstPoint);

DrawAll;

FirstPointActive:=False;

end;

LastPoint:=Te

end

else begin

FirstPoint:=Te;

FirstPointActive:=True;

end;

MyDraw.SetActive(Te);

if State=msDelete then

RemovePoint(Te);

Exit;

end;

if not flag then begin

if FSnapToGrid then IONewPoint(StepRound(x,GrigStep),StepRound(y,GrigStep))

else IONewPoint(x,y);end;

end;

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

var s:string;

begin

with MyData do begin

DrawPath(FirstPoint,LastPoint,true);

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

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

ShowMessage(‘Неправильно введена длина’);

exit;

end;

{ if Oriented then

if Matrix[FirstPoint,LastPoint]<>0 then

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

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

else

begin }

LengthActive:=True;

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

// end;

DrawPath(FirstPoint,LastPoint,false);

end;

end;

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

var s:string;

begin

with MyDraw,MyCanvas do

begin

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

Pen.Width:=2;

brush.Style:=bsClear;

Font.Color:=TextColor;

PenPos:=FindByNumber(First);

if Light then begin

Pen.Color:=clYellow;

SetActive(First);

SetActive(Last);

end

else Pen.Color:=RebroColor;

LineTo(FindByNumber(Last).x,

FindByNumber(Last).y );

if (MyData.LengthActive)and

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

begin

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

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

(FindByNumber(Last).y+FindByNumber(First).y) div 2-13,s);

end;

DrawSelf(First);

DrawSelf(Last);

end;

end;

procedure TIO.DrawAll;

var i,j:byte;

begin

for i:=1 to MyData.Dimension do

for j:=1 to MyData.Dimension do

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

MyDraw.DrawAll;

end;

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

begin

MyData.NewPoint;

MyDraw.NewPoint(xPos,yPos);

MyDraw.DrawAll;

end;

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

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

begin

if FDrawGrid then begin

nx:=x div GrigStep;

nx1:=x1 div GrigStep;

ny:=y div GrigStep;

ny1:=y1 div GrigStep;

MyCanvas.Brush.Style:=bsClear;

MyCanvas.Pen.Color:=GridColor;

for i:=1 to nx1-nx do

for j:=1 to ny1-ny do

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

end;

if FDrawCoord then

with MyCanvas do begin

Pen.Width:=1;

MoveTo(nx+GrigStep,y-5);

LineTo(nx+GrigStep,y1+2);

LineTo(x1-4,y1+2);

{horizontal}

for i:=1 to nx1-nx do begin

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

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

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

end; {vertical}

for i:=1 to ny1-ny do begin

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

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

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

end;

end;

end;

constructor TIO.Create(Canvas:TCanvas);

begin

GrigStep:=20;

FSnapToGrid:=true;

GridColor:=clBlack;

RebroColor:=clMaroon;

MovingColor:=clBlue;

TextColor:=clBlack;

Mashtab:=1;

MyCanvas:=Canvas;

State:=msNewPoint;

FDrawCoord:=false;

end;

procedure TIO.RemovePoint(Num: integer);

var j:integer;N,MPenPos:TPoint;

begin

{with MyCanvas do begin

Pen.Width:=2;

Pen.Color:=RebroColor;

Pen.Mode:=pmXor;

Pen.Style:=psSolid;

MPenPos:=MyDraw.FindByNumber(Num);

for j:=1 to MyData.Dimension do

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

N:=MyDraw.FindByNumber(j);

PolyLine([MPenPos,N]);

end;}

{ Pen.Mode:=pmNot;

for j:=1 to MyData.Dimension do

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

N:=MyDraw.FindByNumber(j);

PolyLine([MPenPos,N]);

end;

end;}

MyData.Remove(Num);

MyDraw.Remove(Num);

end;

end.

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

unit DrawingObject;

interface

uses

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 of Obj;

constructor Create(Canvas:TCanvas);

procedure Remove(Num:integer);

procedure NewPoint(x,y:integer);

procedure DrawSelf(Num:integer);

procedure DrawSelfXY(X,Y:integer);

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

destructor Destroy ;

procedure DrawAll;

procedure Clear;

procedure Save(FileName:string);

procedure Load(FileName:string);

procedure SetActive(Num:integer);

procedure SetUnActive(Num:integer);

procedure SetAllUnActive;

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

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

function FindByNumber(Num:integer): TPoint;

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

end;

var MyDraw:TDrawingObject;

implementation

procedure TDrawingObject.Clear;

begin

Dim:=0;

Arr:=nil;

end;

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

begin

inc(Dim);

SetLength(Arr,Dim+1);

with Arr[Dim] do

begin

PlaceX:=x;

PlaceY:=y;

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

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

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

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

Color :=Red;

end;

end;

constructor TDrawingObject.Create(Canvas:TCanvas);

var i:byte;

begin

MyCanvas:=Canvas;

Dim:=0;

for i:=1 to 6 do

Bitmaps[i]:=TBitmap.Create;

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

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

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

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

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

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

for i:=1 to 6 do

Bitmaps[i].Transparent:=True;

end;

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

begin

DrawSelf(FindNumberByXY(X,Y));

end;

procedure TDrawingObject.DrawSelf(Num:integer);

begin

with Arr[Num] do

case Color of

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

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

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

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

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

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

else

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

end;

end;

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

begin

with Arr[Num] do

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

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

Result := True

else

Result := False;

end;

procedure TDrawingObject.DrawAll;

var

i: Integer;

begin

for i :=1 to Dim do

DrawSelf(i);

end;

function TDrawingObject.FindByNumber(Num:integer): TPoint;

begin

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

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

end;

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

var

i: Integer;

begin

Result:=-1;

for i :=1 to Dim do

if HasPoint(i,X,Y) then

begin

Result:=i;

Exit;

end;

end;

procedure TDrawingObject.SetUnActive(Num:integer);

begin

Arr[Num].Color:=Red;

DrawSelf(Num);

end;

destructor TDrawingObject.Destroy ;

var i:byte;

begin

for i:=1 to 6 do

Bitmaps[i].Free;

end;

procedure TDrawingObject.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 to Dim 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;

procedure TDrawingObject.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 to Dim 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;

procedure TDrawingObject.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;

procedure TDrawingObject.SetActive(Num:integer);

begin

Arr[Num].Color:=RedLight;

DrawSelf(Num);

end;

procedure TDrawingObject.SetAllUnActive;

var i:byte;

begin

for i:=1 to Dim do

Arr[i].Color:=Red;

end;

procedure TDrawingObject.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;

{$R bitmapsshar.res}

procedure TDrawingObject.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

uses Dialogs,Classes,SysUtils;

type TData=class

public

LengthActive:boolean;

Dimension: integer;

Oriented:boolean;

Matrix: array of array of Integer;

MatrixLength: array of array of Integer;

procedure Clear;

procedure NewPoint;

procedure Rebro(First,Second:integer);

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

procedure Save(FileName:string);

procedure Load(FileName:string);

procedure Remove(Num:integer);

constructor Create;

end;

var MyData:TData;

implementation

constructor TData.Create;

begin Clear;

end;

procedure TData.Clear;

begin Oriented:=false;

LengthActive:=True;

Matrix:=nil;

MatrixLength:=nil;

Dimension:=0;

end;

procedure TData.NewPoint;

begin

inc(Dimension);

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

if LengthActive then

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

end;

procedure TData.Rebro(First,Second:integer);

begin

Matrix[First,Second]:=1;

Matrix[Second,First]:=1;

end;

procedure TData.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 to Dimension do

for j:=1 to Dimension do

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

for i:=1 to Dimension do

for j:=1 to Dimension do

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

finally

stream.Free;

st.Free;

end;

end;

procedure TData.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 to Dimension do

for j:=1 to Dimension do

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

for i:=1 to Dimension do

for j:=1 to Dimension do

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

finally

stream.Free;

st.Free;

end;

end;

procedure TData.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:array of integer;

function Proverka:Boolean;

public

procedure Make;

end;

var

MyMinLength: TMinLength;

implementation

uses MainUnit, Setting;

procedure TMinLength.Make;

var i ,j : integer;

PathPlace,TempPoint:Integer;

flag:boolean;

begin

with MyData do begin

StartPoint:=MyIO.FirstPoint;

EndPoint:=MyIO.LastPoint;

SetLength(Lymbda,Dimension+1);

SetLength(Path,Dimension+1);

for i:=1 to Dimension do

Lymbda[i]:=100000;

Lymbda[StartPoint]:=0;

repeat

for i:=1 to Dimension do

for j:=1 to Dimension do

if Matrix[i,j]=1 then

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

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

until Proverka ;

Path[1]:= EndPoint ;

j:=1;

PathPlace:=2;

repeat

TempPoint:=1;

Flag:=False;

repeat

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

Lymbda[ Path[ PathPlace-1] ] =

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

then Flag:=True

else Inc( TempPoint );

until Flag;

Path[ PathPlace ]:=TempPoint;

inc( PathPlace );

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

// ShowMessage(‘f’);

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

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

end;

end;

function TMinLength.Proverka:Boolean;

var i,j:integer;

Flag:boolean;

begin

i:=1;

Flag:=False;

With MyData do begin

repeat

j:=1;

repeat

if Matrix[i,j]=1 then

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

inc(j);

until(j>Dimension)or(Flag);

inc(i);

until(i>Dimension)or(Flag);

Result:=not Flag;

end;

end;

end.

]]>