Через некоторое количество шагов обязательно наступит момент, когда все дуги, инцидентные последней пройденной вершине, уже пройдены. Так как степени всех вершин удовлетворяют критерию, в этот моменти пройденные дуги образуют цикл, но он может включать еще не все дуги графа. Для обнаружения еще не пройденных дугпридется вернуться попройденному пути, перемещая вершины из стекав другойстек, пока не встретим вершину, которой инцидентнанепройденная дуга. Так какграф сильно связный, такаявершинаобязательно встретится. Тогда продолжаем движение понепройденнымдугам, пока не дойдем до нового тупика и т. д.Процесс заканчивается, когда в очередном тупике обнаруживается, что стек пуст. В этот момент в стекенаходится последовательность вершин эйлеровацикла. Рассмотрим пример. Для заданного ориентированного графа найти эйлеров цикл.Рис. 13. Ориентированный граф.
Проверим критерийэйлеровости орграфа,, ,, ,, ,.Критерий для всех вершин выполняется. Следовательно, можно построить эйлеров цикл. Шаг 1. Шаг 2.
Берем вершину из стека:. Имеется непройденнаядуга. Помечаем ее. Добавляем вершину в стек .Шаг 3.. В стеке есть вершины. Повторяем шаг 2.
Заполняем таблицу 1. Таблица 1. Построение циклического эйлерова пути.
Стекинепомеченные ребрапомечаем.
Продолжение таблицы 1Стекинепомеченные ребрапомечаемнетнетнетнетнет.
Продолжение таблицы 1Стекинепомеченные ребрапомечаемнетнетнетнетнетнетнетконец.
Итак, в стекенаходится последовательность вершин эйлеровацикла. Запишем его в порядке прохождения вершин,.Построение сетевого графика.
В таблице 2 приведены работы (процессы), выполняемые при строительстве каркасного дома. Разработаем сетевой график этих работ [2, 8, 11]. Таблица 2. Характеристики работ.
Процесс Предшествующий процесс.
Продолжительность АОчистка строительного участка -1BЗавоз оборудования -2CЗемляные работыA1DЗаливка фундамента C2EНаружные сантехнические работыB, C6FВозведение каркаса домаD10GПрокладка электропроводки F3HУстройство перекрытий G1IУстройство каркаса крыши F1JВнутренние сантехнические работы E, H5KПокрытие крыши I2LНаружные изоляционные работы F, J1MУстановка окон и наружных дверей F2NОблицовка дома кирпичом L, M4OШтукатурка стен и потолков G, J2PОблицовка стен и потолков O2QИзоляция крыши I, P1RОкончание внутренних отделочных работ P7SОкончание наружных отделочных работ I, N7TЛандшафтные работы S3Построим сетевую модель проекта строительства каркасного дома. На сетевом графике обозначим момент начала всего комплекса работ — вершина 0, момент окончания комплекса работ — вершина 15, моменты начала и окончания отдельных видов работ — вершины 1,…, 14; работы — дуги графа; фиктивные работы — пунктирные дуги.Рис. 14. Сетевой график строительства дома.
По сетевому графику можно определить, сколько времени потребуется для выполнения всего комплекса работ. Для этого отметим на сетевом графике продолжительности работ.Рис. 15. Сетевой график с пометками времени.
Составим таблицу временн.
Ых характеристик работ для расчета критического пути:
Таблица 3. Временные характеристики работ.
РаботаНачалоработы.
КонецработыПродолжительностьработы.
Наиболее раннее время начала работы.
Наиболее раннее время окончания работыA01101B03202C12112фиктивная23022D24224E37628F4510414G5631417фиктивная580 1414H6711718I51311415J7851823K131521517L81112324M51121416N111242428фиктивная12 130 2828O8922325P91022527фиктивная10 130 2727Q101212728R101572734S131472835T141533538.
Для восстановления критического пути пройдем по таблице в обратном порядке, выбирая максимальное значение наиболее раннего времени окончания работы. Событию 15 предшествуют события 13, 10, 14, выбираем максимальное раннее время для них: Событию 14 предшествует событие 13: И так далее:
Итак, мы дошли до исходного события 0. Критический путь протяженностью 38 ед. показан на сети двойными стрелками:
Рис. 16. Критический путь.
Выводы по главе 2 В данной главе рассмотрены примеры решения задач на ориентированных графах, а также задача, использующая ориентированный граф в качестве математической модели.
ЗАКЛЮЧЕНИЕ
Теория графов широко используется для решения прикладных задач в различных областях науки, инженерии, экономики. Достоинство моделирования с помощью состоит в том, что они достаточно наглядно представляют объекты и процессы исследования. В данной работе кратко приведены основные теоретические сведения об одном из важных классов графов — ориентированные графы. Во второй части работы приведены несколько задач на ориентированных графах, подробно описаны алгоритмы их решения. Задача поиска кратчайшего пути на орграфе может интерпретироваться по-разному и применяться в различных областях. К задачам поиска эйлеровых путей близки, задачи на отыскание путей через лабиринты, которые применяются, в частности, в современной психологии. Методы сетевого планирования напрямую связаны с экономическими и управленческими задачами. Кроме того, матричное представление графов и разработка специальных алгоритмов на графах позволяют применять компьютеры для расчетов параметров моделей, а, следовательно, и для решения прикладных задач.
ЛИТЕРАТУРА
Басакер
Р, Саати Т. Конечные графы и сети. — М.:Наука. Гл. ред. физ.-мат.
лит., 1973. — 368с. Березина Л. Ю. Графы и их применение. — М.: Просвещение, 1979. -.
143с.Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. — М.: Наука. Физматлит, 1997.
— 368с. Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука.
Гл. ред. физ.-мат.
лит., 1977. — 368с. Дистель Р.
Теория графов: Пер. с англ. — Новосибирск.: Изд-во Ин-та математики, 2002. — 336с. Кристофидес Н.Теория графов.
Алгоритмический подход. — М.: Мир, 1978. — 432с. Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. -.
М.:Наука. Гл. ред. физ.-мат.
лит., 1990. — 384с. Прикладные задачи исследования операций: Учеб.
пособие / М. Ю. Афанасьев, К. А. Багриновский, В. М. Матюшок. — М.: ИНФРА-М, 2006.
— 352с. Оре О. Графы и их применение. — М.: Мир, 1965. — 174с. Свами М., Тхуласираман К. Графы, сети и алгоритмы: пер.
с англ. — М.: Мир, 1984. — 455. Соболева Т. С. Дискретная математика: учебник для студ. вузов / Т. С. Соболева, А. В. Чечкин; под ред.
А.В.Чечкина. — М.: Издательский центр «Академия», 2006. -.
256с.Хагарти Р. Дискретная математика для программистов. — М.: Техносфера, 2003. 320с. Харари Ф. Теория графов: пер. с англ. — М.: Мир, 1984.
— 456с.
