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

Один и тот же граф геометрически можно изобразить различными способами. Так на рис. 2.7 приведены три изображения одного и того же графа. Такие графы называются изоморфными.

1

1 2

2

1 4 3 4

4 3

2 3

Рис.2.7 - Пример изоморфных графов

Произвольный граф G имеет как минимум один автоморфизм - тождественное преобразование VG  VG, при котором e(v) = v для произвольной вершины v. Очевидно, что если  - автоморфизм графа G, то й обратная подстановка ^-1 также является автоморфизмом. Если подстановки  і  обе суть автоморфизмы, те и их произведение  - автоморфизм.

2.4. Отношение порядка и отношение эквивалентности на графе.

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

Будем считать, что на графе G=(X,Г) введено отношение порядка, если для любых 2-х вершин (х и у), удовлетворяющих условию ху,  путь из х в у. В этом случае говорят, что вершина х предшествует вершине у или что вершина у следует за вершиной х.

Покажем, что данное определение отражает на графе все свойства отношения порядка

Рефлексивность: Условие хх истинно означает эквивалентность вершины самой себе, т.е. условие хх. Однако при желании это условие можно рассматривать как наличие пути из х в х, т.е. как петлю в вершине х (рис. 2.8 а).

Транзитивность: Условие ху, уz хz означает, что вершины x,y,z последовательно встречаются на одном и том же пути (рис. 2.8).

Рис.2.8 - Транзитивность на графах

Антисиметричность: Покажем справедливость условия ху, ух ху. Левая часть этого выражения говорит о том, что существует путь из х в у, а так же существует путь из у в х. Но это означает, что в графе имеется контур, на котором лежат вершины х, у (рис. в).

Из правой части условия вытекает, что вершины, лежащие на одном и том же контуре, являются эквивалентными. Будем рассматривать этот вывод как определение эквивалентности на графе и покажем, что такое определение удовлетворяет всем трём условиям отношения эквивалентности. Условия рефлексивности хх и симметрии хуух являются очевидными и вытекают из данного выше определения эквивалентности. Условие транзитивности хy, yzxz также является очевидным, так как говорит о том, что если в графе имеется контур с вершинами X и Y, а также контур с вершинами у и z , то имеется и контур, на котором лежат вершины х и z (рис. в).

Таким образом, отношение порядка совместно с отношением эквивалентности определяет некоторый граф.

На графе может быть также введено отношение строгого порядка. В этом случае для любых двух вершин (X и Y), удовлетворяющих условно XY, существует путь, идущий из X в Y. Условие транзитивности XYZXZ означает, как и в предыдущем случае, что вершины X, Y и Z встречаются последовательно на одном и том же пути. Условие антирефлексивности (XX ложно) говорит об отсутствии петель на графе, а условие несимметричности (XY, уõ взаимоисключается ) говорит об контуров.

Таким образом, отношение строгого порядка определяет граф без контуров.

Сведем все данные по отношениям порядка в таблицу 2.1.

Таблица 2.1 - Определение различных видов порядка

Порядки	Отношение
	Антисимметричное	Транзитивное	Рефлексивное	Антирефлексивное	Полное	Неполное
Строгий	+	+		+
Нестрогий	+	+	+
Полный	+	+			+
Неполный	+	+				+