Размещено на http://www. аllbest.ru/

Размещено на http://www. аllbest.ru/

Содержание

• Введение
• 1. Основы теории графов
• 2. Алгоритмическая часть
• 2.1 Применение поставленнай задачи
• 2.2 Алгоритм нахождения критического пути в орграфе
• 3. Описание программы
• 3.1 Общие сведения
• 3.2 Функциональное назначение
• 3.3 Описание логической структуры программы
• 3.4 Описание данных
• 3.5 Руководство пользователю
• 3.6 Контрольный пример
• Заключение
• Список использованной литературы
• Приложение. Листинг программы
• алгоритм матрица ациклический граф

Введение

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

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

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

1. Основы теории графов

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

Рисунок 1.1

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

Графом называется алгебраическая система G = (М, R), где R - двухместный предикатный символ. Элементы носителя М называются вершинами графа G, а элементы бинарного отноше-ния R М² - дугами. Таким образом, дугами являются пары вершин (a, b) R. При этом дуга (a, b) называется исходящей из вершины а и заходящей в вершину b.

Изображение графа G = (М, R) получается путем расположения различных точек на плоскости для каждой вершины a М, причем если (а, b)  R, то проводится стрелка (дуга) из вершины а к вершине b.

Пример: Изображение графа G с множеством вершин М

{1,2,3,4} и множеством дуг R = {(1,1), (1,2), (2,3),(3, 4), (4,3), (4,1)} представлено на рисунке 1.1.

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

Рисунок 1.2.

Мулътиграфом G называется тройка (М, U, P), в которой М - множество вершин, U - множество дуг, а Р МUМ - трехместный предикат, называемый инцидентором и представляемый следующим образом: (a, u, b) P тогда и только тогда, когда дуга и исходит из вершины а и заходит в вершину b. Отметим, что любой граф можно представить в виде мультиграфа.

Граф G = (M, R) называется ориентированным (орграфом), если найдется дуга (а, b) R такая, что (b, а) R. Если же отношение R симметрично, т. е. из (а, b) R следует (b, а) R, то граф G называется неориентированным (неорграфом). Если одновременно пары (а, b) и (b, а) принадлежат R (рисунок 1.3, а), то информацию об этих дугах можно представить множеством [а, b] = {(а, b), (b, а)}, называемым ребром, которое соединяет вершины а и b. При этом вершины а и b называются концами ребра [а, b]. Ребра изображаются линиями (без стрелок), соединяющими вершины (рисунок 1.3, б).

Рисунок 1.3.

Если в мультиграфе вместо дуг рассматриваются ребра, то мультиграф также называется неориентированным. Отметим, что если в орграфе G = (М, R) к каждой дуге (а, b) R добавить пару (b, а), то в результате образуется неорграф, который будем называть соответствующим данному орграфу G и обозначать через F(G).

Пример: Орграфу G, изображенному на рисунке 1.1, соответствует неорграф F(G), изображенный на рисунке 1.4.

Рисунок. 1.4.

Информация о структуре графа может быть задана матрицей бинарного отношения. Пусть G = (М, R) - граф, в котором множество вершин имеет n элементов: М = {a₁, a₁, …, a_n}. Матрицей смежности А_G = (A_ij) графа G называется матрица порядка n, определенная следующим образом:

Если А_ij = 1, то вершина а_j называется последователем вершины а_i, а а_i - предшественником а_j. Вершины а_i и а_j называются смежными, если A_ij = 1 или A_ji = 1.

Если G - мультиграф, то в матрице смежности A_G элемент А_ij по определению равен числу дуг, исходящих из вершины а_i и заходящих в вершину а_j (i, j {1, ..., n}).

Рисунок 1.5.

Граф G, изображенный на рисунке 1.1.5, имеет матрицу смежности

Отметим, что если G - неорграф, то матрица смежности A_G симметрична, т. е. не меняется при транспонировании: .

Петлей в графе G называется дуга, соединяющая вершину саму с собой. Если G - граф без петель, то в матрице смежности A_G по главной диагонали стоят нулевые элементы:

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

Согласно этой теореме по матрице смежности граф восста-навливается однозначно с точностью до изоморфизма.

