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

36

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. ПОСТАНОВКА ЗАДАЧИ

2. ТЕОРИЯ ГРАФОВ КАК МАТЕМАТИЧЕСКИЙ АППАРАТ

ДЛЯ РЕШЕНИЯ ЗАДАЧ ПОДОБНОГО ТИПА

3. ОСНОВЫ ТЕОРИИ ГРАФОВ

3.1 Основные определения и теоремы

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

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

4. НАХОЖДЕНИЕ КРАТЧАЙШЕГО ПУТИ В ГРАФЕ

4.1 Волновой алгоритм

4.2 Алгоритм Дейкстры

ЗАКЛЮЧЕНИЕ

ПРИЛОЖЕНИЯ

Приложение 1. Программная реализация алгоритма Дейкстры

ЛИТЕРАТУРА

ВВЕДЕНИЕ

Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Но такой избыток ресурсов бывает не всегда. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся “на глазок” (теперь, впрочем, зачастую тоже).

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

Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича “Математические методы организации и планирования производства”. Поскольку методы, изложенные Л.В. Канторовичем, были мало пригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В. Канторовича осталась почти не замеченной.

Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В. Канторович и американец профессор Т. Купманс получили Нобелевскую премию по экономическим наукам за “вклад в разработку теории и оптимального использования ресурсов в экономике”.

В автобиографии, представленной в Нобелевский комитет, Леонид Витальевич Канторович рассказывает о событиях, случившихся в 1939 году. К нему, 26-летнему профессору-математику, обратились за консультацией сотрудники лаборатории планерного треста, которым нужно было решить задачу о наиболее выгодном распределении материала между станками. Эта задача сводилась к нахождению максимума линейной функции, заданной на многограннике. Максимум такой функции достигался в вершине, однако число вершин в этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился. Леонид Витальевич писал: “оказалось, что эта задача не является случайной. Я обнаружил большое число разнообразных по содержанию задач, имеющих аналогичный математический характер: наилучшее использование посевных площадей, выбор загрузки оборудования, рациональный раскрой материала, распределение транспортных грузопотоков… Это настойчиво побудило меня к поиску эффективного метода их решения”. И уже летом 1939 года была сдана в набор книга Л.В. Канторовича “Математические методы организации и планирования производства”, в которой закладывались основания того, что ныне называется математической экономикой.

Однако идеи Л.В. Канторовича не встретили понимания в момент их зарождения, были объявлены ересью, и его работа была прервана. Концепции Леонида Витальевича вскоре после войны были переоткрыты на западе. Американский экономист Т. Купманс в течение многих лет привлекал внимание математиков к ряду задач, связанных с военной тематикой. Он активно способствовал тому, чтобы был организован математический коллектив для разработки этих проблем. В итоге было осознано, что надо научиться решать задачи о нахождении экстремумов линейных функций на многогранниках, задаваемых линейными неравенствами. По предложению Купманса этот раздел математики получил название линейного программирования.

Американский математик А. Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течение пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.

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

А самому Леониду Витальевичу - как естественно было бы ему, испытав первые грозные удары ретроградов, остеречься от “грехов” молодости, забыть про всю эту экономику и вернуться к математике. Но Л.В. Канторович продолжает писать математические работы, навеянные экономическими идеями, участвует и в конкретных разработках на производстве. При этом (одновременно с Данцигом, но, не зная его работ) он разрабатывает метод, позже названный симплекс-методом. Как только в 50-е годы образуется маленький просвет, и кое-что из запретного становится возможным, он организует группу студентов на экономическом факультете ЛГУ для обучения методам оптимального планирования. А, начиная с 1960 года, Леонид Витальевич занимается только экономической и связанной с нею математической проблемами. Его вклад в этой области был отмечен Ленинской премией в 1965 году (присуждена ему совместно с В.С. Немчиновым и В.В. Новожиловым) и Нобелевской премией в 1975 году.

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

В развитие динамического программирования большой вклад внес голландский ученый Эдсгер Вайб Дейкстра (1930-2002). Рассказывать об этом человеке можно очень долго и много. Только список его работ занимает "увесистый" десятимегабайтовый pdf-файл. Можно перечислять научные регалии, звания и степени, бесконечно повторять слова "неоценимый вклад" и "основоположник". Он являлся создателем принципа семафоров, одной из концептуальных основ синхронизации вычислительных процессов, а также одним из главных разработчиков языка ALGOL. Среди специалистов в области вычислительной математики широко известен алгоритм поиска кратчайшего пути, известный также как алгоритм Дейкстры. В 1972 году за свой вклад в развитие информационных технологий Дейкстра был удостоен премии Тьюринга, которую называют аналогом Нобелевской премии в области компьютеров.

