Реализация основных операций над графами, представленных в виде матриц смежностей

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

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

Пензенский государственный педагогический университет им. В. Г. Белинского

Кафедра прикладной математики и информатики

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

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

на тему: «Реализация основных операций над графами, представленных в виде матриц смежностей»

Автор:	Бабаджанов Б. Ю.
Специальность:	Математическое обеспечение и администрирование информационных систем.
Группа:	МП-21.
Курс:	2
Руководитель:	Тобольченко В.М.

ПЕНЗА 2010

Задания.

Реализовать представление графа с помощью матрицы смежности. Реализовать основные операции над графами (дополнение графа, объединение графов, добавление ребра в граф, удаление вершины из графа, удаление ребра из графа, добавление вершины в граф).

Реферат

Пояснительная записка содержит 30 листов, 7 рисунков, 2 таблиц, 3 приложений на 12 листах.

Дискретная Математика, ИНФОРМАТИКА, ПРОГРАММИРОВАНИЕ,ООП, С++, ГРАФ, ОПЕРЦИИ НАД ГРАФАМИ, дополнение графа, объединение графов, соединение графов, добавление ребра в граф, стягивание подграфа, удаление вершины из графа, удаление ребра из графа, добавление вершины в граф.

В работе реализован граф виде матрицы смежности на языке программирование С++. Написан код для вычисление основных операций над графами.

Содержание .

Задания. - 2 -

Реферат.. - 3 -

Содержание. - 4 -

Введение.. - 5 -

1 Разработка программы для реализации графа. - 6 -

1.1 Анализ математических требований. - 8 -

1.2 Кодирование. - 18 -

1.3 Тестирование. - 19 -

Заключение. - 21 -

ПРИЛОЖЕНИЕ А. - 22 -

ПРИЛОЖЕНИЕ Б. - 23 -

ПРИЛОЖЕНИЕ В. - 28 -

Список литературы: - 32 -

Введение

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

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.

В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Теория графов рассматривается как одна из ветвей топологии; непосредственное отношение она имеет также к алгебре и к теории чисел. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач, нахождении максимального потока в сети, кратчайшего расстояния, максимального паросочетания, проверки планарности графа и др. Как особый класс можно выделить задачи оптимизации на графах. Математические развлечения и головоломки тоже являются частью теории графов, например, знаменитая проблема четырех красок, интригующая математиков и по сей день. Теория графов быстро развивается, находит все новые приложения и ждет молодых исследователей.

1 Разработка программы для реализации графа.

Приведенные ниже этапы создания программы.

I этап. Создание любой программы начинается с постановки задачи или анализа требования. Изначально задача поставлена в терминах предметной области, и приведена в термины, более близкие к программированию.

В ходе работе:

• описаны исходные данные и результаты (типы, форматы, точность, способ передачи, ограничения);

• описаны задачи, реализуемой программой;

• способ обращения к программе;

• описаны возможные аварийные ситуации и ошибки пользователя.

Таким образом, функции, входные и выходные данные.

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

III этап. Кодирование. Процесс программирования также организовался по принципу «сверху вниз»: вначале ко

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать