Отношения и графы. Отображения, индуцируемые графами

Пусть G = (V, Γ)

– орграф. Очевидно,

V

2

и является бинарным отношением на V. И

наоборот: если R V

2

, где V – конечное непустое множество, то пара (V, R) является орграфом.

Отображение :V V , индуцируемое орграфом G, определяется так:

v V : v w V : v,w .

Можно ввести обратное отображение: w V :

1

w v V : v,w . Тогда множество Γ(v) будем

называть множеством образов вершины v, а Γ–1(w) – множеством прообразов вершины w.

И наоборот: если

f : V V – отображение, то графом этого отображения называется орграф

Gf = (V, Γ), где v, w : v V & w f v .

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

f

Два графа G = (V, X) и H = (W, Y) называют изоморфными и обозначают G ~ H или G ~ H ,

если существует взаимнооднозначное соответствие f : V → W, сохраняющее связность, т.е.

G ~ H , если

f : V W v

, v

j

V

v

, v

j

X f v

, f v

j

Y .

i

i

i

Геометрически изоморфность графов означает возможность наложения их диаграмм друг на

друга без разрывов и склеиваний.

Теорема 8. Изоморфность графов является отношением эквивалентности на множестве графов.

Необходимые условия изоморфности графов

Теорема 9. Пусть G = (V, X), H = (W, Y). Тогда, если G ~ H, то G1

G H1 H : G1 ~ H1 .

Теорема 10. Если графы G = (V, X) и H = (W, Y) изоморфны, то в них одинаково:

1.

число вершин и ребер ( V W ,

X Y );

2.

число вершин степени k, k 0

;

3.

d(G) = d(H);

4.

число простых циклов длины k,

k 0

;

5.

число компонент: K(G) = K(H).

Матричное представление графов

Пусть G = (V, X) – простой (p, q)-граф, V = {v1, v2, …, vp), X = {x1, x2, …, xq).

Матрица смежности графа G – матрица A(G)p×p, в которой

	1, если	v	i	см v	j	,
aij
					случае.
	0, в противном

	Свойства матрицы смежности A(G):
1)	A(G) – симметричная матрица (AT = A);
2)	i 1, p aii 0 – граф не содержит петель;
	i		aij d vi – число единиц в i-й строке равно степени d(vi) вершины vi.
3)		1, p
			j
				1, если				vi инцидентна x j ,
	Матрица инциденций графа G –матрица B(G)p×q, в которой bij
				0, в противном случае.
	Нетрудно доказать, что A = BBT – diag{d1, d2, …, dp}, где di = d(vi), i 1, p .
	Т.к. каждое ребро графа инцидентно двум разным вершинам, то каждый столбец матрицы
инциденций B(G) содержит ровно два единичных элемента, т.е. j					: bij			2.
				1, q

i

Теорема 11. Матрица A(G) и B(G) определяют граф с точностью до изоморфизма.

1