Поиск критического пути в ориентированном ациклическом графе

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

4

Министерство образования Российской Федерации

ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Естественно - гуманитарный факультет

Кафедра САПРиС

Информационные системы и технологии

КУРСОВАЯ РАБОТА

По дисциплине: «Дискретная математика»

Тема: «Поиск критического пути в ациклическом ориентированном графе»

Выполнил: Сухочев А. Е.

Проверил: Белецкая С.Ю.

Воронеж 2007

Содержание

Введение

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

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

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

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

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

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

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

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

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

Заключение

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

Введение

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

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

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

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

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

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

Рисунок 1.1

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

Графом называется алгебраическая система G = (М, R), где R - двухместный предикатный символ. Элементы носителя М называются вершинами графа G, а элементы бинарного отношения R М2 - дугами. Таким образом, дугами являются пары вершин (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 элементов: М = {a1, a1, …, an}. Матрицей смежности АG = (Aij) графа G называется матрица порядка n, определенная следующим образом:



Если Аij = 1, то вершина аj называется последователем вершины аi, а аi - предшественником аj. Вершины аi и аj называются смежными, если Aij = 1 или Aji = 1.

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

Рисунок 1.5

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

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

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

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

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

В графе G = (М, U, Р) дуга u U называется инцидентной вершине а М, если (а, u, b) Р или (b, u, а) Р для некоторого b М. Если М = {a1, ..., am}, U = {u1, ..., un}, то матрицей инцидентности BG = (В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' изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга некоторыми перестановками строк и столбцов.

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

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

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

Так на рисунке 2.1 а) б) представлены несвязный и связный неорграфы, а на рисунке 2.1в) - сильносвязный орграф. Орграф на рисунке 2.1г) односторонне связный, так как его вершины x1 и x5 не являются взаимно достижимыми. Орграф на рисунке 2.1д) слабо связный и не является ни сильно, ни односторонне связным, так как вершина x1 не достижима из вершины x3, а вершина x3 из x1.

Рисунок 2.1

{дальше в этом пункте своя теория, пример решения из методы}

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

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

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

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

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

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

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

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

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

Вывод данных происходит на экран

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

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

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

alg.tpu - вычислительный модуль;

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

Модуль Alg.tpu

Модуль состоит из шести процедур, четыре из которых доступны пользователю: Smejnost, Svyaznost, Siln_Komponent, BAZ_AND_ABAZ;

Константы:

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

Типы:

TM - одномерный целочисленный массив максимальной размерностью N0 с элементами от 1 до n0.

TTM - двумерный целочисленный массив максимальной размерностью n0*n0.

Переменные:

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

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

R - матрица достижимости;

Q - матрица контрдостижимости;

S - матрица сильной связности;

SK - матрица сильносвязных компонент;

KG - конденсация графа;

BAZ - базы графа;

ABAZ - антибазы графа;

ws - вспомогательная переменная, двумерный массив TTM;

str - вспомогательная переменная, одномерный массив TM:

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

i, j, l, g - счетчики.

Процедуры:

Procedure Smejnost - Заполнение матрицы смежности из указанного пользователем файла.

Procedure Svyaznost - Построение матрицы достижимости по матрице смежности, а также контрдостижимости и связности графа.

Procedure Siln_Komponent - Поиск сильных компонент.

Procedure BAZ_AND_ABAZ - Построение конденсации графа, поиск баз и антибаз заданного графа.

Procedure Poisk(var m: TTM) - Выполняет посик следующего элемента базы или интибазы. Вызывается процедурой BAZ_AND_ABAZ.

Procedure Vivod(x:integer) - Процедура рекурсия. Завершает поиск следующего элемента базы или антибазы. Вызывается процедурой Poisk.

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

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

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

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

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

После запуска программы появится окно с сообщением: «Введите имя файла с исходными данными». Путь к файлу может быть указан как абсолютный, так и относительный, при этом необходимо указать расширение файла (*.txt). Если на этом этапе будет обнаружена ошибка (файла не существует на диске или путь к файлу указан не верно), то появится сообщение: «Файл не найден» и выполнение программы прекратиться. Если же ошибок обнаружено не будет, то пользователь увидит результат работы алгоритма. При этом после выполнения каждого блока программы пользователю будет предложено продолжить выполнение алгоритма: «Для продолжения нажмите Enter». По окончании прогона программы пользователь будет предупрежден сообщением: «Поиск окончен. Для выхода из программы нажмите Enter».

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

Задан граф G. Найти сильные компоненты, базу и антибазу.

Решение, полученное программой:



Результат прогона программы нетрудно проверить, построив конденсацию графа G.

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

Заключение

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

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

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

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

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

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

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

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

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

3. Попов В. Б. Turbo Pascal для школьников: Учебное пособие. - 3-е доп. изд. - М.: Финансы и статистика, 2003.- 528 с.:ил.

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

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