Федеральное агентство по образованию

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

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

Кафедра саприс курсовая работа

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

Тема: «Определение сильных компонент, базы и антибазы ориентированного графа»

работу выполнил:

студентка группы ИС-063б Арепьева А. С.

Фамилия, инициалы

работу принял:

профессор Белецкая С.Ю.

ученая степень и звание фамилия, инициалы

Воронеж 2007

Замечания руководителя

Содержание

Введение 4

1.Основные определения 5

1.1 Граф. Ориентированный граф 5

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

1.3 Степени вершин..............................................................................................6

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

1.5 Матричные представления графов…………………………………………7

1.5.1 Матрица смежности…………………………………………………...7

1.5.3 Матрицы достижимости…………………………………….….……..7

1.5.3Матрица контрдостижимости…………………………………………8

1.5.4 Матрица сильной связанности………………………………………..8

1.6 Нахождение сильных компонент………………………………………..…9

1.7 База, антибаза в орграфах………………………………………………….10

2.Описание программы…... ……………………………………………………....11

2.1 Назначение программы…………………………………………………... 11

2.2 Язык программирования…………………………………………………. 11

2.3 Техническое обеспечение ………………………………………………...11

2.4 Запуск программы……………………………………………………….....12

2.5 Состав программы………………………………………………………....14

2.6 Контрольный пример ……………………………………………………..15

Заключение………………………………………………………….……..………18

Список литературы……………………………………………………………......19

Приложение. Листинг программы …………………………………………….…20

Введение

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