Реализация основных операций над графами, представленных в виде матриц смежностей (стр. 2 из 5)
Два графа G1 и G2 с матрицами смежности A1 и A2 являются изоморфными если и только если существует перестановочная матрица P, такая что
PA1P-1 = A2.
Из этого следует, что матрицы A1 и A2 подобны, а значит имеют равные наборы собственных значений, определители и характеристические многочлены. Однако обратное утверждение не всегда верно — два графа с подобными матрицами смежности могут быть неизоморфны.
Если A — матрица смежности графа G, то матрица Am обладает следующим свойством: элемент в i-й строке, j-м столбце равен числу путей из i-й вершины в j-ю, состоящих из ровно m ребер.
Матрица смежности и списки смежности являются основными структурами данных, которые используются для представления графов в компьютерных программах
Использование матрицы смежности предпочтительно только в случае неразряженных графов, с большим числом ребёр, так как она требует хранения по одному биту данных для каждого элемента. Если граф разрежён, то большая часть памяти напрасно будет тратиться на хранение нулей, зато в случае неразряженных графов матрица смежности достаточно компактно представляет граф в памяти, используя примерно n2 / 8 байт памяти, что может быть на порядок лучше списков смежности.
В алгоритмах, работающих со взвешенными графами (например в алгоритме Флойда-Уоршелла), элементы матрицы смежности вместо чисел 0 и 1, указывающих на присутствие или отсутствие ребра, часто содержат веса самих ребер. При этом на место отсутствующих ребер ставят некоторое специальное граничное значение (англ. sentinel), зависящее от решаемой задачи, обычно 0 или
.В нашей работе анализ требований есть анализ основных требований теорий графов. В нашей работе был разработан представление графа в виде матрицы смежности и представлены основные операции над графами. Рассмотрим следующие элементы теорий графов.
Операции над графами и их свойства.
Удаление вершины
из графа G приводит к подграфу 
, содержащему все вершины графа G, за исключением , и все рёбра графа G, не инцидентные 
. Другими словами, 
есть максимальный подграф графа G, не содержащий .Удаление ребра ej из графа G приводит к основному подграфу, содержащему все рёбра графа G, за исключением ej, т.е. G–ej есть максимальный подграф графа G, не содержащий ej.
Удаление произвольного множества вершин или рёбер из G определяется как последовательное удаление всех элементов этого множества.
Если
и 
не смежны в G, то добавление ребра 
( 
) образует наименьший надграф графа G, содержащий ребро 
( 
).Эти понятия иллюстрируются на рис. 2.1.1.
 |
Рис. 2.1.1–Примеры графов
Существуют графы, для которых результат удаления вершины или ребра, а также добавления ребра не зависит от выбора вершины или ребра. Для графа G, обладающего этим свойством, обозначим соответствующие графы через G–v,
G+e, см. рис. 2.1.2.  |
Рис. 2.1.2–Удаление и добавление дуги в граф.
Удаление вершины х3 показано на рис. 2.2.3,б (для исходного графа, изображенного на рис. 2.2.3,а). Матрица смежности исходного графа представлена на таблице 1а). Результирующая матрица смежности графа после выполнения операции удаления вершины хi получается путем удаления соответствующего i- го столбца и i-ой строки из исходной матрицы и "сжимания" матрицы по вертикали и горизонтали начиная с (i+1)- го столбца и (i+1)-ой строки (таблица 1б).В дальнейшем элементы графа могут быть переобозначены.
Рисунок 2.2.2–Преставление графов графически и с помощи матриц.
Рисунок 2.2.3––Преставление графов графически .
| a. | |||||
| X1 | X2 | X3 | X4 | X5 | |
| X1 | 1 | ||||
| X2 | 1 | 1 | |||
| X3 | 1 | 1 | |||
| X4 | 1 | ||||
| X5 | 1 | 1 | |||
| б. | ||||
| X1 | X2 | X4 | X5 | |
| X1 | 1 | |||
| X2 | 1 | |||
| X4 | ||||
| X5 | 1 | 1 | ||
| в. | |||||
| 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–Дополнение графов.
Очевидно, что
и 
тогда и только тогда, когда 
.