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

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

Композиция графов

Пусть G₁(X,E₁) и G₂(X,E₂) — два графа с одним и тем же множеством вершин X.

Определение 11.5. Композицией G₁(G₂) графов G₁и G₂ называется граф с множеством вершин E, в котором существует дуга (x_i,x_j) тогда и только тогда, когда существует дуга (x_i,x_k), принадлежащая множеству E₁, и дуга (x_k,x_j), принадлежащая множеству E₂.

Рассмотрим выполнение операции композиции G₁(G₂) на графах, изображенных на рис.11.3. Для рассмотрения операции составим таблицу, в первом столбце которой указываются ребра (x_i, x_k), принадлежащие графу G₁, во втором — ребра (x_k, x_j), принадлежащие графу G₃, а в третьем — результирующее ребро (x_i, x_j) для графа G₁(G₂).

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)

Заметим, что дуга (x₁,x₃) результирующего графа в таблице встречается дважды. Однако, поскольку рассматриваются графы без параллельных ребер (дуг), то в множестве E результирующего графа дуга (x₁,x₃) учитывается только один раз, т.е. E = {(x₁,x₁), (x₁,x₃), (x₂,x₁), (x₂,x₃)}

На рис. 3 изображены графы G₁ и G₂ и их композиции G₁(G₂). На этом же рисунке изображен граф G₂(G₁). Рекомендуется самостоятельно построить граф G₂(G₁) и убедиться, что графы G₁(G₂) и G₂(G₁) не изоморфны.




Рисунок 11.3.

Пусть А₁ и A₂ – матрицы смежности вершин графов G₁(X,E₁) и G(X,E₂) соответственно. Рассмотрим матрицу A₁₂элементы a_ij которой вычисляется так:

_n

a_ij= a_1ika_2kj (1)

^k=1

где a_1ikи a_2kj – элементы матрицы смежности вершин первого и второго графов соответственно. Элемент a_ij равен 1, если в результирующем графе G₁(G₂) существует дуга, исходящая из вершины x_i и заходящая x_j, и нулю – в противном случае.

Пример. Выполнить операцию композиции для графов, пред­ставленных на рис.11.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

Нетрудно убедиться, что полученным матрицам смежности вершин соответствуют графы G₁(G₂) и G₂(G₁), представленные на рис. 11.3.