В графе G = (М, U, Р) дуга u U называется инци-дентной вершине а М, если (а, u, b) Р или (b, u, а) Р для некоторого b М. Если М = {a₁, ..., a_m}, U = {u₁, ..., u_n}, то матрицей инцидентности B_G = (В_ij) мультиграфа G на-зывается матрица размера m*n, определяемая по следующему правилу:

Рисунок. 1.6.

Пример: Мультиграф G, изображенный на рисунке 1.6, имеет матрицу инцидентности

Мультиграфы G = (M, U, P) и G' = (M', U', P') называ-ются изоморфными, если существуют биекции : М М' и : U U' такие, что (a, u, b) Р тогда и только тогда, когда ((a), (u), (b)) P'.

Аналогично теореме 1 справедлива

Теорема 2. Мультиграфы G и G' изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга некоторыми перестановками строк и столбцов.

Пути и маршруты

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

Так, на рис. 1.6 последовательности дуг

а₆ а₅ а₉ a₈ а₄ (1.1)

а₁ а₆ а₅ а₉ (1.2)

а₁ а₆ а₅ а₉ а₁₀ а₆ а₄ (1 3)

являются путями.

Рисунок 1.6

Дуги а = (х_i , x_j), x_i ? x_j , имеющие общие концевые вершины, называются смежными. Две вершины x_i и x_j называются смежными, если какая-нибудь из двух дуг (x_i, x_j) и (х_j), x_i) или обе одно-временно присутствуют в графе. Так, например, на рис. 1.6 дуги а₁, а₁₀, а₃ и а₆, как и вершины х₅ и х₃, являются смежными, в то время как дуги а₁ и а₅ или вершины х₅ и x₃ не являются смежными.

Ориентированной цепью (или, короче, орцепъю) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например, приведенные выше пути (1.1) и (1.2) являют-ся орцепями, а путь (1.3) не является таким, поскольку дуга а_в в нем используется дважды.

Простой орцепъю называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (1.2) является простой орцепью, а пути (1.1) и (1.3) -- нет. Очевидно, что простая орцепь является также орцепью, но обратное утвер-ждение неверно. Например, путь (1.1) является орцепью, но не простой орцепью, путь (1.2) является орцепью и простой орцепью, а путь (1.3) не является ни орцепью, ни простой орцепью. Маршрут есть неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направ- ленностью дуг в графе. Таким образом, маршрут есть последова-тельность ребер а₁, а₂,...,a_q , в которой каждое ребро a_i, за исключением, возможно, первого и последнего ребер, связано с ребрами а_i-1 и a_i+1 своими двумя концевыми вершинами. После-довательности дуг

а₂, a₄, a₈, a₁₀, (1.4)

a₂, a₇, а₈, а₄, а₃ (1.5)

a₁₀, a₇, а₄, а₈, а₇, а₂ (1.6)

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

Точно так же, как мы определили орцепи и простые орцепи, можно определить цепи и простые цепи. Так, например, маршрут (1.4) есть цепь и простая цепь, маршрут (1.5) -- цепь, но не простая цепь, а маршрут (1.6) не является ни цепью, ни простой цепью.

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

Веса и длина пути

Иногда дугам графа G сопоставляются (приписываются) чис-ла -- дуге (x_t, xj) ставится в соответствие некоторое число с,_;-, называемое весом, или длиной, или стоимостью (ценой) дуги. Тогда граф G называется графом со взвешенными дугами. Иногда веса (числа у,) приписываются вершинам x_t графа, и тогда полу-чается граф со взвешенными вершинами. Если в графе веса при-писаны и дугам, и вершинам, то он называется просто взвешен-ным.

При рассмотрении пути м, представленного последовательно-стью дуг (а_х, а₂, . . ., a_q), за его вес (или длину, или стоимость) принимается число I(м), равное сумме весов всех дуг, входящих в м, т. е.

Таким образом, когда слова «длина», «стоимость», «цена» и «вес» применяются к дугам, то они эквивалентны по содержанию, и в каждом конкретном случае выбирается такое слово, которое

Рисунок 1.3

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

Петли, ориентированные циклы и циклы

Петлей называется дуга, начальная и конечная вершины кото-рой совпадают. На рис. 1.7, например, дуги а₂ и а₅ являются пет-лями.

Путь а₁, а₂, ... , a_q называется замкнутым, если в нем начальная вершина дуги а₁ совпадает с конечной вершиной дуги а_q. Так, например, в графе, приведенном на рис. 1.7, последова-тельности дуг

