Реферат: Операции на графах
Операции на графах позволяют образовывать новые графы из нескольких более простых. В этом параграфе будут рассмотрены операции на графах без параллельных ребер (дуг).
Объединение графов .
Пусть 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 |
--> ЧИТАТЬ ПОЛНОСТЬЮ <-- К-во Просмотров: 975
Бесплатно скачать Реферат: Операции на графах
|