Реферат на тему Операции на графах
Работа добавлена на сайт bukvasha.net: 2014-12-21Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра информатики
РЕФЕРАТ
На тему:
«Операции на графах»
МИНСК, 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 = {x1, x2, x3, x4}. Составим матрицы смежности вершин вспомогательных графов G’1 и G’2.
Матрица 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.
Составим матрицы смежности вершин исходных графов.
Находим множество вершин X результирующего графа.
X = X1ÇX2 = {x1, x2, x3}.
Составим матрицы смежности вершин вспомогательных графов G’1 и G’2.
Найдем матрицу смежности вершин A = A1 Ç A2
Полученная матрица смежности вершин 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).
Заметим, что дуга (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 = Úa1ikÙa2kj (1)
k=1
где a1ik и a2kj – элементы матрицы смежности вершин первого и второго графов соответственно. Элемент aij равен 1, если в результирующем графе G1(G2) существует дуга, исходящая из вершины xi и заходящая xj, и нулю – в противном случае.
Пример 3. Выполнить операцию композиции для графов, представленных на рис. 3.
Составим матрицы смежности вершин графов:
Вычислив элементы матрицы согласно (1), получаем:
Нетрудно убедиться, что полученным матрицам смежности вершин соответствуют графы G1(G2) и G2(G1), представленные на рис. 3.
Декартово произведение графов. Пусть G1(X,E1) и G2(Y,E2) — два графа. Декартовым произведением G1(X,E1)´G2(Y,E2) графов G1(X,E1) и G2(X,E2) называется граф с множеством вершин X´Y, в котором дуга (ребро), идущая из вершины (xiyj) в (xkyl), существует тогда и только тогда когда существует дуга (xixk), принадлежащая множеству дуг E1 и j = l или когда существует дуга (yj,yl), принадлежащая множеству E2 и i = k.
Выполнение операции декартова произведения рассмотрим на примере графов, изображенных на рис. 4. Множество вершин Z результирующего графа определяется как декартово произведение множеств X´Y. Множество Z содержит следующие элементы: z1=(x1y1), z2=(x1y2), z3=(x1y3), z4=(x2y1), z5=(x2y2), z6=(x2y3).
Определим множество дуг результирующего графа. Для этого выделим группы вершин множества Z, компоненты которых совпадают. В рассматриваемом примере пять таких групп: две группы с совпадающими компонентами из множества X, и три группы, имеющие совпадающие компоненты из Y. Рассмотрим группу вершин результирующего графа, которые имеют общую компоненту x1: z1=(x1y1), z2=(x1y1), z3=(x1y3). Согласно определению операции декартова произведения графов, множество дуг между этими вершинами определяется связями между вершинами множества Y. Таким образом, дуга (y1,y1) в графе G2 определяет наличие дуги (z1,z1) в результирующем графе. Для удобства рассмотрения всех дуг результирующего графа составим таблицу, в первом столбце которой перечисляются вершины с совпадающими компонентами, во втором – дуги между несовпадающими компонентами, а в третьем и четвертом – дуги в результирующем графе.
Кафедра информатики
РЕФЕРАТ
На тему:
«Операции на графах»
МИНСК, 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 | 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 |
| 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 |
Пересечение графов
Пусть 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.
Составим матрицы смежности вершин исходных графов.
| 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 = 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 |
| x1 | x2 | x3 | |||
| x1 | 0 | 0 | 0 | ||
| A’1ÇA’2 | = | x2 | 1 | 0 | 1 |
| x3 | 0 | 0 | 0 |
Композиция графов
Пусть 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 = Úa1ikÙa2kj (1)
k=1
где a1ik и a2kj – элементы матрицы смежности вершин первого и второго графов соответственно. Элемент aij равен 1, если в результирующем графе G1(G2) существует дуга, исходящая из вершины xi и заходящая xj, и нулю – в противном случае.
Пример 3. Выполнить операцию композиции для графов, представленных на рис. 3.
Составим матрицы смежности вершин графов:
| x1 | 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 |
| x1 | x2 | x3 | x1 | x2 | x3 | ||||||
| x1 | 1 | 0 | 2 | x1 | 0 | 1 | 1 | ||||
A12 | = | x2 | 1 | 0 | 1 | A21 | = | x2 | 0 | 1 | 1 |
| x3 | 0 | 0 | 0 | x3 | 0 | 0 | 0 |
Декартово произведение графов. Пусть G1(X,E1) и G2(Y,E2) — два графа. Декартовым произведением G1(X,E1)´G2(Y,E2) графов G1(X,E1) и G2(X,E2) называется граф с множеством вершин X´Y, в котором дуга (ребро), идущая из вершины (xiyj) в (xkyl), существует тогда и только тогда когда существует дуга (xixk), принадлежащая множеству дуг E1 и j = l или когда существует дуга (yj,yl), принадлежащая множеству E2 и i = k.
Выполнение операции декартова произведения рассмотрим на примере графов, изображенных на рис. 4. Множество вершин Z результирующего графа определяется как декартово произведение множеств X´Y. Множество Z содержит следующие элементы: z1=(x1y1), z2=(x1y2), z3=(x1y3), z4=(x2y1), z5=(x2y2), z6=(x2y3).
| № п.п. | Группы вершин с совпадающими компонентами | Дуги для несовпадающих компонент | Дуга (xiyj)®(xkyl) | Дуга (za,zb) |
| 1 | z1=(x1y1), z2=(x1y2), z3=(x1y3) | (y1,y1) (y1,y2) (y2,y3) (y3,y1) | (x1y1)®(x1y1) (x1y1)®(x1y2) (x1y2)®(x1y3) (x1y3)®(x1y1) | (z1,z1) (z1,z2) (z2,z3) (z3,z1) |
| 2 | z4=(x2y1), z5=(x2y2), z6=(x2y3) | (y1,y1) (y1,y2) (y2,y3) (y3,y1) | (x2y1)®(x2y1) (x2y1)®(x2y2) (x2y2)®(x2y3) (x2y3)®(x2y1) | (z4,z4) (z4,z5) (z5,z6) (z6,z4) |
| 3 | z1=(x1y1), z4=(x2y1) | (x1,x2) (x2,x1) | (x1y1)®(x2y1) (x2y1)®(x1y1) | (z1,z4) (z4,z1) |
| 4 | z2=(x1y2), z5=(x2y2) | (x1,x2) (x2,x1) | (x1y2)®(x2y2) (x1y2)®(x1y2) | (z2,z5) (z5,z2) |
| 5 | Z3=(x1y3), z6=(x2y3) | (x1,x2) (x2,x1) | (x1y3)®(x2y3) (x2y3)®(x1y3) | (z3,z6) (z6,z3) |
Граф G1´ G2 изображен на рис. 4.
Операция декартова произведения обладает следующими свойствами.
1. G1´G2 = G2´G1
2. G1´(G2´G3) = (G1´G2)´G3.
Операция декартова произведения графов может быть выполнена в матричной форме.
Пусть G1(X,E1) и G2(Y,E2) – два графа, имеющие nx и ny вершин соответственно. Результирующий граф G1´G2 имеет nx×ny вершин, а его матрица смежности вершин - квадратная матрица размером (nx×ny)´ (nx ×ny). Обозначим через aab = a(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину za=(xiyj) c zb=(xkyl). Согласно определению операции этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:
aab = a(ij)(kl) = Kik×a2,jl Ú Kjl×a1,ik, (2)
где a1,ik, a2,jl – элементы матрицы смежности вершин графов G1 и G2 соответственно;
Kik – символ Кронекера, равный 1, если i=k, и нулю, если i¹k .
Пример 4. Выполнить операцию декартова произведения на графах, приведенных на рис. 4.
Составим матрицы смежности вершин исходных графов.
| x1 | x2 | y1 | y2 | y3 | |||||||
| x1 | 0 | 1 | y1 | 1 | 1 | 0 | |||||
| A1 | = | x2 | 1 | 0 | A2 | = | y2 | 0 | 0 | 1 | |
| y3 | 1 | 0 | 0 | ||||||||
| x1y1 | x1y2 | x1y3 | x2y1 | x2y2 | x2y3 | |||
| x1y1 | XÚY | X | X | Y | 0 | 0 | ||
| x1y2 | X | XÚY | X | 0 | Y | 0 | ||
| Axy | = | X1y3 | X | X | XÚY | 0 | 0 | Y |
| X2y1 | Y | 0 | 0 | XÚY | X | X | ||
| X2y2 | 0 | Y | 0 | X | XÚY | X | ||
| X2y3 | 0 | 0 | Y | X | X | XÚY |
| x1y1 | x1y2 | x1y3 | x2y1 | x2y2 | x2y3 | |||
| x1y1 | a1,11Ú a2,11 | a2,12 | a2,13 | a1,12 | ||||
| x1y2 | a2,21 | a1,11Úa2,22 | a2,11 | a1,12 | ||||
| A* | = | x1y3 | a2,31 | A2,32 | a1,11Úa2,33 | 0 | 0 | a1,12 |
| x2y1 | a1,21 | 0 | 0 | a1,22Úa2,11 | a2,12 | a2,13 | ||
| x2y2 | 0 | a1,21 | 0 | a2,21 | a1,22Úa2,22 | a2,23 | ||
| x2y3 | 0 | 0 | a1,21 | a2,31 | a2,32 | a1,22Ú a2,33 |
Заметим, что в матрицах Axy и A* на главной диагонали располагаются элементы, равные логической сумме значений элементов матриц смежности вершин обоих графов. Это определяется тем, что на главной диагонали расположены элементы, для которых Kik = Kjl = 1.
Таким образом, матрица смежности вершин результирующего графа принимает вид:
| x1y1 | x1y2 | x1y3 | x2y1 | x2y2 | x2y3 | |||
| x1y1 | 1 | 1 | 0 | 1 | 0 | 0 | ||
| x1y2 | 0 | 0 | 1 | 0 | 1 | 0 | ||
| A | = | x1y3 | 1 | 0 | 0 | 0 | 0 | 1 |
| x2y1 | 1 | 0 | 0 | 1 | 1 | 0 | ||
| x2y2 | 0 | 1 | 0 | 0 | 0 | 1 | ||
| x2y3 | 0 | 0 | 1 | 1 | 0 | 0 |
Операция произведения графов. Пусть G1(X,E1) и G2(Y,E2) - два графа. Произведением G1×G2 графов G1 и G2 называется граф с множеством вершин X´Y, а дуга из вершины (xi,yj) в вершину (xk,yl) существует тогда и только тогда, когда существуют дуги (xi,xk) Î E1 и (yj,yl) Î E2.
Выполнение операции произведения рассмотрим на примере графов, изображенных на рис. 5. Множество вершин Z результирующего графа определяется как декартово произведение множеств X´Y. Множество Z содержит следующие элементы: z1=(x1y1), z2=(x1y2), z3=(x1y3), z4=(x2y1), z5=(x2y2), z6=(x2y3).
Определим множество дуг результирующего графа. Для удобства рассмотрения составим таблицу, в первом столбце которой указываются дуги графа G1, во втором – дуги графа G2, а в третьем и четвертом – дуги результирующего графа.
| G1 | G2 | (x1,y1)®(x2,y1) | (za, zb) |
| (x1,x2) | (y1,y1) (y1,y2) (y2,y3) (y3,y2) | (x1,y1)®(x2,y1) (x1,y1)®(x2,y2) (x1,y2)®(x2,y3) (x1,y3)®(x2,y2) | (z1,z4) (z1,z5) (z2,z6) (z3,z5) |
| (x2,x1) | (y1,y1) (y1,y2) (y2,y3) (y3,y2) | (x2,y1)®(x1,y1) (x2,y1)®(x1,y2) (x2,y2)®(x1,y3) (x2,y3)®(x1,y2) | (z4,z1) (z4,z2) (z5,z3) (z6,z2) |
Операция произведения обладает следующими свойствами.
1. G1×G2 = G2×G1.
2. G1×(G2×G3) = (G1×G2)×G3.
Рассмотрим выполнение операции произведения графов в матричной форме.
Пусть G1(X,E1) и G2(Y,E2) – два графа, имеющие nx и ny вершин соответственно. Результирующий граф G1×G2 имеет nx×ny вершин, а его матрица смежности вершин - квадратная матрица размером (nx×ny)´ (nx ×ny). Обозначим через aab = a(ij)(kl) элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину za=(xiyj) c zb=(xkyl). Этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:
aab =a(ij)(kl) = a1,ik Ù a2,jl, (3)
де a1,ik, a1,ik – элементы матрицы смежности вершин графов G1 и G2 соответственно.
Пример 5. Выполнить операцию произведения на графах, приведенных на рис. 5.
Составим матрицы смежности вершин исходных графов.
| x1 | x2 | y1 | y2 | y3 | |||||||
| x1 | 0 | 1 | y1 | 1 | 1 | 0 | |||||
| A1 | = | x2 | 1 | 0 | A2 | = | y2 | 0 | 0 | 1 | |
| y3 | 0 | 1 | 0 | ||||||||
| x1y1 | x1y2 | x1y3 | x2y1 | x2y2 | x2y3 | |||
| x1y1 | a1,11Ù a2,11 | a1,11Ùa2,12 | a1,11Ù a2,13 | a1,12Ùa2,11 | a1,12Ù a2,12 | a1,12Ù a2,13 | ||
| x1y2 | a1,11Ù a2,21 | a1,11Ù a2,22 | a1,11Ù a2,23 | a1,12Ù a2,21 | a1,12Ù a2,22 | a1,12Ù a2,23 | ||
| A | = | x1y3 | a1,11Ù a2,21 | a1,11Ù a2,22 | a1,11Ù a2,23 | a1,12Ù a2,31 | a1,12Ù a2,32 | a1,12Ù a2,33 |
| x2y1 | a1,21Ù a2,11 | a1,21Ù a2,12 | a1,21Ù a2,13 | a1,22Ù a2,11 | a1,22Ù a2,12 | a1,22Ù a2,13 | ||
| x2y2 | a1,21Ù a2,21 | a1,21Ù a2,22 | a1,21Ù a2,23 | a1,12Ù a2,21 | a1,12Ù a2,22 | A1,12Ù a2,23 | ||
| x2y3 | a1,21Ù a2,31 | a1,21Ù a2,32 | a1,21Ù a2,33 | a1,22Ù a2,31 | a1,12Ù a2,32 | A1,12Ù a2,33 |
| x1y1 | x1y2 | x1y3 | x2y1 | x2y2 | x2y3 | |||
| x1y1 | a1,11ÙA2 | a1,12ÙA2 | ||||||
| x1y2 | ||||||||
| A | = | x1y3 | ||||||
| x2y1 | a1,21ÙA2 | a1,22ÙA2 | ||||||
| x2y2 | ||||||||
| x2y3 | ||||||||
| x1y1 | x1y2 | x1y3 | x2y1 | x2y2 | x2y3 | |||
| x1y1 | 0 | 0 | 0 | 1 | 1 | 0 | ||
| x1y2 | 0 | 0 | 0 | 0 | 0 | 1 | ||
| A | = | x1y3 | 0 | 0 | 0 | 0 | 1 | 0 |
| x2y1 | 1 | 1 | 0 | 0 | 0 | 0 | ||
| x2y2 | 0 | 0 | 1 | 0 | 0 | 0 | ||
| x2y3 | 0 | 1 | 0 | 0 | 0 | 0 |
ЛИТЕРАТУРА
1. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана, 2001.– 744 с. (Сер. Математика в техническом университете; Вып XIX).
2. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.– М.: Наука, Физматлит, 2000.– 544 с.– ISBN 5-02-015238-2.
3. Зарубин В.С. Математическое моделирование в технике: Учеб. для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.– 496 с. (Сер. Математика в техническом университете; вып. XXI, заключительный).