а₃ ,а₆, а₁₁, (1.7)

а₁₁ , а₃, а₄, а₇, а_i, а₁₂, а₉, (1.8)

а₃, а₄, а₇, а₁₀, а₉, а₁₁, (1.9)

являются замкнутыми путями.

Пути (1.7) и (1.9) являются замкнутыми простыми орцепями (контурами, или простыми орциклами), поскольку в них одна и та же вершина используется только один раз (за исключением начальной и конечной вершин, которые совпадают), а путь (1.8) не является контуром, так как вершина х₁ используется в нем дважды. Контур, проходящий через все вершины графа, имеет особое значение и называется гамилътоновым контуром. Конеч-но, не все графы обладают гамильтоновыми контурами. Так, например, контур (1.9) является гамильтоновым контуром графа, приведенного на рис. 1.7, а граф на рис. 1.6 не имеет гамильтоно-вых контуров, поскольку не существует такой дуги, для которой х₁ была бы конечной вершиной.

Замкнутый маршрут является неориентированным двойником замкнутого пути. Таким образом, замкнутый маршрут является маршрутом х₁, х₂, ... , x_q, в котором совпадают начальная и конечная вершины, т. е. в котором х_х = x_q.

На рис. 1.7 маршруты

a₁, а₁₂, а₁₀, (1.10)

а₁₀, а₁, а₃, а₄, а₇, а₁, а₁₂ (1.11)

являются замкнутыми маршрутами.

2. Алгоритмическая часть

2.1 Применение поставленной задачи

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

Допустим, что нужно реализовать некий большой проект, и этот проект состоит из большого числа этапов. Мы можем изобра-зить каждый этап вершиной некоторого графа и построить дугу от вершины x_i к вершине x_j, чтобы показать, что этап i должен предшествовать этапу j. Каждой дуге приписывается некоторый вес c_ij, равный минимальной задержке во времени между началом этапа i и началом этапа j. Пусть, например, проект представляет собой процесс строительства здания. Этап i может состоять в строительстве стен, этап j - вставка окон, этап к - прокладка про-водов в стенах и т. д. Очевидно, что в этом случае нужно провести дуги от х_i- к x_j и от x_j к х_к. Но минимальный срок между началом строительства стен и вставкой окон может быть отличным от срока между строительством стен и прокладкой проводов. Если, напри-мер, оконные рамы деревянные и стены должны сначала высох-нуть, а для прокладки проводов это не важно,

то c_ij > c_ik.

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

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

Сходство этой задачи с задачей о кратчайшем пути между s и t совершенно очевидно и ее можно решить, используя алгоритм приведённый ниже.

2.2 Алгоритм нахождения критического пути в ациклическом орграфе

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

Присвоим вершине x_j пометку l(x_j),-- равную длине самого длинного пути от 1 до x_j, используя для этого соотношения

l(x_j) = max [l(x_i) + c_ij]; (*)

Затем присвоим пометку вершине (x_j+ 1), применив снова формулу (8.7), и так далее до тех пор, пока последняя вершина п не получит пометку l(п). В соотношении (*) l(1) полагается равным нулю. Если вершина х_j помечена, то пометки I(x_t) извест-ны для всех вершин x_t Г^-1 (x_j), так как в соответствии со спо-собом нумерации это означает, что x_i < x_j и, следовательно, вер-шины x_i уже помечены в процессе применения алгоритма.

Пометка l(n) равна длине самого длинного пути от 1 до n. Сами дуги, образующие путь, могут быть найдены обычным спо-собом последовательного возвращения. А именно дуга (x_i, x_j) принадлежит пути тогда и только тогда, когда l(x_j) = I (x_i) + c_ij. Начиная с вершины x_j равной n, полагаем на каждом шаге x_j равной такой вершине x_t (скажем, х_i*), для которой выполняется это последнее равенство, и так продолжаем до тех пор, пока не бу-дет достигнута начальная вершина (т. е. пока не будет х_i* = 1).

Совершенно очевидно, что пометка l (x_j) вершины x_j дает длиннейший путь от 1 до х_j, т. е. самое раннее возможное начало выполнения этапа, изображаемого вершиной x_j. Таким образом, если (х_i, x_j) -- дуга в графе, то I(x_i ) -- I(x_j) -- c_ij (неотрицатель-ная величина, как это видно из (*)) дает самое большое возмож-ное время задержки начала этапа i, не оказывающее влияния на время начала этапа j. Из вышесказанного видно, что если i и j -- два последовательные этапа в самом длинном пути, то I (х_i) - I (x_j) - c_ij = 0.

