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

• Название: Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4
• Анкор: лекции по дм
• Дата: 08.02.2021
• Размер: 1.51 Mb.
• Имя файла: лекции.docx
• Тип: Документы; #174835
• страница: 21 из 40

Пересечение графов

Пусть G₁(X₁,E₁) и G₂(X₂,E₂) – произвольные графы.

Определение 11.4. Пересечением G₁G₂ графов G₁ и G₂ называется граф с множеством вершин X₁X₂ с множеством ребер (дуг) E = E₁E₂

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

1. 
   G₁G₂ = G₂G₁– свойство коммутативности;
   
2. 
   G₁ (G2G3) = (G1G2)  G₃ – свойство ассоциативности.
   

Для того чтобы операция пересечения была всеобъемлющей, необходимо ввести понятие пустого графа. Граф G(X,E) называется пустым, если множество X вершин графа является пустым (X=). Заметим, что в этом случае и множество E ребер (дуг) графа также пустое множество (E=). Пустой граф обозначается символом . Такой граф может быть получен в результате выполнения операции пересечения графов, у которых X₁X₂=. В этом случае говорят о непересекающихся графах.

Рассмотрим выполнение операции пересечения графов, изображенных на рис. 2. Для нахождения множества вершин результирующего графа запишем множества вершин исходных графов и выполним над этими множествами операцию пересечения:
X₁ = {x₁, x₂, x₃}; X₂ = {x₁, x₂, x₃, x₄};

X = X₁X₂ = {x₁, x₂, x₃}.
Аналогично определяем множество E дуг результирующего графа:

E₁ = {(x₁, x₂), (x₁, x₃), (x₂, x₁), (x₂, x₃), (x₃, x₂)};

E₂ = {(x₁, x₃), (x₂, x₁), (x₂, x₃), (x₂, x₄), (x₃, x₁)};

E = E₁E₂ = {(x₁, x₃), (x₂, x₁)}.

Графы G₁(X₁,E₁), G₂(X₂,E₂) и их пересечение приведены на рис 11.2.



Рисунок 11.2

Операция пересечения графов может быть выполнена в матричной форме.

Теорема 11.3. Пусть G₁ и G₂ – два графа (ориентированные или неориентированные одновременно) с одним и тем же множеством вершин X, и пусть A₁ и A₂ – матрицы смежности вершин этих графов. Тогда матрицей смежности вершин графа G1G2 является матрица A = A₁A₂ образованная поэлементным логически умножением матриц A₁ и A₂.

Рассмотрим выполнение операции пересечения для графов с несовпадающим множеством вершин.

Пусть G₁(X₁,E₁) и G₂(X₂,E₂) – графы без параллельных ребер, множества X₁ и X₂ вершин графов не совпадают, а A₁ и A₂ – матрицы смежности вершин графов. Для таких графов операция пересечения может быть выполнена так.

В соответствии с определением операции пересечения графов найдем множество вершин результирующего графа как X₁X₂. Построим вспомогательные графы G’₁ и G’₂, множества вершин которых есть множество X₁X₂, а множество ребер (дуг) определяется множествами E’₁ и E’₂ всех ребер (дуг), инцидентных этим вершинам. Очевидно, что матрицы A’₁ и A’₂ смежности вершин этих графов могут быть получены из матриц A₁ и A₂ путем удаления из них столбцов и строк, соответствующих вершинам, не вошедшим во множество X1X2.

Применив к графам G’₁ и G’₂ теорему 2, найдем матрицу смежности вершин графа G’₁G’₂ как A’₁A’₂. Очевидно, что полученной матрице смежности вершин соответствует граф, множество вершин которого равно X₁X₂, а множество ребер определяется, как E₁E₂, что соответствует операции пересечения графов.

Пример. Выполнить в матричной форме операцию пересечения графов G₁ и G₂, представленных на рис. 11.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 = X₁X₂ = {x₁, x₂, x₃}.

Составим матрицы смежности вершин вспомогательных графов G’₁ и G’₂.

			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 = A₁  A₂

			x1	x2	x3
		x1	0	0	0
A’1A’2	=	x2	1	0	1
		x3	0	0	0

Полученная матрица смежности вершин A’₁ A’₂ соответствует графу G₁G₂, изображенному на рис.11.2.