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

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

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

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

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

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

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

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

 
 
 
 

      ПЕНЗА 2010

      Задания.

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

      Реферат

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

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

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

      Содержание.

 

      

      Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

     Матрица смежности — один из способов представления графа в виде матрицы.

     Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица Aразмера n, в которой значение элемента aij равно числу ребёр из i-й вершины графа в j-ю вершину.

     Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента aii в этом случае равно удвоенному числу петель вокруг i-й вершины.

     Матрица смежности простого графа (не содержащего петель и кратных ребер) является бинарной матрицей и содержит нули на главной диагонали.

     Ниже  приведён пример (рис 1.) неориентированного графа и соответствующей ему матрицы смежности A. Этот граф содержит петлю вокруг вершины 1, так что, в зависимости от конкретных приложений, элемент a11 может считаться равным либо единице (как показано ниже), либо двум.

      Рисунок 1– Граф и представления графа в виде матрицы. 

     Матрица смежности полного графа Kn содержит единицы во всех своих элементах, кроме главной диагонали, на которой расположены нули.

     Матрица смежности пустого графа, не содержащего  ни одного ребра, состоит из одних  нулей.

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

     Два графа G1 и G2 с матрицами смежности A1 и A2 являются изоморфными если и только если существует перестановочная матрица P, такая что

     PA1P-1 = A2.

     Из  этого следует, что матрицы A1 и A2 подобны, а значит имеют равные наборы собственных значений, определители и характеристические многочлены. Однако обратное утверждение не всегда верно — два графа с подобными матрицами смежности могут быть неизоморфны.

     Если A — матрица смежности графа G, то матрица A^m обладает следующим свойством: элемент в i-й строке, j-м столбце равен числу путей из i-й вершины в j-ю, состоящих из ровно m ребер.

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

     Использование матрицы смежности предпочтительно  только в случае неразряженных графов, с большим числом ребёр, так как  она требует хранения по одному биту данных для каждого элемента. Если граф разрежён, то большая часть памяти напрасно будет тратиться на хранение нулей, зато в случае неразряженных графов матрица смежности достаточно компактно представляет граф в памяти, используя примерно n2 / 8 байт памяти, что может быть на порядок лучше списков смежности.