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

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

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

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

 Скачать реферат