3.4.2.4. Соединение графов

Граф G=(G₁+G₂)=<X, r> представляет собой объединение графов G₁ и G₂ и двудольного полного графа, построенного на носителях X₁\(X₁X₂) и X₂\(X₁X₂). Каждая вершина xX₁, не вошедшая в пересечение (X₁X₂), соединяется со всеми вершинами X₂, не вошедшими в пересесчение (X₁X₂), и наоборот.

X=X₁X₂, r=r₁r₂{(x⁽¹⁾, x⁽²⁾)| x⁽¹⁾(X₁\(X₁X₂)), x⁽²⁾(X₂\(X₁X₂)))}.

На рис. 3.21а) X₁X₂=. Следовательно, ребра двудольного графа соединяют каждую вершину графа G₁ с каждой вершиной графа G₂. На рис. 3.21b) X₁X₂=x₃. Следовательно, ребра двудольного графа соединяют только вершины x₁ и x₂ графа G₁ с вершинами x₄, x₅, x₆ графа G₂. На рис. 3.21c) X₁X₂={x₁, x₂, x₃}. Следовательно, X₁\(X₁X₂)=, а X₂\(X₁X₂)=x₄. Следовательно, множество ребер двудольного графа (x⁽¹⁾, x⁽²⁾)=.

3.4.2.5. Прямое произведение графов

G=G₁G₂=<Z, r> есть граф, множество вершин которого

Z={(x_i, y_j)}(XY), а множество рёбер r={(x_i, y_j)} существует тогда и только тогда, когда в графах G₁ и G₂ есть соответственно рёбра

(x_i, x_t)r₁ и (y_j, y_s)r₂.

Для поиска смежных вершин графа G удобно использовать списки отображений вершин графов G₁ и G₂ и составить списки отображений для (x_i, y_j)(XY). Элементы списка смежных вершин графа G следует определять по правилу:h(x_i, y_j)={(h(x_i), h(y_j))}.

Ниже составлены списки отображений и показан процесс вычисления прямого произведения для графов (см. рис. 3.22).

xi	h(xi)		yJ	h(yj)		(xi, yj)	h(xi, yj)
x1	x2		y1	y3		(x1, y1)	(x2, y3)
x2	x1, x3	*	y2	y3	=	(x1, y2)	(x2, y3)
x3	x2		y3	y1, y2		(x1, y3)	(x2, y1), (x2, y2)
						(x2, y1)	(x1, y3), (x3, y3)
						(x2, y2)	(x1, y3), (x3, y3)
						(x2, y3)	(x1, y1), (x1, y2), (x3, y1), (x3, y2)
						(x3, y1)	(x2, y3)
						(x3, y2)	(x2, y3)
						(x3, y3)	(x2, y1), (x2, y2)

3.4.2.6. Изоморфизм графов

Изоморфизм есть взаимно однозначное отображение объектов произвольной природы, выражающее тождество их строения. Для этого необходимо проверить прямое отображение одного объекта на другой и, наоборот, обратное отображение.

Если даны графы G₁=<X₁; r₁> и G₂=<X₂; r₂> и операторы прямомого и обратного отображений множества вершин и рёбер, т. е.

h₁: X₁X₂, h₂: r₁r₂ и h₁^-1:X₂X₁, h₂^-1: r₂ r₁, то граф G₁ гомоморфен графу G₂ тогда и только тогда, когда каждая вершина x_i⁽¹⁾X₁ и инцидентное ему ребро r_i,j⁽¹⁾r₁ имеют отображение на графе G₂ в виде вершины h₁(x_i⁽¹⁾)=x₂X₂ и инцидентного ребра h₂(r_i,j⁽¹⁾)=r_l,m⁽²⁾r₂ и, наоборот, граф G₂ гомоморфен графу G₁ тогда и только тогда, когда каждая вершина x_i⁽²⁾X₂ и инцидентное ему ребро r_i,j⁽²⁾r₂ имеют отображение на графе G₁ в виде вершины h₁^-1(x_i⁽²⁾)=x₁X₁ и инцидентного ребра h₂^-1(r_i,j⁽²⁾)=r_l,m⁽¹⁾r₁.

Если существует прямой и обратный гомоморфизмы, то графы изоморфны.

Пример: На рис. 3.23 даны три графа. Изоморфны ли они?

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

r1	а	б	в	г	д	е		r2	1	3	5	2	4	6		r3	a	c	f	b	d	e
а	0	0	0	1	1	1		1	0	0	0	1	1	1		a	0	0	0	1	1	1
б	0	0	0	1	1	1		3	0	0	0	1	1	1		c	0	0	0	1	1	1
в	0	0	0	1	1	1		5	0	0	0	1	1	1		f	0	0	0	1	1	1
г	1	1	1	0	0	0		2	1	1	1	0	0	0		b	1	1	1	0	0	0
д	1	1	1	0	0	0		4	1	1	1	0	0	0		d	1	1	1	0	0	0
е	1	1	1	0	0	0		6	1	1	1	0	0	0		e	1	1	1	0	0	0
	3	3	3	3	3	3			3	3	3	3	3	3			3	3	3	3	3	3

Пример: На рис. 3.24 даны два графа. Изоморфны ли они?

Представленные ниже матрицы смежности двух графов имеют одинаковое число вершин и одинаковые степени вершин, но при исполнении операции перестановки строк и столбцов не совпадают.

r1	a	b	c	d	e		r2	5	2	4	1	3
a	0	1	1	1	0		5	0	1	1	1	0
b	1	0	1	1	1		2	1	0	1	1	1
c	1	1	0	0	1		4	1	1	0	0	1
d	1	1	0	0	0		1	1	1	0	0	0
e	0	1	1	0	0		3	0	1	1	0	0
	3	4	3	2	2			3	4	3	2	2

Это позволяет сделать следующие выводы:

• необходимыми условиями являются равенство числа вершин и рёбер, одинаковость числа петель и наборов степеней вершин,

• достаточными условиями являются одинаковость матриц инциденции или смежности графов.