Операции на графах БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ Кафедра информатики На тему: «Операции на графах» МИНСК, 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 x 1 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= Æ ) . Пустой граф обозначается символом Æ . Такой граф может быть получен в результате выполнения операции пересечения графов, у которых X 1 Ç X 2 = Æ . В этом случае говорят о непересекающихся графах. Рассмотрим выполнение операции пересечения графов, изображенных на рис. 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 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’1 Ç A’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 = Ú a 1 ik Ù a 2 kj (1) k =1 где a1ik и a2kj – элементы матрицы смежности вершин первого и второго графов соответственно. Элемент aij равен 1, если в результирующем графе G1 (G2 ) существует дуга, исходящая из вершины xi и заходящая xj , и нулю – в противном случае. Пример 3. Выполнить операцию композиции для графов, пред­ставленных на рис. 3. Составим матрицы смежности вершин графов: x 1 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