Реферат: Операции на графах

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

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

РЕФЕРАТ

На тему:

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

МИНСК, 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 _{1 ik} Ù a _{2 kj} (1)

^{k =1}

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

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

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

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

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

Декартово произведение графов. Пусть G₁ (X,E₁ ) и G₂ (Y,E₂ ) — два графа. Декартовым произведением G₁ (X,E₁ ) ´ G₂ ( Y ,E₂ ) графов G₁ (X,E₁ ) и G₂ (X,E₂ ) называется граф с множеством вершин X ´ Y , в котором дуга (ребро), идущая из вершины (x_i y_j ) в (x_k y_l ) , существует тогда и только тогда когда существует дуга (x_i x_k ) , принадлежащая множеству дуг E₁ и j = l или когда существует дуга (y_j ,y_l ) , принадлежащая множеству E₂ и i = k .

Выполнение операции декартова произведения рассмотрим на примере графов, изображенных на рис. 4. Множество вершин Z результирующего графа определяется как декартово произведение множеств X ´ Y . Множество Z содержит следующие элементы: z₁ =(x₁ y₁ ), z₂₌ (x₁ y₂ ), z₃ =(x₁ y₃ ), z₄ =(x₂ y₁ ), z₅ =(x₂ y₂ ), z₆ =(x₂ y₃ ) .

Определим множество дуг результирующего графа. Для этого выделим группы вершин множества Z, компоненты которых совпадают. В рассматриваемом примере пять таких групп: две группы с совпадающими компонентами из множества X , и три группы, имеющие совпадающие компоненты из Y . Рассмотрим группу вершин результирующего графа, которые имеют общую компоненту x₁ : z₁ =(x₁ y₁ ), z₂₌ (x₁ y₁ ), z₃ =(x₁ y₃ ). Согласно определению операции декартова произведения графов, множество дуг между этими вершинами определяется связями между вершинами множества Y . Таким образом, дуга (y₁ ,y₁ ) в графе G2 определяет наличие дуги (z₁ ,z₁ ) в результирующем графе. Для удобства рассмотрения всех дуг результирующего графа составим таблицу, в первом столбце которой перечисляются вершины с совпадающими компонентами, во втором – дуги между несовпадающими компонентами, а в третьем и четвертом – дуги в результирующем графе.

Граф G₁ ´ G₂ изображен на рис. 4.

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

1. G₁ ´ G₂ = G₂ ´ G₁

2. G₁ ´ (G₂ ´ G₃ ) = (G₁ ´ G₂ ) ´ G₃ .

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

Пусть G₁ (X,E₁ ) и G₂ (Y,E₂ ) – два графа, имеющие n_x и n_y вершин соответственно. Результирующий граф G₁ ´ G₂ имеет n_x × n_y вершин, а его матрица смежности вершин - квадратная матрица размером (n_x × n_y ) ´ (n_x × n_y ) . Обозначим через a _{a b} = a_(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z _a =(x_i y_j ) c z _b =(x_k y_l ) . Согласно определению операции этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:

a _{a b} = a_(ij)(kl) = K_ik × a_2,jl Ú K_jl × a_1,ik , (2)

где a_1,ik , a_2,jl – элементы матрицы смежности вершин графов G₁ и G₂ соответственно;

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

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

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

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

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

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

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

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

Операция произведения графов. Пусть G₁ (X,E₁ ) и G₂ (Y,E₂ ) - два графа. Произведением G₁ × G₂ графов G₁ и G₂ называется граф с множеством вершин X ´ Y , а дуга из вершины (x_i ,y_j ) в вершину (x_k ,y_l ) существует тогда и только тогда, когда существуют дуги (x_i ,x_k ) Î E₁ и (y_j ,y_l ) Î E₂ .

Выполнение операции произведения рассмотрим на примере графов, изображенных на рис. 5. Множество вершин Z результирующего графа определяется как декартово произведение множеств X ´ Y . Множество Z содержит следующие элементы: z₁ =(x₁ y₁ ), z₂₌ (x₁ y₂ ), z₃ =(x₁ y₃ ), z₄ =(x₂ y₁ ), z₅ =(x₂ y₂ ), z₆ =(x₂ y₃ ) .

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

Результирующий граф G_{1 ×} G₂ изображен на рис.5.

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

1. G₁ × G₂ = G₂ × G₁ .

2. G₁ × (G₂ × G₃ ) = (G₁ × G₂ ) × G₃ .

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

Пусть G₁ (X,E₁ ) и G₂ (Y,E₂ ) – два графа, имеющие n_x и n_y вершин соответственно. Результирующий граф G₁ × G₂ имеет n_x × n_y вершин, а его матрица смежности вершин - квадратная матрица размером (n_x × n_y ) ´ (n_x × n_y ) . Обозначим через a _{a b} = a_(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z _a =(x_i y_j ) c z _b =(x_k y_l ) . Этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:

a _{a b} =a_(ij)(kl) = a_1,ik Ù a_2,jl , (3)

де a_1,ik , a_1,ik – элементы матрицы смежности вершин графов G₁ и G₂ соответственно.

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

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

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

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

Таким образом, матрица смежности вершин графа G₁ × G ₂ имеет вид:

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

ЛИТЕРАТУРА

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

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

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