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

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

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

РЕФЕРАТ

На тему:

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

МИНСК, 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₁Ç (G2ÇG3) = (G1ÇG2) Ç 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₂ тАУ матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1ÇG2Ваявляется матрица A = A₁ÇA₂ образованная поэлементным логически умножением матриц A₁ и A₂.

Рассмотрим выполнение операции пересечения для графов с несовпадающим множеством вершин.

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

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

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

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

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

Находим множество вершин X результирующего графа.

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

Составим матрицы смежности вершин вспомогательных графов GтАЩ₁ и GтАЩ₂.

Найдем матрицу смежности вершин A = A₁ Ç A₂

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

Композиция графов

Пусть G₁(X,E₁) и G₂(X,E₂) тАФ два графа с одним и тем же множеством вершин X. Композицией G₁(G₂) графов G₁и G₂ называется граф с множеством вершин E, в котором существует дуга (x_i,x_j) тогда и только тогда, когда существует дуга (x_i,x_k), принадлежащая множеству E₁, и дуга (x_k,x_j), принадлежащая множеству E₂.

Рассмотрим выполнение операции композиции G₁(G₂) на графах, изображенных на рис.3. Для рассмотрения операции составим таблицу, в первом столбце которой указываются ребра (x_i, x_k), принадлежащие графу G₁, во втором тАФ ребра (x_k, x_j), принадлежащие графу G₃, а в третьем тАФ результирующее ребро (x_i, x_j) для графа G₁(G₂).

Заметим, что дуга (x₁,x₃) результирующего графа в таблице встречается дважды. Однако, поскольку рассматриваются графы без параллельных ребер (дуг), то в множестве E результирующего графа дуга (x₁,x₃) учитывается только один раз, т.е. E = {(x₁,x₁), (x₁,x₃), (x₂,x₁), (x₂,x₃)}

На рис. 3 изображены графы G₁ и G₂ и их композиции G₁(G₂). На этом же рисунке изображен граф G₂(G₁). Рекомендуется самостоятельно построить граф G₂(G₁) и убедиться,Ва что графы G₁(G₂) и G₂(G₁)ВаВа не изоморфны.

Пусть А₁ и A₂ тАУ матрицы смежности вершин графов G₁(X,E₁) и G(X,E₂) соответственно.Ва Рассмотрим матрицу A₁₂элементы a_ij которой вычисляется так:

_n

a_ij= Úa_1ikÙa_2kj(1)

^k=1

Вагде a_1ikи a_2kj тАУ элементы матрицы смежности вершин первого и второго графов соответственно. Элемент a_ij равен 1, если в результирующем графе G₁(G₂) существует дуга, исходящая из вершины x_i и заходящаяВа x_j, и нулю тАУ в противном случае.

Пример 3. Выполнить операцию композиции для графов, предВнставленных на рис. 3.

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

Вычислив элементы матрицы согласно (1), получаем: