Реализация основных операций над графами, представленных в виде матриц смежностей (стр. 4 из 5)
Соединение графов
Эта операция была введена А.А. Зыковым. Пусть
и 
– два одновременно неориентированных или ориентированных графа с непересекающимися множествами вершин. Соединение графов 
состоит из 
и всех рёбер в случае неориентированного графа (пар нестрого параллельных дуг в случае орграфа), соединяющих вершины из 
с вершинами из 
. В частности, 
, по определению полного двудольного графа. Эта операция иллюстрируется на рис. 3.2.1, где 
и 
.  |
Рис. 3.2.1–Соединение графов.
Операция соединения графов обладает следующими свойствами, которые следуют из её определения и свойств операции объединения:
для любых графов
и 
– свойство коммутативности;для любых графов
, 
и 
– свойство ассоциативности.Операцию соединения можно распространить по индукции на любое конечное число графов, все множества вершин которых различны: G1+…+Gn–1+Gn=(G1+…+Gn–1)+Gn.
В программе реализован граф в виде матрице смежности. Использован класс «MatrixGraph». Анализировав требования было разработано меню понятный для пользователя.(приложение «А» рис.А4)
Класс «MatrixGraph».
Переменные класса:
int** graph;– Инициализация динамического массива.
int vertexNumber; Число вершин графа.
Методы класса.
Таблица 2– Методы класса «Polya».
| Название | Входные данные | Выходные данные | Описание |
| MatrixGraph(); | int | - | Инициализирует динамический массив. |
| ShowUnion(); | MatrixGraph a | Void | Вывод на экран объединение двух графов. |
| ComplementGraph(); | - | Void | Дополнение графа. |
| addArc(); | int from, int to | void | Добавление дуги в граф. |
| deleteArc(); | int from, int to | Void | Удаление дуги из граф. |
| addNode(); | int n | Void | Добавление вершины |
| deleteNode(); | int n,bool flag | Void | Удаление вершины |
| hasArc(); | int from, int to | Int | Проверка на наличие дуги |
| Size() | int | Возвращает значение количества вершин. | |
| PrintMatrix(); | void | Вывод на экран матрицу смежности графа. |
В функции «Main» инициализируется два графа, и выводиться меню. В меню предложены основные операции над графами.
Код программы проекта приведен в приложении «Б».
В Проекте программа неоднократно тестировалась. Тестировался инициализация динамической матрицы. Тестировались также такие части программы как:
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;
}
}
}
void MatrixGraph::addNode(int n)
{
int temp_n=n,countVertex;
temp_n--;
int** tempgraph;
if(temp_n<=0)
{
return;
}
if(temp_n>0&&temp_n<vertexNumber)
{
if(graph[temp_n][temp_n]==-1)
{
deleteNode(temp_n,false);
}
}
else
{
countVertex=n-vertexNumber;
n=countVertex+vertexNumber;
tempgraph=new int*[n];
for(int i=0;i<n;i++)
{
tempgraph[i]=new int[n];
for(int j=0;j<n;j++)
{
tempgraph[i][j]=0;
}
}
for(int i=0;i<vertexNumber;i++)
{
for(int j=0;j<vertexNumber;j++)
{
tempgraph[i][j]=graph[i][j];
}
}
delete [] graph;
graph=tempgraph;
vertexNumber+=countVertex;
}
}
void MatrixGraph::deleteNode(int n,bool flag)
{
if(n<0||n>=vertexNumber)
{
return;
}
if(flag)
{
for(int i=0;i<vertexNumber;i++)