Здесь сразу уместно будет привести несколько фрагментов из воспоминаний Дейкстры. Во-первых, алгоритм этот создавался не из простого любопытства, а для решения вполне конкретной задачи, а именно, - минимизации длины проводников на аналоге "материнской платы" нового разрабатываемого командой компьютера X1, так что лавровый венок создателя первой "утилиты всех времен и народов" класса CAD-CAE Дейкстре можно присваивать смело. А вот "во-вторых" лучше сказать словами самого Дейкстры: "На много лет и в широких кругах алгоритм поиска кратчайшего пути был основным источником моей славы, что мне всегда казалось странным - ведь он был создан даже без карандаша и бумаги, за чашкой кофе на солнечной террасе кафе в Амстердаме ...".

1. ПОСТАНОВКА ЗАДАЧИ

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

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

Нашу задачу можно переформулировать следующим образом:

В ориентированной, неориентированной или смешанной (т. е. такой, где часть дорог имеет одностороннее движение) сети V найти кратчайший путь из заданной вершины i во все остальные вершины. [11]

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

2. ТЕОРИЯ ГРАФОВ КАК МАТЕМАТИЧЕСКИЙ АППАРАТ ДЛЯ РЕШЕНИЯ ЗАДАЧ ПОДОБНОГО ТИПА

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

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

Рис. 1. Кенигсбергские мосты на карте, и в виде графа.

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

Свет вода газ

Рис.2. Задача о электро-газо-водоснабжения, схематично и в виде графа.

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

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

Рис. 3. Пространственные графы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. ОСНОВЫ ТЕОРИИ ГРАФОВ

3.1 Основные определения и теоремы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15. Конечная последовательность необязательно различных рёбер E₁,E₂,...E_n называется маршрутом длины n, если существует последовательность V₁, V₂, ... V_n необязательно различных вершин, таких, что E_i = (V_i-1,V_i ).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27. Два графа G₁=(V₁;E₁), G₂=(V₂;E₂),называются изоморфными, если существует взаимно-однозначное соответствие между множествами вершин V₁ и V₂ и между множествами рёбер Е₁ и Е₂, такое, чтобы сохранялось отношение инцидентности.

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

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

Теорема 1.

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

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

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

Теорема 3.

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

3.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).

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

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

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

Рис. 4. Пример дерева (генеалогическое).

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

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

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

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

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

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

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

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

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

Рис. 5. Геометрический способ задания графа

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

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

Матрица смежности - квадратная матрица, размерности, равной количеству вершин. A[i,j]=1, если существует ребро (i,j) (дуга <i,j>), A[i,j]=0 - в противном случае. Для неориентированных графов матрица смежности симметрична относительно главной диагонали.

Для взвешенных графов значение элемента A[i,j] обычно используют для хранения веса соответствующего ребра. Если граф неориентированный, то матрица симметрична. Если в графе нет петель, то диагональные элементы равны 0.

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

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

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

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

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

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

4. НАХОЖДЕНИЕ КРАТЧАЙШЕГО ПУТИ В ГРАФЕ

4.1 Волновой алгоритм

Прекрасно подойдет, если все пути из вершины в соседнюю равны по длине (цене, весу) Время O(n).

Дано: непyстой гpаф G=(V,E). Требуется найти путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (ребер).

I.

1. каждой вершине vi приписывается целое число T(vi) - волновая метка (начальное значение T(vi)=-1);

2. заводятся два списка OldFront и NewFront (старый и новый "фpонт волны"), а также пеpеменная T (текyщее вpемя);

3. OldFront:={s}; NewFront:={}; T(s):=0; T:=0;

4. для каждой из веpшин, входящих в OldFront, пpосматpиваются инцидентные (смежные) ей веpшины uj, и если T(uj) = -1, то T(uj):=T+1, NewFront:=NewFront + {uj};

5. если NewFront = {}, то ВЫХОД("нет решения");

6. если t О NewFront (т.е. одна из веpшин uj совпадает t), то найден кpатчайший пyть между s и t с T(t)=T+1 промежуточными ребрами; ВЫХОД("решение найдено");

7. OldFront:=NewFront; NewFront:={}; T:=T+1; goto (4).

Замечание: на шаге (4) "соседними" вершинами для неориентированных графов считаются все смежные вершины, а для орграфов - вершины, в которые из данной вершины ведут дуги.

II.

Если на шаге (6) была достигнyта веpшина t, то восстановить кpатчайший пyть можно следyющим обpазом: сpеди соседей веpшины t найдем любую веpшину с волновой меткой T(t)-1, сpеди соседей последней - веpшину с меткой T(t)-2, и т.д., пока не достигнем s. Найденная последовательность вершин определяет один из кpатчайших пyтей из s в t. Hа пpактике выгодно сохpанять на шаге (4) инфоpмацию о том, из какой веpшины "волна" пpишла в веpшинy uj - тогда восстановление пyти осyществляется быстpее.