3 Описание программы

3.1 Общие сведения

Программа написана на языке Turbo Pascal версии 7.0 Отладка производилась в операционной системе MS Windows ХР с процессором Athlon.

3.2 Функциональное назначение

Программа предназначена для определения критического пути в ациклическом ориентированном графе. Максимальное число вершин обрабатываемого графа может быть не более 30.

Ввод матрицы смежности графа целесообразно задавать в отдельном файле.

3.3 Описание логической структуры программы

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

kurs.exe - главный файл проекта;

graf.txt - текстовый файл, содержащий входные данные (количество вершин графа и матрицу смежности).

Константы:

n0 = 30 - максимальное число вершин обрабатываемого графа.

Переменные:

n - количество вершин в заданном графе;

n - количество вершин в заданном графе;

ves - матрица весов заданного графа;

l - матрица рабочих меток заданного графа;

m - массив для записи пути;

q - вспомогательная переменная;

fl - вспомогательная переменная;

k - количество сильных компонент;

i, j, k, - счетчики.

Процедуры:

Procedure krit - отыскание критического пути в графе.

3.4 Описание входных данных

Входные данные программы:

На первой строке файла с входными данными задано количество вершин графа (n: integer). На последующих строках задана матрица весов графа с соответствующим количеством элементов (n*n), расположенных через разделитель (пробел или конец строки).

3.5 Руководство пользователю

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

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

3.6 Контрольный пример

Задан ацикличекий ориентированный граф - G(рис. 2.1). Найти критичечкий путь .

Рисунок 2.1

Результат работы программы:

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



Рисунок 2.2

Заключение

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

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

интегрирование модуля программы в другие более сложные.

Программа может работать на компьютере не хуже Pentium с операционной системой Windows 9x или с ней совместимой.

Кроме практических результатов при выполнении курсовой работы был изучен теоретический материал по основам теории графов.

Список использованной литературы

1. Белецкая С.Ю. Комбинаторика. Графы. Алгоритмы. Учебное пособие. Воронеж. гос. тех. ун-т, 2003.103с.

2. Кристофидес Н. Теория графов. Алгоритмический подход. - М.: Мир, 1978, -432 с.

3. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0 - М.:ВЕК+, 2000, - 464 с.:ил.

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

program prog;

uses

SysUtils;

const

n0 = 30;

var

ves : array [1..n0, 1..n0] of integer;

L : array [1..n0, 1..n0] of integer;

M : array [1..n0] of integer;

i,j,fl,n,q, max: integer;

f:text;

Procedure krit;

var k:integer;

begin Max:=0;

for k:=1 to n do

begin

if l[k,i] <> 0 then

begin fl:=fl+1;

if MAX < l[k,i] then

begin

MAX:=l[k,i];

m[i]:=k;

end;

end;

end;

End;

begin

assign(f,'graf.txt');

reset(f);

readln(f,n);

for i:=1 to n do

for j:=1 to n do read(f, ves[i,j]);

close(f);

writeln;

writeln('Matrica vesov zadannogo grafa');

for i:=1 to n do

begin

for j:=1 to n do write (ves[i,j],' ');

writeln;

end;

writeln;

for i:= 1 to n do

begin

for j:= 1 to n do

l[i,j]:=0;

M[i]:= 0;

end;

fl:=0;

for j:= 1 to n do begin

for i:= 1 to n do

begin krit;

if ves[i,j]<>0 then l[i,j]:= ves[i,j] + max;

fl:=0; end

end;

Writeln;

writeln('L');

for i:=1 to n do begin

for j:=1 to n do write(l[i,j],' ');

writeln;

end;

q:=0;

writeln;

writeln ('Kriticheskii put v zadannom grafe:');

write (n,' ');

i:=n;

repeat

write (m[i],' ');

i:=m[i];

until m[i]=0;

writeln;

q:=0;

for j:=1 to n do begin

if q < l[j,n] then q:= l[j,n];

end;

writeln;

Writeln('Dlina kriticheskogo puti = ',q,'.');

readln;

end.

Размещено на аllbest.ru