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

     В алгоритмах, работающих со взвешенными графами (например в алгоритме Флойда-Уоршелла), элементы матрицы смежности вместо чисел 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––Преставление графов графически . 
 

                       
 
 
 
 
 
 
 
            
            
 
 
 
 
 
 
 
 

     Таблица 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) в А.