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

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

Будем считать, что на графе 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 - Определение различных видов порядка