Реферат: Операции на графах - Refy.ru - Сайт рефератов, докладов, сочинений, дипломных и курсовых работ

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

Рефераты по математике » Операции на графах

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

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


РЕФЕРАТ

На тему:

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


МИНСК, 2008


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


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


Пусть G1(X1,E1) и G2(X2,E2) – произвольные графы. Объединением G1G2 графов G1 и G2 называется граф с множеством вершин X1X2, и с множеством ребер (дуг) E1E2.

Рассмотрим операцию на примере графов G1(X1,E1) и G2(X2,E2), приведенных на рис. 4.1. Множества вершин первого и второго графов соответственно равны X1 = {x1, x2, x3} и X2 = {x2, x3, x4}, а множество вершин результирующего графа определится как X = X1X2 = {x1, x2, x3, x4}. Аналогично определяем множества дуг графа:

E1 = {(x1, x2), (x1, x3), (x2, x1), (x3, x3)}. E2 = {(x2, x4), (x3, x2), (x4, x2)}.

E = {(x1, x2), (x1, x3), (x2, x1), (x3, x3), (x2, x4), (x3, x2), (x4, x2)}.

Результирующий граф G(X,E) = G1(X1,E1)G2(X2,E2) также приведен на рис. 1.



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

G1G2 = G2G1 – свойство коммутативности;

G1(G2G3) = (G1G2)G3 – свойство ассоциативности.

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

Теорема 1. Пусть G1 и G2 – два графа (ориентированные или не ориентированные одновременно) с одним и тем же множеством вершин X, и пусть A1 и A2 – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1G2 является матрица A = A1A2, образованная поэлементным логическим сложением матриц A1 и A2.

Рассмотрим выполнение операции объединения графов, множества вершин которых не совпадают. Пусть G1(X1,E1) и G2(X2,E2) – графы без параллельных ребер и множества X1 и X2 вершин этих графов не совпадают. Пусть A1 и A2 – матрицы смежности их вершин графов. Для таких графов операция объединения может быть выполнена следующим образом.

В соответствии с определением операции объединения графов найдем множество вершин результирующего графа как X1X2. Построим вспомогательные графы G’1 и G’2, множества вершин которых есть множество X1X2, а множество ребер (дуг) определяется множествами E1 для графа G’1 и E2 для графа G’2. Очевидно, что матрицы A’1 и A’2 смежности вершин этих графов могут быть получены из матриц A1 и A2 путем добавления в них дополнительных столбцов и строк с нулевыми элементами.

Применив к графам G’1 и G’2 теорему 4.1, найдем матрицу смежности вершин графа G’1G’2 как A’1A’2. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно X1X2, а множество ребер определяется, как E1E2, что соответствует операции объединения графов.

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

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





x1

x2

x3




x2

x3

x4



x1

0 1 1

x2

0 0 1

A1

=

x2

1 0 0

A2

=

x3

1 0 0


x3

0 0 1

x4

0 1 0

Множество вершин результирующего графа X1X2 = {x1, x2, x3, x4}. Составим матрицы смежности вершин вспомогательных графов G’1 и G’2.





x1

x2

x3

x4




x1

x2

x3

x4



x1

0 1 1 0

x1

0 0 0 0

A’1

=

x2

1 0 0 0

A’2

=

x2

0 0 0 1


x3

0 0 1 0

x3

0 1 0 0


x4

0 0 0 0

x4

0 0 1 0

Матрица A = A’1A’2 имеет вид





X1

x2

x3

x4



x1

0 1 1 0


x2

1 0 0 1

A = A’1A’2

=

x3

0 1 1 0


x4

0 0 1 0

Полученная матрица смежности вершин A’1  A’2 соответствует графу G1G2, изображенному на рис.1.


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


Пусть G1(X1,E1) и G2(X2,E2) – произвольные графы. Пересечением G1G2 графов G1 и G2 называется граф с множеством вершин X1X2 с множеством ребер (дуг) E = E1E2

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


G1G2 = G2G1– свойство коммутативности;

G1 (G2G3) = (G1G2)  G3 – свойство ассоциативности.


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

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