Рис.6. Разметка графа после выполнения волнового алгоритма.

Идея этого метода весьма проста: в стороны от исходной точки распространяется волна.

Начальное значение волны - ноль.

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

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

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

Сам путь в получившемся массиве значений волны вычисляется по наименьшим клеткам.

4.2 Алгоритм Дейкстры

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

Известно, что все цены (прокладки пути или проезда) неотрицательны. Найти наименьшую стоимость пути 1->i для всех i=1..n за время O(n2).

В процессе работы алгоритма некоторые города будут выделенными (в начале - только город 1, в конце - все). При этом:

для каждого выделенного города i хранится наименьшая стоимость пути 1->i; при этом известно, что минимум достигается на пути, проходящем только через выделенные города;

для каждого невыделенного города i хранится наименьшая стоимость пути 1->i, в котором в качестве промежуточных используются только выделенные города.

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

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

Опишем более подробно схему работы алгоритма Дейкстры. Алгоритм использует три массива из N (= числу вершин сети) чисел каждый. Первый массив A содержит метки с двумя значения: 0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена); второй массив B содержит расстояния - текущие кратчайшие рас- стояния от до соответствующей вершины; третий массив с содержит номера вершин - k-й элемент С[k] есть номер предпоследней вершины на текущем кратчайшем пути из Vi в Vk. Матрица расстояний D[i,k] задает длины дуге D[i,k]; если такой дуги нет, то D[i,k] присваивается большое число Б, равное "машинной бесконечности".

Теперь можно описать:

1. (инициализация). В цикле от 1 до N заполнить нулями массив A; заполнить числом i массив C; перенести i-ю строку матрицы D в массив B, A[i]:=1; C[i]:=0 (i - номер стартовой вершины)

2. (общий шаг). Hайти минимум среди неотмеченных (т. е. тех k, для которых A[k]=0); пусть минимум достигается на индексе j, т. е. B[j]<=B[k] Затем выполняются следующие операции: A[j]:=1; если B[k]>B[j]+D[j,k], то (B[k]:=B[j]+D[j,k]; C[k]:=j) (Условие означает, что путь Vi ... Vk длиннее, чем путь Vi...Vj Vk). (Если все A[k] отмечены, то длина пути от Vi до Vk равна B[k]. Теперь надо) перечислить вершины, входящие в кратчайший путь).

3. (выдача ответа). (Путь от Vi до Vk выдается в обратном порядке следующей процедурой:)

1. z:=C[k];

2. Выдать z;

3. z:=C[z]. Если z = О, то конец, иначе перейти к 3.2.

Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность:O(n2).

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

ПРИЛОЖЕНИЕ 1.

Алгоритм Дейкстры. Реализация на языке Паскаль

Исходные данные для программы хранятся в текстовом файле DIJKSTRA.IN. Граф задается в виде списка пар вершин, соединенных ребрами с указанием их веса. Для примера - используем файл со следующим содержимым:

6 11 - в первой строке указывается, что в графе 6 вершин и 11 ребер

1 2 41 - ребро из вершины 1 в вершину 2 имеет вес 41

2 3 51 - ребро из вершины 2 в вершину 3 имеет вес 51

3 4 50 - ребро из вершины 3 в вершину 4 имеет вес 50

5 4 36 - ………. и т.д. ………

4 6 38

4 1 45

1 6 29

6 5 21

2 5 32

5 3 32

6 2 29 - ребро из вершины 6 в вершину 2 имеет вес 29

Таким образом - мы задали ориентированный граф в виде списка. Графическое представление этого графа выглядит следующим образом:



36

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

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

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

Вершины задаются в самом тексте программы, и при необходимости - их можно изменить.

Результаты работы программы (диалог с пользователем):

Введите начальную вершину: 1

Введите конечную вершину: 4

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

Алгоритм Дейкстры

Количество вершин: 6

Матрица смежности. (oo означает бесконечность):

oo 41 oo oo oo 29

oo oo 51 oo 32 oo

oo oo oo 50 oo oo

45 oo oo oo oo 38

oo oo 32 36 oo oo

oo 29 oo oo 21 oo

Кратчайший путь из 1-ой вершины в 4-ую вершину: 1 6 5 4

Длина пути = 86

Для выхода нажмите любую клавишу

Листинг программы:

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

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

{ Алгоритм Дейкстры }

{ Матрица смежности }

Uses tpcrt;

const

maxn = 100; { максимальное кол-во вершин }

oo = maxint div 2; { бесконечность }

var

a: array [1..maxn, 1..maxn] of integer; { матрица смежности }

d: array [1..maxn] of longint; { кратчайшие пути }

