Программа формирования списка дуг ориентированного мультиграфа с петлями по заданной матрице инцидентности

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Кафедра САПР

Пояснительная записка

к курсовому проекту по дисциплине

“Алгоритмические языки и программирование”

На тему: “Программа формирования списка дуг ориентированного мультиграфа с петлями  по заданной матрице инцидентности"

Выполнил: Малышев Алексей

Группа   08Вс1

                                                                 Приняла Аксёнова Л.И.

Пенза  2009 г

Бланк задания

Ориентированный  мультиграф с петлями G=(X,U), где Х-множество вершин графа, U- множество дуг графа, задан матрицей инцидентности МI.Сформировать список дуг графа. По сформированному списку дуг определить степени исхода всех вершин графа. Упорядочит номера вершин по возрастанию значений их степеней исхода. Удалить из списка дуг все дуги, исходящие из вершины с максимальной степенью исхода и имеющий петли.

Аннотация

              В настоящей пояснительной записке приведено описание алгоритма и программы формирования списка дуг ориентированного мультиграфа с петлями, по заданной матрице инцидентности, и работы со списком дуг мультиграфа. Изложены вопросы проектирования структуры программы и данных.  Разработаны схемы алгоритмов решения задачи. Разработана и отлажена  программа, реализующая представленные алгоритмы на языке  Турбо Паскаль. Представлены результаты решения контрольных примеров, выполненные с помощью разработанной программы на ПЭВМ IBM PC Pentium, проведен анализ временной и емкостной сложности алгоритма.

Пояснительная записка содержит 21 страниц, 3 рисунка, 2 использованных источника,  приложения.

СОДЕРЖАНИЕ

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

1. 1  Общие сведения     .    .    .    .    .   6

1. 2  Функциональное назначение    .    .    .   6

1. 3  Описание логической структуры     .    .   7

1. 4  Входные и выходные данные    .    .    .   11

  1. 5 Анализ временной и емкостной сложности     11

     Заключение    .    .    .    .    .    .   .  12

     Список использованных источников   .    .  .  12

     Приложение   Результаты решения примера     

     Приложение   Текст программ    

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

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

              Программа формирования списка дуг ориентированного мультиграфа с петлями по заданной матрице инцидентности реализована на языке Turbo Pascal. Программа имеет имя Course.

              Программа содержит около 321 строк, исполняемый код программы (файл Course.exe) занимает около 27 Кбайт оперативной памяти и примерно столько же на диске.  Исходный текст программы на языке Турбо Паскаль (файл Course.pas) занимает 7 Кбайт памяти на диске.

              Для запуска программы на выполнение необходимо запустить Turbo Pascal, открыть (F3) файл Course.pas и запустить программу на выполнение (Ctrl/F9).

              При наличии файла с выполняемым кодом программы Course.exe можно запустить его на выполнение как в операционной системе MS-DOS, так и в  ОС Windows.

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

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

              Программа выполняет следующие функции:

1.      Ввод матрицы инцидентности из текстового файла и вывод её на экран.

2.      Формирование списка  дуг ориентированного графа по заданной матрице инцидентности и вывод полученного списка дуг вершин и входной матрицы инцидентности на экран.

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

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

5.      Построение рисунка графа до и после удаления дуг.

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

              При разработке программы воспользуемся модульным программированием и  структурным программированием, суть которых заключается в том, что программа разбивается на отдельные функциональные части – подпрограммы, которые распределяются по отдельным уровням иерархии. Каждая из подпрограмм решает только свою небольшую задачу по преобразованию данных, что позволяет упростить процесс написания и отладки программы в целом. Основная идея структурного программирования состоит в том, что программа любой сложности состоит из структур следования, разветвления и повторения.

              Иерархическая или структурная схема разработанной в данной работе программы приведена на рис. 1.

Обозначения в структурной схеме программы

MainProgram – главная программа.

Initgr – процедура инициализации графического режима.

Rismenu – процедура рисования кнопок меню и  вывод задания на проектирование.

Formi – ввод матрицы инцидентности из файла и вывод матрицы на экран.

Formd – процедура формирования списка дуг мультиграфа с петлями, процедура вывода списка на экран.

Stepen – процедура определения степеней вершин,  поиск вершины, имеющей максимальную степень - Vmax.

Delete – процедура удаления вершины с максимальным значением степени исхода и петлями.

Ris_graph – рисование ориентированного графа.

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

-         разработка алгоритма основной программы;

-         разработка детальных алгоритмов отдельных подпрограмм;

-         оценка разработанных алгоритмов.

Схемы алгоритмов  основной программы и процедуры формирования списка дуг по матрице инцидентности приведены на рисунках 2  и 3.

Рис. 1. Структурная схема программы

Рис. 2 Схема алгоритма основной программы

Рис. 3 Схема алгоритма формирования списка дуг по матрице инцидентности

1. 4  Входные и выходные данные   

              Входными данными служат  число вершин и дуг и матрица инцидентности ориентированного мультиграфа. Эта информация хранится в файле на диске. При вводе эти данные считываются в двумерный массив MI.

              Массив MS имеет в программе следующее описание:

              MI:array[1..10,1..20] of integer;

              Каждый из трех контрольных примеров хранится в отдельном файле. Файлы с контрольными примерами имеют имена file.pas, 11.pas, f.pas.

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

Описание типа  для динамического линейного списка     

Type

    T=^elem;

    elem=record

    natchalo,konec:integer;

    adr:T;

    end;

Var First:T;

First – переменная для хранения адреса начала динамического линейного списка в динамической области памяти.

1.          5 Анализ временной и емкостной сложности

Емкостная сложность O(v) ~ – память под глобальные массивы. В программе максимальное значение n=50, поэтому на матрицу и массив степеней  отведено: 50*100*2 байта = 15 Кбайт в ОП.

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

Formi: O(t) ~.

Formd: O(t) ~.

stepen: O(t) ~.

Delete: O(t) ~.

Ris_graph: O(t) ~ .

Суммарная оценка:

O(t) ~ .

ЗАКЛЮЧЕНИЕ

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

Разработанная программа позволяет:

-         создавать линейный динамический список дуг по матрице инцидентности;

-         определять степени  вершин и вершину, имеющую максимальную степень;

-         удалять из списка дуг, все дуги исходящие из вершины с максимальной степенью исхода;

-         выводить полученный список  на экран дисплея;

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

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Фаронов  В. В. Турбо Паскаль 7.0. Начальный курс. Учебное пособие. - М.: “Нолидж”, 1997

2. В.Э. Фигурнов  IBM для пользователя. М.: Финансы и статистика

ПРИЛОЖЕНИЕ

Решение контрольного примера

       Введите имя файла с исходными данными 11.pas

Исходные данные:

13

Матрица инцидентности: