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

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

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

РЕФЕРАТ

На тему:

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


МИНСК, 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 для графа G1 и E2 для графа G2. Очевидно, что матрицы 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

011

x2

001

A1

=

x2

100

A2

=

x3

100

x3

001

x4

010

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

x1

x2

x3

x4

x1

x2

x3

x4

x1

0110

x1

0000

A’1

=

x2

1000

A’2

=

x2

0001

x3

0010

x3

0100

x4

0000

x4

0010

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

X1

x2

x3

x4

x1

0110

x2

1001

A = A’1ÈA’2

=

x3

0110

x4

0010

Полученная матрица  смежности вершин 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 = A1ÇA2 образованная поэлементным логически умножением матриц 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’1ÇA’2. Очевидно, что полученной матрице смежности вершин  соответствует граф, множество вершин которого равно X1ÇX2, а множество ребер определяется, как E1ÇE2, что соответствует операции пересечения графов.

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

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

x1

x2

x3

x1

x2

x3

x4

x1

011

x1

0001

A1

=

x2

101

A2

=

x2

1011

x3

010

x3

1000

x4

0000

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

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

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

x1

x2

x3

x1

x2

x3

x1

011

x1

000

A’1

=

x2

101

A’2

=

x2

101

x3

010

x3

100

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

x1

x2

x3

x1

000

A’1ÇA’2

=

x2

101

x3

000

 Полученная матрица  смежности вершин 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

011

x1

101

A1

=

x2

100

A2

=

x2

101

x3

000

x3

001

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

x1

x2

x3

x1

x2

x3

x1

102

x1

011

A12

=

x2

101

A21

=

x2

011

x3

000

x3

00Поняття фракталів


Построение математических моделей


Приложения определенного интеграла к решению некоторых задач механики и физики


Применение производной при нахождении предела


Применение тригонометрической подстановки для решения алгебраических задач


Актуально: