в А и  в , т. к. G и – обыкновенные графы.

     Матрицы смежности вершин А графа  и графа , изображённых на рис. 3.1.3, имеют вид:

      ,               .

     Правильность построения матрицы можно легко проверить по рис. 3.1.3

     Объединение графов G1 и G2 , обозначаемое как G1   G2 , представляет такой граф G3 = (Х1   Х2, A1   A2), что множество его вершин является объединением Х1 и Х2 , а множество ребер – объединением A1 и A2 . ГрафG3 , полученный операцией объединения графов G1 и G2 , показан на рис. 2.2.1,д, а его матрица смежности – на рис. 2.2.1,е. Матрица смежности результирующего графа получается операцией поэлементного логического сложения матриц смежности исходных графов G1 и G2 .

     Объединение графов.

     Пусть и – произвольные графы. Объединением графов и называется граф со множеством вершин и множеством рёбер .

     Операция  объединения графов обладает следующими свойствами, которые следуют из её определения и свойств операции объединения множеств:

     для любых графов и – свойство коммутативности;

     для любых графов , и – свойство ассоциативности.

     Операция  объединения распространяется на любое  конечное число графов по индукции: .

     Операция объединения графов может быть выполнена в матричной форме.

     Теорема . Пусть  и – два графа (ориентированные или неориентированные одновременно), и пусть и – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа является матрица А, полученная поэлементным взятием максимального элемента вспомогательных матриц А1¢ и А2¢. Матрицы Аi¢, i=1,2, получаются из с помощью добавления нулевых строк и столбцов, соответствующих вершинам, отсутствующим в , но присутствующим в .

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

     Следствие. Если элементы матриц смежности вершин и графов и принимают только значения 0 и 1, то операция взятия максимального элемента для нахождения матрицы смежности вершин графа соответствует логической сумме элементов.

     Соединение  графов

     Эта операция была введена А.А. Зыковым. Пусть  и – два одновременно неориентированных или ориентированных графа с непересекающимися множествами вершин. Соединение графов состоит из и всех рёбер в случае неориентированного графа (пар нестрого параллельных дуг в случае орграфа), соединяющих вершины из с вершинами из . В частности, , по определению полного двудольного графа. Эта операция иллюстрируется на рис. 3.2.1, где и .

       
 
 
 

     Рис. 3.2.1–Соединение графов.

     Операция  соединения графов обладает следующими свойствами, которые следуют из её определения и свойств операции объединения:

     для любых графов и – свойство коммутативности;

     для любых графов , и – свойство ассоциативности.

     Операцию  соединения можно распространить по индукции на любое конечное число графов, все множества вершин которых различны: G1+…+Gn–1+Gn=(G1+…+Gn–1)+Gn.

2. Кодирование.

      В программе реализован граф в виде матрице смежности.  Использован класс «MatrixGraph». Анализировав требования было разработано меню понятный для пользователя.(приложение «А» рис.А4)

      Класс «MatrixGraph».

      Переменные класса: 

        int** graph;– Инициализация динамического массива.

      int vertexNumber; Число вершин графа.

      Методы класса.

      Таблица 2– Методы класса «Polya».

 

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

      Код программы проекта приведен  в приложении «Б».

3. Тестирование.

     В Проекте программа неоднократно тестировалась. Тестировался инициализация динамической матрицы. Тестировались также такие части программы как:

     1.Добавление дуги  в матрицу А.    

     2.Удаление дуги из матрицы А.      

     3. Добавление вершину в матрицу А. 

     4. Удаление вершину из матрицы A.  

     5.Вывод объединения А и B.       

     6.Вывод дополнения  А.           

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

     1.Добавить  дугу  в матрицу А.    

     2.Удалить  дугу из матрицы А.      

     3.Добавить  дугу  в матрицу B.    

     4.Удалить  дугу из матрицы B.      

     5.Добавить  вершину  в матрицу А. 

     6.Удалить  вершину из матрицы A.     

     7.Вывод  объединения А и B.       

     8.Вывод  дополнения  А.          

     9.Выход…

     Все результаты должны были соответствовать законам теории графов.

     1. Добавление дуги в матрицу  – проверяется методом класса  правильность веденных значений вершин между которыми должно установиться смежность. Если значение корректны устанавливается дуга.

     2. Удаление дуги из матрицы –также  проводиться на корректность  значений вершин и удаляется  дуга.      

     3. Добавление вершины– проверяется  значение веденное пользователем.  Если значение вершины существует в матрице, проверяется было ли удалено раньше эта вершина, если да соответственно производиться добавление в противном случаи оставляется все без изменение.    В случаи не существование вершины  матрица увеличивается в размере.

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

     5. Объединение двух графов -  Матрица смежности результирующего графа получается операцией поэлементного логического сложения матриц смежности исходных графов G1 и G2 .

     Результаты  тестирование выбора типа операции и соответственно выполнения операции над графами показаны в приложении «В» на рисунке В5-В11. 

        

      Заключение.

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

      

• дополнение графа;
• объединение графов;
• добавление ребра в граф.
• удаление вершины из графа
• удаление ребра из графа
• добавление вершины в граф

 

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

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

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

        
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

        
 
 
 
 
 
 
 
 

      Рисунок A4 – Алгоритм меню.

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

Файл MatrixGraph.h

#pragma once

class MatrixGraph

{

      int** graph;

      int vertexNumber;//число вершин

public:

      MatrixGraph(int);

      void  ShowUnion(MatrixGraph a);

      void ComplementGraph(); //дополнение

      void addArc(int,int);//добавление дуги

      void deleteArc(int,int);

      void addNode(int);

      void deleteNode(int,bool);

      int hasArc(int,int);// проверка дуги

      int Size(){return vertexNumber;}

      void PrintMatrix();

};

Файл MatrixGraph.cpp

#include "StdAfx.h"

#include "MatrixGraph.h"

MatrixGraph::MatrixGraph(int n)

{

      graph=new int*[vertexNumber=n];

      for(int i=0;i<n;i++)

      {

            graph[i]=new int[n];

            for(int j=0;j<n;j++)

            {

                  graph[i][j]=0;

            }

      }