Добавлен: 06.05.2024
Просмотров: 59
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
T.
Последовательность определения сильных компонент.
1. Построение матриц достижимости R и контрдостижимости
.
2. Определение матриц
.
3. Выделение сильных компонент графа. Вершины, соответствующие одинаковым строкам и столбцам матрицы S, принадлежат одной сильной компоненте графа.
Программа написана на языке Turbo Pascal версии 7.0 Отладка производилась в операционной системе MS Windows 95 на компьютере совместимом с IBM PC с процессором 80486 DX4.
Программа предназначена для определения сильных компонент ориентированного графа. Максимальное число вершин обрабатываемого графа может быть не более 15. Ввод матрицы графа осуществляется из текстового файла с именем STRONG. Вывод результатов расчета производится на экран.
Константы.
Nmax = 15 - максимальное число вершин обрабатываемого графа.
Типы:
Link = ^PLink - тип - список.
PLink = record - тип запись с полями:
sled - ссылочное поле - связь со следующим элементом.
P - признак наличия пути: 1 - есть, 0 - нет.
Mat2 - двумерный массив максимальной размерностью 15 * 15 состоящий из 0 и 1.
Mas1 - одномерный массив максимальной размерностью 15 с элементами от 0 до 15.
MasMno - массив максимальной размерностью 15 с элементами типа множество 1..15.
Переменные (основные).
G - матрица смежности исходного графа;
R - матрица достижимости;
Q - матрица контрдостижимости;
C - произведение Адамара;
C1 - матрица С, приведенная к блочно - диагональному виду.
SetOfStr - массив множества сильных компонент;
Описание процедур
1) Процедура Dostig
Составление матрицы достижимости графа.
2) Процедура BDG
Формирует блочно - диагональную матрицу.
3) Процедура Silnie
Нахождение сильных компонент графа.
Для использования программы необходимы следующие условия:
Требования к компьютеру. Для нормальной работы программы требуется любой IBM - совместимый компьютер с процессором 80386 или выше с минимальной конфигурацией: оперативная память не менее 1024 Кбайт, размер свободного дискового пространства не менее 50 Кбайт для размещения основной программы, цветной графический монитор EGA, VGA, SVGA.
Программное обеспечение. Разработка и отладка программы производилась с использованием интегрированной среды Turbo Pascal 7.0.
Программа может работать в операционной системе MS-DOS не ниже пятой версии.
Входные данные:
матрица смежности графа, расположенная в текстовом файле с именем STRONG. Каждая строка этого файла представляет собой набор из 0 и 1, разделенных одним пробелом.
число вершин графа – определяется программно при считывании матрицы смежности.
Выходные данные:
количество сильных компонент графа;
список вершин для каждой компоненты.
Запуск программы производится выбором из панели Norton Commander файла с именем SILNYE.EXE и нажатия клавиши Enter.
После этого работа с программой производится без вмешательства пользователя в следующей последовательности:
- чтение данных их текстового файла с именем STRONG;
- преобразование списка и формированием матрицы смежности графа;
- формирование матриц достижимости, контрдостижимости и произведения Адамара;
- приведение матрицы Адамара к блочно - диагональному виду;
- поиск сильных компонент графа;
- вывод решения.
Начало
Чтение данных из файла
Вывод матрицы смежности
Формирование матрицы достижимости Dostig и расчет произведения Адамара
Приведение к блочно – диагональному виду BDV
Поиск сильных компонент Silnie
Вывод сильных компонент
Конец
Главным итогом выполнения курсовой работы было создание программы определения сильных компонент ориентированного графа в соответствии с поставленной задачей и получение практических результатов работы программы. Созданная программа позволяет:
- ввод размерности исходной матрицы смежности графа из файла;
- формировать решение в соответствии с условием поставленной задачи;
- вывод на экран исходного графа и полученных компонент.
Созданная программа полностью удовлетворяет поставленной задаче, но при этом имеет ряд недостатков:
- нет вывода на печать результатов расчета;
- нет контроля правильности вводимых данных;
- ограниченная размерность графа.
Доработка указанных недостатков позволит сделать программу более универсальной и надежной.
1. Бондарев В.М. Основы программирования. Харьков: Фолио, 1997, 367 с.
2. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. -М.: Наука, 1990, 384 с.
3. Нефедов В.Н., Осипова В.А. Курс дискретной математики / Учебное пособие. -М:. МАИ, 1992 г. -264 с.
4. Фаронов В.В. Программирование на персональных ЭВМ в среде ТУРБО - ПАСКАЛЬ. -М., изд - во МГТУ, -1991, -580 с.
5. Фаронов В.В. Turbo Pascal 7.0. Начальный курс. -М.: Нолидж, -1997, 616 с.
Последовательность определения сильных компонент.
1. Построение матриц достижимости R и контрдостижимости
. 2. Определение матриц
. 3. Выделение сильных компонент графа. Вершины, соответствующие одинаковым строкам и столбцам матрицы S, принадлежат одной сильной компоненте графа.
3. Описание программы
3.1. Общие сведения
Программа написана на языке Turbo Pascal версии 7.0 Отладка производилась в операционной системе MS Windows 95 на компьютере совместимом с IBM PC с процессором 80486 DX4.
3.2. Функциональное назначение
Программа предназначена для определения сильных компонент ориентированного графа. Максимальное число вершин обрабатываемого графа может быть не более 15. Ввод матрицы графа осуществляется из текстового файла с именем STRONG. Вывод результатов расчета производится на экран.
3.3. Описание логической структуры программы
Константы.
Nmax = 15 - максимальное число вершин обрабатываемого графа.
Типы:
Link = ^PLink - тип - список.
PLink = record - тип запись с полями:
sled - ссылочное поле - связь со следующим элементом.
P - признак наличия пути: 1 - есть, 0 - нет.
Mat2 - двумерный массив максимальной размерностью 15 * 15 состоящий из 0 и 1.
Mas1 - одномерный массив максимальной размерностью 15 с элементами от 0 до 15.
MasMno - массив максимальной размерностью 15 с элементами типа множество 1..15.
Переменные (основные).
G - матрица смежности исходного графа;
R - матрица достижимости;
Q - матрица контрдостижимости;
C - произведение Адамара;
C1 - матрица С, приведенная к блочно - диагональному виду.
SetOfStr - массив множества сильных компонент;
Описание процедур
1) Процедура Dostig
Составление матрицы достижимости графа.
2) Процедура BDG
Формирует блочно - диагональную матрицу.
3) Процедура Silnie
Нахождение сильных компонент графа.
3.4. Использование технических средств
Для использования программы необходимы следующие условия:
Требования к компьютеру. Для нормальной работы программы требуется любой IBM - совместимый компьютер с процессором 80386 или выше с минимальной конфигурацией: оперативная память не менее 1024 Кбайт, размер свободного дискового пространства не менее 50 Кбайт для размещения основной программы, цветной графический монитор EGA, VGA, SVGA.
Программное обеспечение. Разработка и отладка программы производилась с использованием интегрированной среды Turbo Pascal 7.0.
Программа может работать в операционной системе MS-DOS не ниже пятой версии.
3.5. Описание данных
Входные данные:
матрица смежности графа, расположенная в текстовом файле с именем STRONG. Каждая строка этого файла представляет собой набор из 0 и 1, разделенных одним пробелом.
число вершин графа – определяется программно при считывании матрицы смежности.
Выходные данные:
количество сильных компонент графа;
список вершин для каждой компоненты.
3.6. Руководство пользователю
Запуск программы производится выбором из панели Norton Commander файла с именем SILNYE.EXE и нажатия клавиши Enter.
После этого работа с программой производится без вмешательства пользователя в следующей последовательности:
- чтение данных их текстового файла с именем STRONG;
- преобразование списка и формированием матрицы смежности графа;
- формирование матриц достижимости, контрдостижимости и произведения Адамара;
- приведение матрицы Адамара к блочно - диагональному виду;
- поиск сильных компонент графа;
- вывод решения.
3.7. Структурная схема программы
Начало
Чтение данных из файла
Вывод матрицы смежности
Формирование матрицы достижимости Dostig и расчет произведения Адамара
Приведение к блочно – диагональному виду BDV
Поиск сильных компонент Silnie
Вывод сильных компонент
Конец
Заключение
Главным итогом выполнения курсовой работы было создание программы определения сильных компонент ориентированного графа в соответствии с поставленной задачей и получение практических результатов работы программы. Созданная программа позволяет:
- ввод размерности исходной матрицы смежности графа из файла;
- формировать решение в соответствии с условием поставленной задачи;
- вывод на экран исходного графа и полученных компонент.
Созданная программа полностью удовлетворяет поставленной задаче, но при этом имеет ряд недостатков:
- нет вывода на печать результатов расчета;
- нет контроля правильности вводимых данных;
- ограниченная размерность графа.
Доработка указанных недостатков позволит сделать программу более универсальной и надежной.
Список литературы
1. Бондарев В.М. Основы программирования. Харьков: Фолио, 1997, 367 с.
2. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. -М.: Наука, 1990, 384 с.
3. Нефедов В.Н., Осипова В.А. Курс дискретной математики / Учебное пособие. -М:. МАИ, 1992 г. -264 с.
4. Фаронов В.В. Программирование на персональных ЭВМ в среде ТУРБО - ПАСКАЛЬ. -М., изд - во МГТУ, -1991, -580 с.
5. Фаронов В.В. Turbo Pascal 7.0. Начальный курс. -М.: Нолидж, -1997, 616 с.