На бирже курсовых и дипломных проектов можно найти образцы готовых работ или получить помощь в написании уникальных курсовых работ, дипломов, лабораторных работ, контрольных работ, диссертаций, рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Реферат Операции на графах позволяют образовывать новые графы из нескольких более простых. Операции на графах без параллельных ребер. Объединение графов. Свойства операции объединения т, которые следуют из определения операции и свойств операций на множествах.

Информация:

Тип работы: Реферат. Предмет: Математика. Добавлен: 27.11.2008. Сдан: 2008. Уникальность по antiplagiat.ru: --.

Описание (план):


БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Кафедра информатики
РЕФЕРАТ
На тему:
«Операции на графах»


МИНСК, 2008
Операции на графах позволяют образовывать новые графы из нескольких более простых. В этом параграфе будут рассмотрены операции на графах без параллельных ребер (дуг).
Объединение графов.
Пусть G1(X1,E1) и G2(X2,E2) - произвольные графы. Объединением G1G2 графов G1 и G2 называется граф с множеством вершин X1X2, и с множеством ребер (дуг) E1E2.
Рассмотрим операцию на примере графов G1(X1,E1) и G2(X2,E2), приведенных на рис. 4.1. Множества вершин первого и второго графов соответственно равны X1 = {x1, x2, x3} и X2 = {x2, x3, x4}, а множество вершин результирующего графа определится как X = X1X2 = {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.
Операция объединения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:
G1G2 = G2G1 - свойство коммутативности;
G1(G2G3) = (G1G2)G3 - свойство ассоциативности.
Операция объединения графов может быть выполнена в матричной форме. Для графов с одним и тем же множеством вершин справедлива следующая теорема.
Теорема 1. Пусть G1 и G2 - два графа (ориентированные или не ориентированные одновременно) с одним и тем же множеством вершин X, и пусть A1 и A2 - матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1G2 является матрица A = A1A2, образованная поэлементным логическим сложением матриц A1 и A2.
Рассмотрим выполнение операции объединения графов, множества вершин которых не совпадают. Пусть G1(X1,E1) и G2(X2,E2) - графы без параллельных ребер и множества X1 и X2 вершин этих графов не совпадают. Пусть A1 и A2 - матрицы смежности их вершин графов. Для таких графов операция объединения может быть выполнена следующим образом.
В соответствии с определением операции объединения графов найдем множество вершин результирующего графа как X1X2. Построим вспомогательные графы G'1 и G'2, множества вершин которых есть множество X1X2, а множество ребер (дуг) определяется множествами E1 для графа G'1 и E2 для графа G'2. Очевидно, что матрицы A'1 и A'2 смежности вершин этих графов могут быть получены из матриц A1 и A2 путем добавления в них дополнительных столбцов и строк с нулевыми элементами.
Применив к графам G'1 и G'2 теорему 4.1, найдем матрицу смежности вершин графа G'1G'2 как A'1A'2. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно X1X2, а множество ребер определяется, как E1E2, что соответствует операции объединения графов.
Пример 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

Множество вершин результирующего графа X1X2 = {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'1A'2 имеет вид
X1
x2
x3
x4

x1
0
1
1
0

x2
1
0
0
1
A = A'1A'2
=
x3
0
1
1
0

x4
0
0
1
0

Полученная матрица смежности вершин A'1 A'2 соответствует графу G1G2, изображенному на рис.1.
Пересечение графов

Пусть G1(X1,E1) и G2(X2,E2) - произвольные графы. Пересечением G1G2 графов G1 и G2 называется граф с множеством вершин X1X2 с множеством ребер (дуг) E = E1E2
Операция пересечения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:
G1G2 = G2G1- свойство коммутативности;
G1 (G2G3) = (G1G2) G3 - свойство ассоциативности.
Для того чтобы операция пересечения была всеобъемлющей, необходимо ввести понятие пустого графа. Граф G(X,E) называется пустым, если множество X вершин графа является пустым (X=). Заметим, что в этом случае и множество E ребер (дуг) графа также пустое множество (E=). Пустой граф обозначается символом . Такой граф может быть получен в результате выполнения операции пересечения графов, у которых X1X2=. В этом случае говорят о непересекающихся графах.
Рассмотрим выполнение операции пересечения графов, изображенных на рис. 2. Для нахождения множества вершин результирующего графа запишем множества вершин исходных графов и выполним над этими множествами операцию пересечения:
X1 = {x1, x2, x3}; X2 = {x1, x2, x3, x4};
X = X1X2 = {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 = E1E2 = {(x1, x3), (x2, x1)}.

Графы G1(X1,E1), G2(X2,E2) и их пересечение приведены на рис 4.2.
Операция пересечения графов может быть выполнена в матричной форме.
Теорема 2. Пусть G1 и G2 - два графа (ориентированные или неориентированные одновременно) с одним и тем же множеством вершин X, и пусть A1 и A2 - матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1G2 является матрица A = A1A2 образованная поэлементным логически умножением матриц A1 и A2.
Рассмотрим выполнение операции пересечения для графов с несовпадающим множеством вершин.
Пусть G1(X1,E1) и G2(X2,E2) - графы без параллельных ребер, множества X1 и X2 вершин графов не совпадают, а A1 и A2 - матрицы смежности вершин графов. Для таких графов операция пересечения может быть выполнена так.
В соответствии с определением операции пересечения графов найдем множество вершин результирующего графа как X1X2. Построим вспомогательные графы G'1 и G'2, множества вершин которых есть множество X1X2, а множество ребер (дуг) определяется множествами E'1 и E'2 всех ребер (дуг), инцидентных этим вершинам. Очевидно, что матрицы A'1 и A'2 смежности вершин этих графов могут быть получены из матриц A1 и A2 путем удаления из них столбцов и строк, соответствующих вершинам, не вошедшим во множество X1X2.
Применив к графам G'1 и G'2 теорему 2, найдем матрицу смежности вершин графа G'1G'2 как A'1A'2. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно X1X2, а множество ребер определяется, как E1E2, что соответствует операции пересечения графов.
Пример 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 = X1X2 = {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'1A'2
=
x2
1
0
1
x3
0
0
0
Полученная матрица смежности вершин A'1 A'2 соответствует графу G1G2, изображенному на рис.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 = a1ika2kj (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
Вычислив элементы матрицы согласно (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(G2) и G2(G1), представленные на рис. 3.

Декартово произведение графов. Пусть G1(X,E1) и G2(Y,E2) -- два графа. Декартовым произведением G1(X,E1)G2(Y,E2) графов G1(X,E1) и G2(X,E2) называется граф с множеством вершин XY, в котором дуга (ребро), идущая из вершины (xiyj) в (xkyl), существует тогда и только тогда когда существует дуга (xixk), принадлежащая множеству дуг E1 и j = l или когда существует дуга (yj,yl), принадлежащая множеству E2 и i = k.

Выполнение операции декартова произведения рассмотрим на примере графов, изображенных на рис. 4. Множество вершин Z результирующего графа определяется как декартово произведение множеств XY. Множество 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) в результирующем графе. Для удобства рассмотрения всех дуг результирующего графа составим таблицу, в первом столбце которой перечисляются вершины с совпадающими компонентами, во втором - дуги между несовпадающими компонентами, а в третьем и четвертом - дуги в результирующем графе.

№ п.п.
Группы вершин с совпадаю-щими компонентами
Дуги для несовпада--ю-щих компонент

Дуга

(xiyj)(xkyl)

Дуга

(z,z)
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)
(x2 и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.