Операции на графах

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

Кафедра информатики

РЕФЕРАТ

На тему:

«Операции на графах»

МИНСК, 2008

Операции на графах позволяют образовывать новые графы из нескольких более простых. В этом параграфе будут рассмотрены операции на графах без параллельных ребер (дуг).

Объединение графов.

Пусть G₁(X₁,E₁) и G₂(X₂,E₂) - произвольные графы. Объединением G₁G₂ графов G₁ и G₂ называется граф с множеством вершин X₁X₂, и с множеством ребер (дуг) E₁E_2.

Рассмотрим операцию на примере графов G₁(X₁,E₁) и G₂(X₂,E₂), приведенных на рис. 4.1. Множества вершин первого и второго графов соответственно равны X₁ = {x₁, x₂, x₃} и X₂ = {x₂, x₃, x₄}, а множество вершин результирующего графа определится как X = X₁X₂ = {x₁, x₂, x₃, x₄}. Аналогично определяем множества дуг графа:

E₁ = {(x₁, x₂), (x₁, x₃), (x₂, x₁), (x₃, x₃)}. E₂ = {(x₂, x₄), (x₃, x₂)_, (x₄, x₂)}.

E = {(x₁, x₂), (x₁, x₃), (x₂, x₁), (x₃, x₃), (x₂, x₄), (x₃, x₂)_, (x₄, x₂)}.

Результирующий граф G(X,E) = G₁(X₁,E₁)G₂(X₂,E₂) также приведен на рис. 1.

Операция объединения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:

G₁G₂ = G₂G₁ - свойство коммутативности;

G₁(G₂G₃) = (G₁G₂)G₃ - свойство ассоциативности.

Операция объединения графов может быть выполнена в матричной форме. Для графов с одним и тем же множеством вершин справедлива следующая теорема.

Теорема 1. Пусть G₁ и G₂ - два графа (ориентированные или не ориентированные одновременно) с одним и тем же множеством вершин X, и пусть A₁ и A₂ - матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G₁G₂ является матрица A = A₁A₂, образованная поэлементным логическим сложением матриц A₁ и A₂.

Рассмотрим выполнение операции объединения графов, множества вершин которых не совпадают. Пусть G₁(X₁,E₁) и G₂(X₂,E₂) - графы без параллельных ребер и множества X₁ и X₂ вершин этих графов не совпадают. Пусть A₁ и A₂ - матрицы смежности их вершин графов. Для таких графов операция объединения может быть выполнена следующим образом.

В соответствии с определением операции объединения графов найдем множество вершин результирующего графа как X₁X₂. Построим вспомогательные графы G'₁ и G'₂, множества вершин которых есть множество X₁X₂, а множество ребер (дуг) определяется множествами E₁ для графа G'₁ и E₂ для графа G'₂. Очевидно, что матрицы A'₁ и A'₂ смежности вершин этих графов могут быть получены из матриц A₁ и A₂ путем добавления в них дополнительных столбцов и строк с нулевыми элементами.

Применив к графам G'₁ и G'₂ теорему 4.1, найдем матрицу смежности вершин графа G'₁G'₂ как A'₁A'₂. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно X₁X₂, а множество ребер определяется, как E₁E₂, что соответствует операции объединения графов.

Пример 1. Выполнить в матричной форме операцию объединения графов G₁ и G₂, представленных на рис. 1.

Составим матрицы смежности вершин графов.

Множество вершин результирующего графа X₁X₂ = {x₁, x₂, x₃, x₄}. Составим матрицы смежности вершин вспомогательных графов G'₁ и G'₂.

Матрица A = A'₁A'₂ имеет вид

Полученная матрица смежности вершин A'₁ A'₂ соответствует графу G₁G₂, изображенному на рис.1.

Пересечение графов

Пусть G₁(X₁,E₁) и G₂(X₂,E₂) - произвольные графы. Пересечением G₁G₂ графов G₁ и G₂ называется граф с множеством вершин X₁X₂ с множеством ребер (дуг) E = E₁E₂

Операция пересечения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:

G₁G₂ = G₂G₁- свойство коммутативности;

G₁ (G2G3) = (G1G2) G₃ - свойство ассоциативности.

Для того чтобы операция пересечения была всеобъемлющей, необходимо ввести понятие пустого графа. Граф G(X,E) называется пустым, если множество X вершин графа является пустым (X=). Заметим, что в этом случае и множество E ребер (дуг) графа также пустое множество (E=). Пустой граф обозначается символом . Такой граф может быть получен в результате выполнения операции пересечения графов, у которых X₁X₂=. В этом случае говорят о непересекающихся графах.

Рассмотрим выполнение операции пересечения графов, изображенных на рис. 2. Для нахождения множества вершин результирующего графа запишем множества вершин исходных графов и выполним над этими множествами операцию пересечения:

X₁ = {x₁, x₂, x₃}; X₂ = {x₁, x₂, x₃, x₄};

X = X₁X₂ = {x₁, x₂, x₃}.

Аналогично определяем множество E дуг результирующего графа:

E₁ = {(x₁, x₂), (x₁, x₃), (x₂, x₁), (x₂, x₃), (x₃, x₂)};

E₂ = {(x₁, x₃), (x₂, x₁), (x₂, x₃), (x₂, x₄), (x₃, x₁)};

E = E₁E₂ = {(x₁, x₃), (x₂, x₁)}.

Графы G₁(X₁,E₁), G₂(X₂,E₂) и их пересечение приведены на рис 4.2.

Операция пересечения графов может быть выполнена в матричной форме.

Теорема 2. Пусть G₁ и G₂ - два графа (ориентированные или неориентированные одновременно) с одним и тем же множеством вершин X, и пусть A₁ и A₂ - матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1G2 является матрица A = A₁A₂ образованная поэлементным логически умножением матриц A₁ и A₂.