p: array [1..maxn] of integer; { дерево кратчайших путей (SPT) }

v: array [1..maxn] of boolean; { использована ли вершина }

n: longint; { кол-во вершин }

start, finish: integer;

{ init: инициализация и чтение данных }

procedure init;

var

i, j, x, y, nn, z: longint;

begin

for i := 1 to maxn do { граф без ребер }

for j := 1 to maxn do

a[i, j] := oo;

fillchar(d, sizeof(d), 0);

fillchar(p, sizeof(p), 0);

fillchar(v, sizeof(v), false); { вершины не использованы }

{ чтение данных }

assign(input, 'dijkstra.in');

{ assign(input, 'randw.in');}

reset(input);

read(n);

read(nn);

for i := 1 to nn do

begin

read(x, y, z);

a[x, y] := z;

{если граф ориентированный - то следующая строка должна быть отключена.

Если неориентированный - то включена.}

{ a[y, x] := z; }

end;

end;

{ print: печать матрицы cмежности }

procedure print;

var

i, j: integer;

begin

writeln;

writeln('Количество вершин: ', n);

writeln('Матрица смежности. (oo означает бесконечность): ');

for i := 1 to n do

begin

for j := 1 to n do

if a[i, j] = oo then

write('oo':3)

else

write(a[i, j]:3);

writeln;

end;

end;

{ dijkstra: алгоритм Дейкстры }

procedure dijkstra(s: integer);

var

i, j, min, m: integer;

begin

for i := 1 to n do { для всех вершин }

begin

d[i] := a[s, i]; { расстояние от истока }

p[i] := s; { предок исток }

end;

d[s] := 0; { расстояние до истока }

p[s] := 0; { у истока нет предков в (SPT) }

v[s] := true; { источник использован }

for i := 2 to n do { для всех вершин кроме истока }

begin

min := oo; { Найдем вершину m с минимальным }

for j := 1 to n do { расстоянием до истока }

if not v[j] and (d[j] < min) then

begin

min := d[j];

m := j;

end;

v[m] := true; { вершина m использована }

for j := 1 to n do { для всех вершин }

if not v[j] and { Если вершина не использована и }

(d[j] > d[m]+a[m, j]) then { через m можно дойти до j быстрее }

begin

d[j] := d[m] + a[m, j]; { уменьшаем расстояние от истока }

p[j] := m; { изменяем предка j }

end;

end;

end;

{write_path: пишет кратчайший путь из s в x }

procedure write_path(s, x: integer);

begin

if x <> s then

write_path(s, p[x]);

write(x, ' ');

end;

begin

clrscr;

Write('Введите начальную вершину: '); ReadLn(start);

Write('Введите конечную вершину: '); ReadLn(finish);

init;

writeln;

writeln('Кратчайшие пути из одного истока в сетях с неотрицательными весами ребер');

writeln('Алгоритм Дейкстры');

print;

write('Кратчайший путь из ', start, '-ой вершины в ', finish, '-ую вершину: ');

dijkstra(start);

write_path(start, finish);

WriteLn;

WriteLn('Длина пути = ', d[finish]);

WriteLn;

WriteLn;

WriteLn('Для выхода нажмите любую клавишу');

ReadKey;

end.

ЛИТЕРАТУРА

1. Кузнецов А.В., Сакович В.А., Холод Н.И. ”Высшая математика. Математическое программирование ”, Минск, Вышейшая школа, 2001г.

2. Красс М.С., Чупрынов Б.П. ”Основы математики и ее приложения в экономическом образовании”, Издательство “Дело”, Москва 2001г.

3. В.И. Ермаков “Общий курс высшей математики для экономистов”, Москва, Инфра-М, 2000г.

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

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

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

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

8. Нефедов В.Н., Осипова В.А. Курс дискретной математики. - М.: Издательство МАИ, 1992.

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

10. Исмагилов Р.С., Калинкин А.В. Матеpиалы к пpактическим занятиям по куpсу: Дискpетная математика по теме: Алгоpитмы на гpафах. - М.: МГТУ, 1995

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

12. Hечепуpенко М.И. Алгоpитмы и пpогpаммы pешения задач на гpафах и сетях. - Hовосибиpск: Hаука, 1990

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

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

15. Бентли Д. Жемчужины творчества программистов: Пер. с англ. -- М.: Радио и связь, 1990. -- 224 c.: ил.

16. Фундаментальные алгоритмы на C++. Алгоритмы на графах. Роберт Седжвик. СПб: ООО “ДиаСофтЮП”, 2002 год.

17. Фундаментальные алгоритмы на C++. Анализ. Структуры данных. Сортировка. Поиск. Роберт Седжвик. СПб: ООО “ДиаСофтЮП”, 2002 год.