X1 = {x1, x2, x3}; X2 = {x1, x2, x3, x4};

X = X1X2 = {x1, x2, x3}.


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


E1 = {(x1, x2), (x1, x3), (x2, x1), (x2, x3), (x3, x2)};

E2 = {(x1, x3), (x2, x1), (x2, x3), (x2, x4), (x3, x1)};

E = E1E2 = {(x1, x3), (x2, x1)}.


Графы G1(X1,E1), G2(X2,E2) и их пересечение приведены на рис 4.2.


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

Теорема 2. Пусть G1 и G2 – два графа (ориентированные или неориентированные одновременно) с одним и тем же множеством вершин X, и пусть A1 и A2 – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1G2 является матрица A = A1A2 образованная поэлементным логически умножением матриц A1 и A2.

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

Пусть G1(X1,E1) и G2(X2,E2) – графы без параллельных ребер, множества X1 и X2 вершин графов не совпадают, а A1 и A2 – матрицы смежности вершин графов. Для таких графов операция пересечения может быть выполнена так.

В соответствии с определением операции пересечения графов найдем множество вершин результирующего графа как X1X2. Построим вспомогательные графы G’1 и G’2, множества вершин которых есть множество X1X2, а множество ребер (дуг) определяется множествами E’1 и E’2 всех ребер (дуг), инцидентных этим вершинам. Очевидно, что матрицы A’1 и A’2 смежности вершин этих графов могут быть получены из матриц A1 и A2 путем удаления из них столбцов и строк, соответствующих вершинам, не вошедшим во множество X1X2.

Применив к графам G’1 и G’2 теорему 2, найдем матрицу смежности вершин графа G’1G’2 как A’1A’2. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно X1X2, а множество ребер определяется, как E1E2, что соответствует операции пересечения графов.

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

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





x1

x2

x3




x1

x2

x3

x4



x1

0 1 1

x1

0 0 0 1

A1

=

x2

1 0 1

A2

=

x2

1 0 1 1


x3

0 1 0

x3

1 0 0 0








x4

0 0 0 0

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

X = X1X2 = {x1, x2, x3}.

Составим матрицы смежности вершин вспомогательных графов G’1 и G’2.





x1

x2

x3




x1

x2

x3



x1

0 1 1

x1

0 0 0

A’1

=

x2

1 0 1

A’2

=

x2

1 0 1


x3

0 1 0

x3

1 0 0

Найдем матрицу смежности вершин A = A1 A2





x1

x2

x3



x1

0 0 0

A’1A’2

=

x2

1 0 1


x3

0 0 0

Полученная матрица смежности вершин A’1 A’2 соответствует графу G1G2, изображенному на рис.2.


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


Пусть G1(X,E1) и G2(X,E2) — два графа с одним и тем же множеством вершин X. Композицией G1(G2) графов G1 и G2 называется граф с множеством вершин E, в котором существует дуга (xi,xj) тогда и только тогда, когда существует дуга (xi,xk), принадлежащая множеству E1, и дуга (xk,xj), принадлежащая множеству E2.

Рассмотрим выполнение операции композиции G1(G2) на графах, изображенных на рис.3. Для рассмотрения операции составим таблицу, в первом столбце которой указываются ребра (xi, xk), принадлежащие графу G1, во втором — ребра (xk, xj), принадлежащие графу G3, а в третьем — результирующее ребро (xi, xj) для графа G1(G2).


G1

G2

G1(G2)

(x1,x2)

(x2,x1)

(x2,x3)

(x1,x1)

(x1,x3)

(x1,x3) (x3,x3) (x1,x3)
(x2,x1)

(x1,x1)

(x1,x3)

(x2,x1)

(x2,x3)


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

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


Пусть А1 и A2 – матрицы смежности вершин графов G1(X,E1) и G(X,E2) соответственно. Рассмотрим матрицу A12элементы aij которой вычисляется так:

n

aij = a1ika2kj (1)

k=1

где a1ik и a2kj – элементы матрицы смежности вершин первого и второго графов соответственно. Элемент aij равен 1, если в результирующем графе G1(G2) существует дуга, исходящая из вершины xi и заходящая xj, и нулю – в противном случае.

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

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





