Операции на графах (стр. 1 из 5)
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра информатики
РЕФЕРАТ
На тему:
«Операции на графах»
МИНСК, 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’1ÈA’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 = A1ÇA2 образованная поэлементным логически умножением матриц A1 и A2.