--PAGE_BREAK--
в.
X1
X2
X3
X4
X5
X1
1
X2
1
X3
1
1
X4
X5
1
1
г.
X1-2
X3
X4
X5
X1-2
1
1
1
X3
1
1
X4
1
X5
1
1
Таблица 1–Матрицы смежности графов.
д.
X1-2
X3
X4
X5
X1-2
1
1
X3
1
1
X4
1
X5
1
1
е.
X1-2
X3-4
X5
X1-2
1
1
X3
1
X5
1
1
Таблица 1–Матрицы смежностей графов.
Удаление ребра или удаление дуги. Если ai -дуга графа G = = (X, A), то G-ai – подграф графа G, получающийся после удаления из G дуги ai . Заметим, что концевые вершины дуги ai не удаляются. Удаление изграфа множества вершин или дуг определяется как последовательное удаление определенных вершин или дуг. Удаление дуг a4 и a7 показано на рис. 2.2.3, в. Результирующая матрица смежности графа после выполнения операции удаления дуги ai получается путем удаления соответствующих элементов из исходной матрицы (таблица 1в).
Стягивание. Под стягиванием подразумевают операцию удаления дуги или ребра и отождествление его концевых вершин. Граф, изображенный на рис. 2.2.3, д получен стягиванием дуги a1 , а на рис. 2.2.3, е – стягиванием дуг a1 ,a6 и a7 . Соответствующие результирующие матрицы смежности показаны в таблицах 1д и 1е.
Пересечение графов G1 и G2 , обозначаемое как G1 G2 , представляет собой граф G4 = (Х1 Х2, A1 A2). Таким образом, множество вершин графа G4 состоит из вершин, присутствующих одновременно в G1 и G2 . Операция пересечения графов G1 G2 показана на рис. 2.2.2, в, а результирующая матрица смежности получается операцией поэлементного логического умножения матриц смежности исходных графов G1 и G2 . показана на рис. 2.2.2.г.
Дополнение.
Пусть G(V,E) – обыкновенный граф. Дополнение графа G (также обыкновенный граф) имеет в качестве множества вершин множество V, любые две несовпадающие вершины в смежны тогда и только тогда, когда они не смежны в G. На рис. 3.1.1 изображены графы , и их дополнения и соответственно.
Рисунок. 3.1.1–Дополнение графов.
Очевидно, что и тогда и только тогда, когда .
Граф, изоморфный своему дополнению, называется самодополнительным. Например, и граф, изображённый на рис. 3.1.2, – самодополнительные.
Рисунок. 3.1.2–Самодополнительные графы.
Теорема Пусть G – обыкновенный граф с матрицей смежности вершин А. Тогда матрицей смежности вершин графа является матрица , образованная поэлементным логическим отрицанием матрицы А, исключая диагональные элементы, которые остаются нулевыми.
Если число вершин графа G равно p, то матрицы А и имеют одинаковую размерность . Если G – неориентированный обыкновенный граф, то элемент () матрицы А равен 1, если вершины и смежны, и 0 в противном случае. Так как и () смежны в тогда и только тогда, когда они не смежны в G, то равно 1 (0) в тогда и только тогда, когда равно 0 (1) в А.
Если G – обыкновенный орграф, то элемент () матрицы А равен 1, если существует дуга в G, и 0 в противном случае. Элемент () в равен 1 (0) тогда и только тогда, когда не существует (существует) дуга в G, т.е. элемент равен 0 (1) в А.
в А и в , т. к. 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.
1.2 Кодирование.
В программе реализован граф в виде матрице смежности. Использован класс «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();
intn,bool flag
Void
Удаление вершины
hasArc();
int from, int to
Int
Проверка на наличие дуги
Size()
int
Возвращает значение количества вершин.
PrintMatrix();
void
Вывод на экран матрицу смежности графа.
В функции «Main» инициализируется два графа, и выводиться меню. В меню предложены основные операции над графами.
Код программы проекта приведен в приложении «Б».
1.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.
продолжение
--PAGE_BREAK--