x1

x2

x3




x1

x2

x3



x1

0 1 1

x1

1 0 1

A1

=

x2

1 0 0

A2

=

x2

1 0 1


x3

0 0 0

x3

0 0 1

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





x1

x2

x3




x1

x2

x3



x1

1 0 2

x1

0 1 1
A12

=

x2

1 0 1

A21

=

x2

0 1 1


x3

0 0 0

x3

0 0 0

Нетрудно убедиться, что полученным матрицам смежности вершин соответствуют графы G1(G2) и G2(G1), представленные на рис. 3.

Декартово произведение графов. Пусть G1(X,E1) и G2(Y,E2) — два графа. Декартовым произведением G1(X,E1)G2(Y,E2) графов G1(X,E1) и G2(X,E2) называется граф с множеством вершин XY, в котором дуга (ребро), идущая из вершины (xiyj) в (xkyl), существует тогда и только тогда когда существует дуга (xixk), принадлежащая множеству дуг E1 и j = l или когда существует дуга (yj,yl), принадлежащая множеству E2 и i = k.

Выполнение операции декартова произведения рассмотрим на примере графов, изображенных на рис. 4. Множество вершин Z результирующего графа определяется как декартово произведение множеств XY. Множество Z содержит следующие элементы: z1=(x1y1), z2=(x1y2), z3=(x1y3), z4=(x2y1), z5=(x2y2), z6=(x2y3).


Определим множество дуг результирующего графа. Для этого выделим группы вершин множества Z, компоненты которых совпадают. В рассматриваемом примере пять таких групп: две группы с совпадающими компонентами из множества X, и три группы, имеющие совпадающие компоненты из Y. Рассмотрим группу вершин результирующего графа, которые имеют общую компоненту x1: z1=(x1y1), z2=(x1y1), z3=(x1y3). Согласно определению операции декартова произведения графов, множество дуг между этими вершинами определяется связями между вершинами множества Y. Таким образом, дуга (y1,y1) в графе G2 определяет наличие дуги (z1,z1) в результирующем графе. Для удобства рассмотрения всех дуг результирующего графа составим таблицу, в первом столбце которой перечисляются вершины с совпадающими компонентами, во втором – дуги между несовпадающими компонентами, а в третьем и четвертом – дуги в результирующем графе.


№ п.п. Группы вершин с совпадаю­щими компонентами Дуги для несовпада­­ю­щих компонент

Дуга

(xiyj)(xkyl)

Дуга

(z,z)

1 z1=(x1y1), z2=(x1y2), z3=(x1y3)

(y1,y1)

(y1,y2)

(y2,y3)

(y3,y1)

(x1y1)(x1y1)

(x1y1)(x1y2)

(x1y2)(x1y3)

(x1y3)(x1y1)

(z1,z1)

(z1,z2)

(z2,z3)

(z3,z1)

2 z4=(x2y1), z5=(x2y2), z6=(x2y3)

(y1,y1)

(y1,y2)

(y2,y3)

(y3,y1)

(x2y1)(x2y1) (x2y1)(x2y2) (x2y2)(x2y3) (x2y3)(x2y1)

(z4,z4)

(z4,z5)

(z5,z6)

(z6,z4)

3 z1=(x1y1), z4=(x2y1)

(x1,x2)

(x2,x1)

(x1y1)(x2y1) (x2y1)(x1y1)

(z1,z4)

(z4,z1)

4 z2=(x1y2), z5=(x2y2)

(x1,x2)

(x2,x1)

(x1y2)(x2y2) (x1y2)(x1y2)

(z2,z5)

(z5,z2)

5 Z3=(x1y3), z6=(x2y3)

(x1,x2)

(x2,x1)

(x1y3)(x2y3) (x2y3)(x1y3)

(z3,z6)

(z6,z3)


Граф G1 G2 изображен на рис. 4.

Операция декартова произведения обладает следующими свойствами.

1. G1G2 = G2G1

2. G1(G2G3) = (G1G2)G3.

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

