Операции на графах
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра информатики
РЕФЕРАТ
На тему:
«Операции на графах»
МИНСК, 2008
Операции на графах позволяют образовывать новые графы из нескольких более простых. В этом параграфе будут рассмотрены операции на графах без параллельных ребер (дуг).
Объединение графов.
Пусть G>1>(X>1>,E>1>) и G>2>(X>2>,E>2>) – произвольные графы. Объединением G>1>G>2> графов G>1> и G>2> называется граф с множеством вершин X>1>X>2>, и с множеством ребер (дуг) E>1>E>2>>.>
Рассмотрим операцию на примере графов G>1>(X>1>,E>1>) и G>2>(X>2>,E>2>), приведенных на рис. 4.1. Множества вершин первого и второго графов соответственно равны X>1> = {x>1>, x>2>, x>3>} и X>2> = {x>2>, x>3>, x>4>}, а множество вершин результирующего графа определится как X = X>1>X>2 >= {x>1>, x>2>, x>3>, x>4>}. Аналогично определяем множества дуг графа:
E>1> = {(x>1>, x>2>), (x>1>, x>3>), (x>2>, x>1>), (x>3>, x>3>)}. E>2> = {(x>2>, x>4>), (x>3>, x>2>)>, >(x>4>, x>2>)}.
E = {(x>1>, x>2>), (x>1>, x>3>), (x>2>, x>1>), (x>3>, x>3>), (x>2>, x>4>), (x>3>, x>2>)>, >(x>4>, x>2>)}.
Результирующий граф G(X,E) = G>1>(X>1>,E>1>)G>2>(X>2>,E>2>) также приведен на рис. 1.
Операция объединения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:
G>1>G>2> = G>2>G>1> – свойство коммутативности;
G>1>(G>2>G>3>) > >= (G>1>G>2>)G>3> – свойство ассоциативности.
Операция объединения графов может быть выполнена в матричной форме. Для графов с одним и тем же множеством вершин справедлива следующая теорема.
Теорема 1. Пусть G>1> и G>2> – два графа (ориентированные или не ориентированные одновременно) с одним и тем же множеством вершин X, и пусть A>1> и A>2> – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G>1>G>2 > является матрица A = A>1>A>2>, образованная поэлементным логическим сложением матриц A>1> и A>2>.
Рассмотрим выполнение операции объединения графов, множества вершин которых не совпадают. Пусть G>1>(X>1>,E>1>) и G>2>(X>2>,E>2>) – графы без параллельных ребер и множества X>1> и X>2> вершин этих графов не совпадают. Пусть A>1> и A>2> – матрицы смежности их вершин графов. Для таких графов операция объединения может быть выполнена следующим образом.
В соответствии с определением операции объединения графов найдем множество вершин результирующего графа как X>1>X>2>. Построим вспомогательные графы G’>1> и G’>2>, множества вершин которых есть множество X>1>X>2>, а множество ребер (дуг) определяется множествами E>1> для графа G’>1> и E>2> для графа G’>2>. Очевидно, что матрицы A’>1> и A’>2> смежности вершин этих графов могут быть получены из матриц A>1> и A>2> путем добавления в них дополнительных столбцов и строк с нулевыми элементами.
Применив к графам G’>1> и G’>2> теорему 4.1, найдем матрицу смежности вершин графа G’>1>G’>2> как A’>1>A’>2>. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно X>1>X>2>, а множество ребер определяется, как E>1>E>2>, что соответствует операции объединения графов.
Пример 1. Выполнить в матричной форме операцию объединения графов G>1> и G>2>, представленных на рис. 1.
Составим матрицы смежности вершин графов.
|
x>1> |
x>2> |
x>3> |
x>2> |
x>3> |
x>4> |
||||||
|
x>1> |
0 |
1 |
1 |
x>2> |
0 |
0 |
1 |
||||
|
A>1> |
= |
x>2> |
1 |
0 |
0 |
A>2> |
= |
x>3> |
1 |
0 |
0 |
|
x>3> |
0 |
0 |
1 |
x>4> |
0 |
1 |
0 |
Множество вершин результирующего графа X>1>X>2> = {x>1>, x>2>, x>3>, x>4>}. Составим матрицы смежности вершин вспомогательных графов G’>1> и G’>2>.
|
x>1> |
x>2> |
x>3> |
x>4> |
x>1> |
x>2> |
x>3> |
x>4> |
||||||
|
x>1> |
0 |
1 |
1 |
0 |
x>1> |
0 |
0 |
0 |
0 |
||||
|
A’>1> |
= |
x>2> |
1 |
0 |
0 |
0 |
A’>2> |
= |
x>2> |
0 |
0 |
0 |
1 |
|
x>3> |
0 |
0 |
1 |
0 |
x>3> |
0 |
1 |
0 |
0 |
||||
|
x>4> |
0 |
0 |
0 |
0 |
x>4> |
0 |
0 |
1 |
0 |
Матрица A = A’>1>A’>2>> >имеет вид
|
X>1> |
x>2> |
x>3> |
x>4> |
|||
|
x>1> |
0 |
1 |
1 |
0 |
||
|
x>2> |
1 |
0 |
0 |
1 |
||
|
A = A’>1>A’>2> |
= |
x>3> |
0 |
1 |
1 |
0 |
|
x>4> |
0 |
0 |
1 |
0 |
Полученная матрица смежности вершин A’>1> A’>2> соответствует графу G>1>G>2>, изображенному на рис.1.
Пересечение графов
Пусть G>1>(X>1>,E>1>) и G>2>(X>2>,E>2>) – произвольные графы. Пересечением G>1>G>2> графов G>1> и G>2> называется граф с множеством вершин X>1>X>2> с множеством ребер (дуг) E = E>1>E>2>
Операция пересечения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:
G>1>G>2> = G>2>G>1>– свойство коммутативности;
G>1> (G2G3) > >= (G1G2) G>3> – свойство ассоциативности.> >
Для того чтобы операция пересечения была всеобъемлющей, необходимо ввести понятие пустого графа. Граф G(X,E) называется пустым, если множество X вершин графа является пустым (X=). Заметим, что в этом случае и множество E ребер (дуг) графа также пустое множество (E=). Пустой граф обозначается символом . Такой граф может быть получен в результате выполнения операции пересечения графов, у которых X>1>X>2>=. В этом случае говорят о непересекающихся графах.
Рассмотрим выполнение операции пересечения графов, изображенных на рис. 2. Для нахождения множества вершин результирующего графа запишем множества вершин исходных графов и выполним над этими множествами операцию пересечения:
X>1> = {x>1>, x>2>, x>3>}; X>2> = {x>1>, x>2>, x>3>, x>4>};
X = X>1>X>2> = {x>1>, x>2>, x>3>}.
Аналогично определяем множество E дуг результирующего графа:
E>1> = {(x>1>, x>2>), (x>1>, x>3>), (x>2>, x>1>), (x>2>, x>3>), (x>3>, x>2>)};
E>2> = {(x>1>, x>3>), (x>2>, x>1>), (x>2>, x>3>), (x>2>, x>4>), (x>3>, x>1>)};
E = E>1>E>2> = {(x>1>, x>3>), (x>2>, x>1>)}.
Графы G>1>(X>1>,E>1>), G>2>(X>2>,E>2>) и их пересечение приведены на рис 4.2.
Операция пересечения графов может быть выполнена в матричной форме.
Теорема 2. Пусть G>1> и G>2> – два графа (ориентированные или неориентированные одновременно) с одним и тем же множеством вершин X, и пусть A>1> и A>2> – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1G2> > является матрица A = A>1>A>2> образованная поэлементным логически умножением матриц A>1> и A>2>.
Рассмотрим выполнение операции пересечения для графов с несовпадающим множеством вершин.
Пусть G>1>(X>1>,E>1>) и G>2>(X>2>,E>2>) – графы без параллельных ребер, множества X>1> и X>2> вершин графов не совпадают, а A>1> и A>2> – матрицы смежности вершин графов. Для таких графов операция пересечения может быть выполнена так.
В соответствии с определением операции пересечения графов найдем множество вершин результирующего графа как X>1>X>2>. Построим вспомогательные графы G’>1> и G’>2>, множества вершин которых есть множество X>1>X>2>, а множество ребер (дуг) определяется множествами E’>1> и E’>2> всех ребер (дуг), инцидентных этим вершинам. Очевидно, что матрицы A’>1> и A’>2> смежности вершин этих графов могут быть получены из матриц A>1> и A>2> путем удаления из них столбцов и строк, соответствующих вершинам, не вошедшим во множество X1X2.
Применив к графам G’>1> и G’>2> теорему 2, найдем матрицу смежности вершин графа G’>1>G’>2> как A’>1>A’>2>. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно X>1>X>2>, а множество ребер определяется, как E>1>E>2>, что соответствует операции пересечения графов.
Пример 2. Выполнить в матричной форме операцию пересечения графов G>1> и G>2>, представленных на рис. 2.
Составим матрицы смежности вершин исходных графов.
|
x>1> |
x>2> |
x>3> |
x>1> |
x>2> |
x>3> |
x>4> |
||||||
|
x>1> |
0 |
1 |
1 |
x>1> |
0 |
0 |
0 |
1 |
||||
|
A>1> |
= |
x>2> |
1 |
0 |
1 |
A>2> |
= |
x>2> |
1 |
0 |
1 |
1 |
|
x>3> |
0 |
1 |
0 |
x>3> |
1 |
0 |
0 |
0 |
||||
|
x>4> |
0 |
0 |
0 |
0 |
Находим множество вершин X результирующего графа.
X = X>1>X>2> = {x>1>, x>2>, x>3>}.
Составим матрицы смежности вершин вспомогательных графов G’>1> и G’>2>.
|
x>1> |
x>2> |
x>3> |
x>1> |
x>2> |
x>3> |
||||||
|
x>1> |
0 |
1 |
1 |
x>1> |
0 |
0 |
0 |
||||
|
A’>1> |
= |
x>2> |
1 |
0 |
1 |
A’>2> |
= |
x>2> |
1 |
0 |
1 |
|
x>3> |
0 |
1 |
0 |
x>3> |
1 |
0 |
0 |
Найдем матрицу смежности вершин A = A>1 > A>2>
|
x>1> |
x>2> |
x>3> |
|||
|
x>1> |
0 |
0 |
0 |
||
|
A’>1>A’>2> |
= |
x>2> |
1 |
0 |
1 |
|
x>3> |
0 |
0 |
0 |
Полученная матрица смежности вершин A’>1> A’>2> соответствует графу G>1>G>2>, изображенному на рис.2.
Композиция графов
Пусть G>1>(X,E>1>) и G>2>(X,E>2>) — два графа с одним и тем же множеством вершин X. Композицией G>1>(G>2>) графов G>1> и G>2> называется граф с множеством вершин E, в котором существует дуга (x>i>,x>j>) тогда и только тогда, когда существует дуга (x>i>,x>k>), принадлежащая множеству E>1>, и дуга (x>k>,x>j>), принадлежащая множеству E>2>.
Рассмотрим выполнение операции композиции G>1>(G>2>) на графах, изображенных на рис.3. Для рассмотрения операции составим таблицу, в первом столбце которой указываются ребра (x>i>, x>k>), принадлежащие графу G>1>, во втором — ребра (x>k>, x>j>), принадлежащие графу G>3>, а в третьем — результирующее ребро (x>i>, x>j>) для графа G>1>(G>2>).
|
G>1> |
G>2> |
G>1>(G>2>) |
|
(x>1>,x>2>) |
(x>2>,x>1>) (x>2>,x>3>) |
(x>1>,x>1>) (x>1>,x>3>) |
|
(x>1>,x>3>) |
(x>3>,x>3>) |
(x>1>,x>3>) |
|
(x>2>,x>1>) |
(x>1>,x>1>) (x>1>,x>3>) |
(x>2>,x>1>) (x>2>,x>3>) |
Заметим, что дуга (x>1>,x>3>) результирующего графа в таблице встречается дважды. Однако, поскольку рассматриваются графы без параллельных ребер (дуг), то в множестве E результирующего графа дуга (x>1>,x>3>) учитывается только один раз, т.е. E = {(x>1>,x>1>), (x>1>,x>3>), (x>2>,x>1>), (x>2>,x>3>)}
На рис. 3 изображены графы G>1> и G>2> и их композиции G>1>(G>2>). На этом же рисунке изображен граф G>2>(G>1>). Рекомендуется самостоятельно построить граф G>2>(G>1>) и убедиться, что графы G>1>(G>2>) и G>2>(G>1>) не изоморфны.
Пусть А>1> и A>2> – матрицы смежности вершин графов G>1>(X,E>1>) и G(X,E>2>) соответственно. Рассмотрим матрицу A>12> элементы a>ij> которой вычисляется так:
>n>
a>ij>> >= a>1>>ik>a>2>>kj>> >(1)
> >k=1
где a>1ik> и a>2kj >– элементы матрицы смежности вершин первого и второго графов соответственно. Элемент a>ij> равен 1, если в результирующем графе G>1>(G>2>) существует дуга, исходящая из вершины x>i> и заходящая x>j>, и нулю – в противном случае.
Пример 3. Выполнить операцию композиции для графов, представленных на рис. 3.
Составим матрицы смежности вершин графов:
|
x>1> |
x>2> |
x>3> |
x>1> |
x>2> |
x>3> |
||||||
|
x>1> |
0 |
1 |
1 |
x>1> |
1 |
0 |
1 |
||||
|
A>1> |
= |
x>2> |
1 |
0 |
0 |
A>2> |
= |
x>2> |
1 |
0 |
1 |
|
x>3> |
0 |
0 |
0 |
x>3> |
0 |
0 |
1 |
Вычислив элементы матрицы согласно (1), получаем:
|
x>1> |
x>2> |
x>3> |
x>1> |
x>2> |
x>3> |
||||||
|
x>1> |
1 |
0 |
2 |
x>1> |
0 |
1 |
1 |
||||
A>12> |
= |
x>2> |
1 |
0 |
1 |
A>21> |
= |
x>2> |
0 |
1 |
1 |
|
x>3> |
0 |
0 |
0 |
x>3> |
0 |
0 |
0 |
Нетрудно убедиться, что полученным матрицам смежности вершин соответствуют графы G>1>(G>2>) и G>2>(G>1>), представленные на рис. 3.
Декартово произведение графов. Пусть G>1>(X,E>1>) и G>2>(Y,E>2>) — два графа. Декартовым произведением G>1>(X,E>1>)G>2>(Y,E>2>) графов G>1>(X,E>1>) и G>2>(X,E>2>) называется граф с множеством вершин XY, в котором дуга (ребро), идущая из вершины (x>i>y>j>) в (x>k>y>l>), существует тогда и только тогда когда существует дуга (x>i>x>k>), принадлежащая множеству дуг E>1> и j = l или когда существует дуга (y>j>,y>l>), принадлежащая множеству E>2> и i = k.
Выполнение операции декартова произведения рассмотрим на примере графов, изображенных на рис. 4. Множество вершин Z результирующего графа определяется как декартово произведение множеств XY. Множество Z содержит следующие элементы: z>1>=(x>1>y>1>), z>2=>(x>1>y>2>), z>3>=(x>1>y>3>), z>4>=(x>2>y>1>), z>5>=(x>2>y>2>), z>6>=(x>2>y>3>).
Определим
множество дуг результирующего графа.
Для этого выделим группы вершин множества
Z, компоненты
которых совпадают. В рассматриваемом
примере пять таких групп: две группы с
совпадающими компонентами из множества
X, и три группы,
имеющие совпадающие компоненты из Y.
Рассмотрим группу вершин результирующего
графа, которые имеют общую компоненту
x>1>:
z>1>=(x>1>y>1>),
z>2=>(x>1>y>1>),
z>3>=(x>1>y>3>).
Согласно определению операции декартова
произведения графов, множество дуг
между этими вершинами определяется
связями между вершинами множества Y.
Таким образом, дуга (y>1>,y>1>)
в графе G2
определяет наличие дуги (z>1>,z>1>)
в результирующем графе. Для удобства
рассмотрения всех дуг результирующего
графа составим таблицу, в первом столбце
которой перечисляются вершины с
совпадающими компонентами, во втором
– дуги между несовпадающими компонентами,
а в третьем и четвертом – дуги в
результирующем графе.
|
№ п.п. |
Группы вершин с совпадающими компонентами |
Дуги для несовпадающих компонент |
Дуга (x>i>y>j>)(x>k>y>l>) |
Дуга (z>>,z>>) |
|
1 |
z>1>=(x>1>y>1>), z>2=>(x>1>y>2>), z>3>=(x>1>y>3>) |
(y>1>,y>1>) (y>1>,y>2>) (y>2>,y>3>) (y>3>,y>1>) |
(x>1>y>1>)(x>1>y>1>) (x>1>y>1>)(x>1>y>2>) (x>1>y>2>)(x>1>y>3>) (x>1>y>3>)(x>1>y>1>) |
(z>1>,z>1>) (z>1>,z>2>) (z>2>,z>3>) (z>3>,z>1>) |
|
2 |
z>4>=(x>2>y>1>), z>5>=(x>2>y>2>), z>6>=(x>2>y>3>) |
(y>1>,y>1>) (y>1>,y>2>) (y>2>,y>3>) (y>3>,y>1>) |
(x>2>y>1>)(x>2>y>1>) (x>2>y>1>)(x>2>y>2>) (x>2>y>2>)(x>2>y>3>) (x>2>y>3>)(x>2>y>1>) |
(z>4>,z>4>) (z>4>,z>5>) (z>5>,z>6>) (z>6>,z>4>) |
|
3 |
z>1>=(x>1>y>1>), z>4>=(x>2>y>1>) |
(x>1>,x>2>) (x>2>,x>1>) |
(x>1>y>1>)(x>2>y>1>) (x>2>y>1>)(x>1>y>1>) |
(z>1>,z>4>) (z>4>,z>1>) |
|
4 |
z>2=>(x>1>y>2>), z>5>=(x>2>y>2>) |
(x>1>,x>2>) (x>2>,x>1>) |
(x>1>y>2>)(x>2>y>2>) (x>1>y>2>)(x>1>y>2>) |
(z>2>,z>5>) (z>5>,z>2>) |
|
5 |
Z>3>=(x>1>y>3>), z>6>=(x>2>y>3>) |
(x>1>,x>2>) (x>2>,x>1>) |
(x>1>y>3>)(x>2>y>3>) (x>2>y>3>)(x>1>y>3>) |
(z>3>,z>6>) (z>6>,z>3>) |
Граф G>1> G>2> изображен на рис. 4.
Операция декартова произведения обладает следующими свойствами.
1. G>1>G>2> = G>2>G>1>
2. G>1>(G>2>G>3>) => > (G>1>G>2>)G>3>.
Операция декартова произведения графов может быть выполнена в матричной форме.
Пусть G>1>(X,E>1>) и G>2>(Y,E>2>) – два графа, имеющие n>x>> >и n>y>> >вершин соответственно. Результирующий граф G>1>G>2>> >имеет n>x>n>y>> >вершин, а его матрица смежности вершин - квадратная матрица размером (n>x>n>y>) (n>x >n>y>). Обозначим через a>> = a>(ij)(kl)> элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z>>=(x>i>y>j>) c z>>=(x>k>y>l>). Согласно определению операции этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:
a>> = a>(ij)(kl)> = K>ik>a>2,jl> K>jl>a>1,ik>, (2)
где a>1,ik>, a>2,jl> – элементы матрицы смежности вершин графов G>1> и G>2> соответственно;
K>ik>> >– символ Кронекера, равный 1, если i=k, и нулю, если ik .
Пример 4. Выполнить операцию декартова произведения на графах, приведенных на рис. 4.
Составим матрицы смежности вершин исходных графов.
|
x>1> |
x>2> |
y>1> |
y>2> |
y>3> |
||||||
|
x>1> |
0 |
1 |
y>1> |
1 |
1 |
0 |
||||
|
A>1> |
= |
x>2> |
1 |
0 |
A>2> |
= |
y>2> |
0 |
0 |
1 |
|
y>3> |
1 |
0 |
0 |
Для построения матрицы смежности результирующего графа воспользуемся соотношением (2). В этом соотношении первое слагаемое K>ik>a>2,jl> указывает на наличие дуг для вершин, у которых совпадают компоненты из множества X. Для пояснения сказанного, рассмотрим вспомогательную матрицу Axy, в которой элементы, для которых K>ik> = 1, помечены символом X. Эти элементы принимают значения, равные значениям соответствующих элементов матрицы A>2> смежности вершин графа G>2>, так, как это показано для матрицы A*.
|
x>1>y>1> |
x>1>y>2> |
x>1>y>3> |
x>2>y>1> |
x>2>y>2> |
x>2>y>3> |
|||
|
x>1>y>1> |
XY |
X |
X |
Y |
0 |
0 |
||
|
x>1>y>2> |
X |
XY |
X |
0 |
Y |
0 |
||
|
Axy |
= |
X>1>y>3> |
X |
X |
XY |
0 |
0 |
Y |
|
X>2>y>1> |
Y |
0 |
0 |
XY |
X |
X |
||
|
X>2>y>2> |
0 |
Y |
0 |
X |
XY |
X |
||
|
X>2>y>3> |
0 |
0 |
Y |
X |
X |
XY |
|
x>1>y>1> |
x>1>y>2> |
x>1>y>3> |
x>2>y>1> |
x>2>y>2> |
x>2>y>3> |
|||
|
x>1>y>1> |
a>1,11> a>2,11> |
a>2,12> |
a>2,13> |
a>1,12> |
||||
|
x>1>y>2> |
a>2,21> |
a>1,11>a>2,22> |
a>2,11> |
a>1,12> |
||||
|
A* |
= |
x>1>y>3> |
a>2,31> |
A>2,32> |
a>1,11>a>2,33> |
0 |
0 |
a>1,12> |
|
x>2>y>1> |
a>1,21> |
0 |
0 |
a>1,22>a>2,11> |
a>2,12> |
a>2,13> |
||
|
x>2>y>2> |
0 |
a>1,21> |
0 |
a>2,21> |
a>1,22>a>2,22> |
a>2,23> |
||
|
x>2>y>3> |
0 |
0 |
a>1,21> |
a>2,31> |
a>2,32> |
a>1,22>> >a>2,33> |
Второе слагаемое K>jl>a>1,ik> соотношения (2) указывает на наличие дуг для групп вершин, у которых совпадают компоненты из множества Y. В матрице Axy элементы, для которых K>jl> = 1 помечены символом Y. Эти элементы принимают значения, равные значениям соответствующих элементов матрицы A>1> смежности вершин графа G>1>, так, как это показано для матрицы A*.
Заметим, что в матрицах Axy и A* на главной диагонали располагаются элементы, равные логической сумме значений элементов матриц смежности вершин обоих графов. Это определяется тем, что на главной диагонали расположены элементы, для которых K>ik> = K>jl >= 1.
Таким образом, матрица смежности вершин результирующего графа принимает вид:
|
x>1>y>1> |
x>1>y>2> |
x>1>y>3> |
x>2>y>1> |
x>2>y>2> |
x>2>y>3> |
|||
|
x>1>y>1> |
1 |
1 |
0 |
1 |
0 |
0 |
||
|
x>1>y>2> |
0 |
0 |
1 |
0 |
1 |
0 |
||
|
A |
= |
x>1>y>3> |
1 |
0 |
0 |
0 |
0 |
1 |
|
x>2>y>1> |
1 |
0 |
0 |
1 |
1 |
0 |
||
|
x>2>y>2> |
0 |
1 |
0 |
0 |
0 |
1 |
||
|
x>2>y>3> |
0 |
0 |
1 |
1 |
0 |
0 |
Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф G>1>G>2>, представленный на рис. 4
Операция произведения графов. Пусть G>1>(X,E>1>) и G>2>(Y,E>2>) - два графа. Произведением G>1>G>2> графов G>1> и G>2> называется граф с множеством вершин XY, а дуга из вершины (x>i>,y>j>) в вершину (x>k>,y>l>) существует тогда и только тогда, когда существуют дуги (x>i>,x>k>) E>1> и (y>j>,y>l>) E>2>.
Выполнение операции произведения рассмотрим на примере графов, изображенных на рис. 5. Множество вершин Z результирующего графа определяется как декартово произведение множеств XY. Множество Z содержит следующие элементы: z>1>=(x>1>y>1>), z>2=>(x>1>y>2>), z>3>=(x>1>y>3>), z>4>=(x>2>y>1>), z>5>=(x>2>y>2>), z>6>=(x>2>y>3>).
Определим множество дуг результирующего графа. Для удобства рассмотрения составим таблицу, в первом столбце которой указываются дуги графа G>1>, во втором – дуги графа G>2>, а в третьем и четвертом – дуги результирующего графа.
|
G>1> |
G>2> |
(x>1,>y>1>)(x>2>,y>1>) |
(z>>, z>>) |
|
(x>1>,x>2>) |
(y>1>,y>1>) (y>1>,y>2>) (y>2>,y>3>) (y>3>,y>2>) |
(x>1,>y>1>)(x>2>,y>1>) (x>1,>y>1>)(x>2>,y>2>) (x>1,>y>2>)(x>2>,y>3>) (x>1,>y>3>)(x>2>,y>2>) |
(z>1,>z>4>) (z>1,>z>5>) (z>2,>z>6>) (z>3,>z>5>) |
|
(x>2>,x>1>) |
(y>1>,y>1>) (y>1>,y>2>) (y>2>,y>3>) (y>3>,y>2>) |
(x>2,>y>1>)(x>1>,y>1>) (x>2,>y>1>)(x>1>,y>2>) (x>2,>y>2>)(x>1>,y>3>) (x>2,>y>3>)(x>1>,y>2>) |
(z>4,>z>1>) (z>4,>z>2>) (z>5,>z>3>) (z>6,>z>2>) |
Результирующий граф G>1>>>G>2> изображен на рис.5.
Операция произведения обладает следующими свойствами.
1. G>1>G>2> = G>2>G>1>.
2. G>1>(G>2>G>3>) > >= (G>1>G>2>)G>3>.
Рассмотрим выполнение операции произведения графов в матричной форме.
Пусть G>1>(X,E>1>) и G>2>(Y,E>2>) – два графа, имеющие n>x>> >и n>y>> >вершин соответственно. Результирующий граф G>1>G>2>> >имеет n>x>n>y>> >вершин, а его матрица смежности вершин - квадратная матрица размером (n>x>n>y>) (n>x >n>y>). Обозначим через a>>> >= a>(ij)(kl)> элемент матрицы смежности вершин, указывающий на наличие дуги (ребра), соединяющей вершину z>>=(x>i>y>j>) c z>>=(x>k>y>l>). Этот элемент может быть вычислен при помощи матриц смежности вершин исходных графов следующим образом:
a>>> >=a>(ij)(kl)> = a>1,ik > a>2,jl>, (3)
де a>1,ik>, a>1,ik> – элементы матрицы смежности вершин графов G>1> и G>2 >соответственно.
Пример 5. Выполнить операцию произведения на графах, приведенных на рис. 5.
Составим матрицы смежности вершин исходных графов.
|
x>1> |
x>2> |
y>1> |
y>2> |
y>3> |
||||||
|
x>1> |
0 |
1 |
y>1> |
1 |
1 |
0 |
||||
|
A>1> |
= |
x>2> |
1 |
0 |
A>2> |
= |
y>2> |
0 |
0 |
1 |
|
y>3> |
0 |
1 |
0 |
Построим матрицу A смежности вершин результирующего графа, каждый элемент которой вычисляется согласно соотношению (4.3).
|
x>1>y>1> |
x>1>y>2> |
x>1>y>3> |
x>2>y>1> |
x>2>y>2> |
x>2>y>3> |
|||
|
x>1>y>1> |
a>1,11> a>2,11> |
a>1,11>a>2,12> |
a>1,11> a>2,13> |
a>1,12>a>2,11> |
a>1,12> a>2,12> |
a>1,12> a>2,13> |
||
|
x>1>y>2> |
a>1,11> a>2,21> |
a>1,11> a>2,22> |
a>1,11> a>2,23> |
a>1,12> a>2,21> |
a>1,12> a>2,22> |
a>1,12> a>2,23> |
||
|
A |
= |
x>1>y>3> |
a>1,11> a>2,21> |
a>1,11> a>2,22> |
a>1,11> a>2,23> |
a>1,12> a>2,31> |
a>1,12> a>2,32> |
a>1,12> a>2,33> |
|
x>2>y>1> |
a>1,21> a>2,11> |
a>1,21> a>2,12> |
a>1,21> a>2,13> |
a>1,22> a>2,11> |
a>1,22> a>2,12> |
a>1,22> a>2,13> |
||
|
x>2>y>2> |
a>1,21> a>2,21> |
a>1,21> a>2,22> |
a>1,21> a>2,23> |
a>1,12> a>2,21> |
a>1,12> a>2,22> |
A>1,12> a>2,23> |
||
|
x>2>y>3> |
a>1,21> a>2,31> |
a>1,21> a>2,32> |
a>1,21> a>2,33> |
a>1,22> a>2,31> |
a>1,12> a>2,32> |
A>1,12> a>2,33> |
Для удобства рассмотрения разделим матрицу A на четыре квадратные подматрицы. Заметим, что каждая подматрица может быть получена путем логического элементов матрицы умножения A>2> на один из элементов a>1,ij> матрицы A>1>. С учетом этого матрицу A можно представить так:
|
x>1>y>1> |
x>1>y>2> |
x>1>y>3> |
x>2>y>1> |
x>2>y>2> |
x>2>y>3> |
|||
|
x>1>y>1> |
a>1,11>A>2> |
a>1,12>A>2> |
||||||
|
x>1>y>2> |
||||||||
|
A |
= |
x>1>y>3> |
||||||
|
x>2>y>1> |
a>1,21>A>2> |
a>1,22>A>2> |
||||||
|
x>2>y>2> |
||||||||
|
x>2>y>3> |
Таким образом, матрица смежности вершин графа G>1>G>2> имеет вид:
|
x>1>y>1> |
x>1>y>2> |
x>1>y>3> |
x>2>y>1> |
x>2>y>2> |
x>2>y>3> |
|||
|
x>1>y>1> |
0 |
0 |
0 |
1 |
1 |
0 |
||
|
x>1>y>2> |
0 |
0 |
0 |
0 |
0 |
1 |
||
|
A |
= |
x>1>y>3> |
0 |
0 |
0 |
0 |
1 |
0 |
|
x>2>y>1> |
1 |
1 |
0 |
0 |
0 |
0 |
||
|
x>2>y>2> |
0 |
0 |
1 |
0 |
0 |
0 |
||
|
x>2>y>3> |
0 |
1 |
0 |
0 |
0 |
0 |
Нетрудно убедиться, что полученной матрице смежности вершин соответствует граф G>1>G>2>, представленный на рис. 5.
ЛИТЕРАТУРА
Белоусов А.И., Ткачев С.Б. Дискретная математика: Учебник для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана, 2001.– 744 с. (Сер. Математика в техническом университете; Вып XIX).
Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.– М.: Наука, Физматлит, 2000.– 544 с.– ISBN 5-02-015238-2.
Зарубин В.С. Математическое моделирование в технике: Учеб. для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.– 496 с. (Сер. Математика в техническом университете; вып. XXI, заключительный).