«Сетевые структуры данных. Понятие графа и его представления.»

Глава 3. Операции над графами
3.1. Операции над графами

Операции над графами образуют новые графы из старых. Операции можно разделить на следующие основные категории.

1. 
   Унарные операции — это метод создания нового графа из старого.
   
   1. 
      Элементарные унарные операции. Иногда этот класс операций называют «операции редактирования» графов. Они создают новый граф из исходного графа путём простых, локальных изменений, таких как добавление или удаление вершины, или дуги, слияние или расщепление вершин, стягивание графа, и т.д.
      
   2. 
      Сложные унарные операции. Это такие операции как: рёберный граф, двойственный граф, дополнение графа, минор графа, возведение в степень, граф Мычельского.
      
2. 
   Бинарные операции - создаёт новый граф из двух исходных графов G1(V1, E1) и G2(V2, E2):
   

Существуют такие бинарные операции как несвязанное объединение графов или просто объединение, соединением двух графов, произведение графов, прямое произведение графов, лексикографическое произведение графов, строгое произведение графов, тензорное произведение графов, зигзаг-произведение.
Все операции, которые нужно произвести, производятся с помощью матриц смежности, верней путём видоизменения исходной матрицы исходного графа.

3.2. Бинарные операции

Объединение графов G₁ и G₂, обозначаемое как G₁ v G₂, представляет такой граф G₃ = (X₁ v X₂, A₁ V A₂), что множество его вершин является объединением Х₁ и Х₂, а множество ребер – объединением A₁ и A₂. Граф G₃, полученный операцией объединения графов G₁ и G₂, показан на рисунке 10 (д), а его матрица смежности – на рисунок 10 (е). Матрица смежности результирующего графа получается операцией поэлементного логического сложения матриц смежности исходных графов G₁ и G₂.

Рисунок 10 – Операция объединения графов
Пересечение графов G₁ и G₂, обозначаемое как G₁^G₂, представляет собой граф G₄ = (X₁ ^ X₂, A₁ ^ A₂). Таким образом, множество вершин графа G₄ состоит из вершин, присутствующих одновременно в G₁ и G₂. Операция пересечения графов G₁ ^ G₂ показана на рисунке 11 (в), а результирующая матрица смежности получается операцией поэлементного логического умножения матриц смежности исходных графов G₁ и G₂. показана на рисунке 11 (г).



Рисунок 11 – Операция пересечения графов

Операция пересечения и кольцевой суммы: (а) – граф G₁; (б) – граф G₂ ; (в) – граф G₁^G₂; (г) – матрица смежности графа G₁^G₂; (д) – граф G₁ G₂; (е) – матрица смежности графа G₁ G₂

Кольцевая сумма двух графов G₁ и G₂, обозначаемая как G₁ G₂, представляет собой граф G₅, порожденный на множестве ребер A₁ A₂. Другими словами, граф G₅ не имеет изолированных вершин и состоит только из ребер, присутствующих либо в G₁ , либо в G₂ , но не в обоих одновременно. Кольцевая сумма графов G₁ u G₂ показана на рисунок 11(д), а результирующая матрица смежности получается операцией поэлементного логического сложения по mod 2 матриц смежности исходных графов G₁ u G₂, показана на рисунок 11(е).
Легко убедиться в том, что три рассмотренные операции коммутативны т.е. G₁ ^ G₂ = G₂ ^ G₁ ; G₁ u G₂ = G₂ u G₁ ; G₁ G₂ = G₂ G₁, и многоместны, т.е. G₁ u G₂ u G₃ u G₄ u … , G₁ ^ G₂ ^ G₃ ^ G₄ ^ … и так далее.