Пусть G1(X,E1) и G2(Y,E2) – два графа, имеющие nx и ny вершин соответственно. Результирующий граф G1G2 имеет nxny вершин, а его матрица смежности вершин - квадратная матрица размером (nxny) (nx ny). Обозначим через a = a(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z=(xiyj) c z=(xkyl). Согласно определению операции этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:


a = a(ij)(kl) = Kika2,jl  Kjla1,ik, (2)


где a1,ik, a2,jl – элементы матрицы смежности вершин графов G1 и G2 соответственно;

Kik – символ Кронекера, равный 1, если i=k, и нулю, если ik .

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

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





x1

x2




y1

y2

y3



x1

0 1

y1

1 1 0

A1

=

x2

1 0

A2

=

y2

0 0 1







y3

1 0 0

Для построения матрицы смежности результирующего графа воспользуемся соотношением (2). В этом соотношении первое слагаемое Kika2,jl указывает на наличие дуг для вершин, у которых совпадают компоненты из множества X. Для пояснения сказанного, рассмотрим вспомогательную матрицу Axy, в которой элементы, для которых Kik = 1, помечены символом X. Эти элементы принимают значения, равные значениям соответствующих элементов матрицы A2смежности вершин графа G2, так, как это показано для матрицы A*.





x1y1

x1y2

x1y3

x2y1

x2y2

x2y3



x1y1

XY X X Y 0 0


x1y2

X XY X 0 Y 0

Axy

=

X1y3

X X XY 0 0 Y


X2y1

Y 0 0 XY X X


X2y2

0 Y 0 X XY X


X2y3

0 0 Y X X XY




x1y1

x1y2

x1y3

x2y1

x2y2

x2y3



x1y1

a1,11 a2,11 a2,12 a2,13 a1,12



x1y2

a2,21 a1,11a2,22 a2,11
a1,12

A*

=

x1y3

a2,31 A2,32 a1,11a2,33 0 0 a1,12


x2y1

a1,21 0 0 a1,22a2,11 a2,12 a2,13


x2y2

0 a1,21 0 a2,21 a1,22a2,22 a2,23


x2y3

0 0 a1,21 a2,31 a2,32 a1,22 a2,33

Второе слагаемое Kjla1,ik соотношения (2) указывает на наличие дуг для групп вершин, у которых совпадают компоненты из множества Y. В матрице Axy элементы, для которых Kjl = 1 помечены символом Y. Эти элементы принимают значения, равные значениям соответствующих элементов матрицы A1смежности вершин графа G1, так, как это показано для матрицы A*.

Заметим, что в матрицах Axy и A* на главной диагонали располагаются элементы, равные логической сумме значений элементов матриц смежности вершин обоих графов. Это определяется тем, что на главной диагонали расположены элементы, для которых Kik = Kjl = 1.

Таким образом, матрица смежности вершин результирующего графа принимает вид:





x1y1

x1y2

x1y3

x2y1

x2y2

x2y3



x1y1

1

1

0

1

0 0


x1y2

0

0

1

0

1

0

A

=

x1y3

1

0

0

0 0

1



x2y1

1

0 0

1

1

0



x2y2

0

1

0

0

0

1



x2y3

0 0

1

1

0

0


Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф G1G2, представленный на рис. 4

Операция произведения графов. Пусть G1(X,E1) и G2(Y,E2) - два графа. Произведением G1G2 графов G1 и G2 называется граф с множеством вершин XY, а дуга из вершины (xi,yj) в вершину (xk,yl) существует тогда и только тогда, когда существуют дуги (xi,xk)  E1 и (yj,yl)  E2.

Выполнение операции произведения рассмотрим на примере графов, изображенных на рис. 5. Множество вершин Z результирующего графа определяется как декартово произведение множеств XY. Множество Z содержит следующие элементы: z1=(x1y1), z2=(x1y2), z3=(x1y3), z4=(x2y1), z5=(x2y2), z6=(x2y3).

Определим множество дуг результирующего графа. Для удобства рассмотрения составим таблицу, в первом столбце которой указываются дуги графа G1, во втором – дуги графа G2, а в третьем и четвертом – дуги результирующего графа.


G1

G2

(x1,y1)(x2,y1)

(z, z)

(x1,x2)

(y1,y1)

(y1,y2)

(y2,y3)

(y3,y2)

(x1,y1)(x2,y1)

(x1,y1)(x2,y2)

(x1,y2)(x2,y3)

(x1,y3)(x2,y2)

(z1,z4)

(z1,z5)

(z2,z6)

(z3,z5)

(x2,x1)

(y1,y1)

(y1,y2)

(y2,y3)

(y3,y2)

(x2,y1)(x1,y1)

(x2,y1)(x1,y2)

(x2,y2)(x1,y3)

(x2,y3)(x1,y2)

(z4,z1)

(z4,z2)

(z5,z3)

(z6,z2)

Результирующий граф G1G2 изображен на рис.5.


Операция произведения обладает следующими свойствами.

1. G1G2 = G2G1.

2. G1(G2G3) = (G1G2)G3.

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

Пусть G1(X,E1) и G2(Y,E2) – два графа, имеющие nx и ny вершин соответственно. Результирующий граф G1G2 имеет nxny вершин, а его матрица смежности вершин - квадратная матрица размером (nxny) (nx ny). Обозначим через a = a(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z=(xiyj) c z=(xkyl). Этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:


a =a(ij)(kl) = a1,ik  a2,jl, (3)


де a1,ik, a1,ik – элементы матрицы смежности вершин графов G1 и G2 соответственно.

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

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





x1

x2




y1

y2

y3



x1

0 1

y1

1 1 0

A1

=

x2

1 0

A2

=

y2

0 0 1







y3

0 1 0

Построим матрицу A смежности вершин результирующего графа, каждый элемент которой вычисляется согласно соотношению (4.3).




x1y1

x1y2

x1y3

x2y1

x2y2

x2y3



x1y1

a1,11 a2,11 a1,11a2,12 a1,11 a2,13 a1,12a2,11 a1,12 a2,12 a1,12 a2,13


x1y2

a1,11 a2,21 a1,11 a2,22 a1,11 a2,23 a1,12 a2,21 a1,12 a2,22 a1,12 a2,23

A

=

x1y3

a1,11 a2,21 a1,11 a2,22 a1,11 a2,23 a1,12 a2,31 a1,12 a2,32 a1,12 a2,33


x2y1

a1,21 a2,11 a1,21 a2,12 a1,21 a2,13 a1,22 a2,11 a1,22 a2,12 a1,22 a2,13


x2y2

a1,21 a2,21 a1,21 a2,22 a1,21 a2,23 a1,12 a2,21 a1,12 a2,22 A1,12 a2,23


x2y3

a1,21 a2,31 a1,21 a2,32 a1,21 a2,33 a1,22 a2,31 a1,12 a2,32 A1,12 a2,33

Для удобства рассмотрения разделим матрицу A на четыре квадратные подматрицы. Заметим, что каждая подматрица может быть получена путем логического элементов матрицы умножения A2 на один из элементов a1,ij матрицы A1. С учетом этого матрицу A можно представить так:




x1y1

x1y2

x1y3

x2y1

x2y2

x2y3



x1y1


a1,11A2


a1,12A2



x1y2

A

=

x1y3



x2y1


a1,21A2


a1,22A2



x2y2



x2y3


Таким образом, матрица смежности вершин графа G1G2 имеет вид:





x1y1

x1y2

x1y3

x2y1

x2y2

x2y3



x1y1

0 0 0 1 1 0


x1y2

0 0 0 0 0 1

A

=

x1y3

0 0 0 0 1 0


x2y1

1 1 0 0 0 0


x2y2

0 0 1 0 0 0


x2y3

0 1 0 0 0 0

Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф G1G2, представленный на рис. 5.

ЛИТЕРАТУРА


Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана, 2001.– 744 с. (Сер. Математика в техническом университете; Вып XIX).

Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.– М.: Наука, Физматлит, 2000.– 544 с.– ISBN 5-02-015238-2.

Зарубин В.С. Математическое моделирование в технике: Учеб. для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.– 496 с. (Сер. Математика в техническом университете; вып. XXI, заключительный).