Главная страница

лекции по дм. лекции. Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4


Скачать 1.51 Mb.
НазваниеОсновные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4
Анкорлекции по дм
Дата08.02.2021
Размер1.51 Mb.
Формат файлаdocx
Имя файлалекции.docx
ТипДокументы
#174835
страница20 из 40
1   ...   16   17   18   19   20   21   22   23   ...   40

Операции над графами:

Объединение графов.


Пусть G1(X1,E1) и G2(X2,E2) – произвольные графы.

Определение 11.3. Объединением G1G2графов G1 и G2 называется граф с множеством вершин X1X2, и с множеством ребер (дуг) E1E2.

Рассмотрим операцию на примере графов G1(X1,E1) и G2(X2,E2), приведенных на рис. 11.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) также приведен на рис. 11.1.



Рисунок 11.1

Операция объединения обладает следующими свойствами, которые следуют из определения операции и свойств операций на множествах:

  1. G1G2 = G2G1 – свойство коммутативности;

  2. G1(G2G3) = (G1G2)G3 – свойство ассоциативности.

Операция объединения графов может быть выполнена в матричной форме. Для графов с одним и тем же множеством вершин справедлива следующая теорема.

Теорема 11.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, а множество ребер (дуг) определяется множествами E1 для графа G1 и E2 для графа G2. Очевидно, что матрицы A’1 и A’2 смежности вершин этих графов могут быть получены из матриц A1 и A2 путем добавления в них дополнительных столбцов и строк с нулевыми элементами.

Применив к графам G’1 и G’2 теорему 4.1, найдем матрицу смежности вершин графа G’1G’2 как A’1A’2. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно X1X2, а множество ребер определяется, как E1E2, что соответствует операции объединения графов.

Пример. Выполнить в матричной форме операцию объединения графов 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, изображенному на рис.11.1.
1   ...   16   17   18   19   20   21   22   23   ...   40


написать администратору сайта