На графе

Будем считать, что на графе введено отношение порядка, если для,любых двух вершин (х и у), удовлетворяющих условию , существует путь из х в у. В этом случае говорят, что вершина х предшествует вершине у, или вершина у следует за вершиной х. Это определение отражает на графе все свойства отношения порядка.

Рефлексивность. Условие

истинно (4.4)

означает эквивалентность вершины самой себе, т.е. условие . В то же время это условие можно рассматривать как наличие пути из х в х, т.е. как петлю в вершине х. (рисунок 6)

Рисунок 4.6

Транзитивность. Условие

(4.5)

означает, что вершины последовательно встречаются на одном и том же пути (рисунок 7).

Рисунок 4.7

Антисимметричность. Условие

(4.6)

означает, что в графе имеется контур, на котором лежат вершины х и у (рисунок 8)

Рисунок 4.8

Левая часть этого выражения (слева от стрелки) говорит о том, что существует путь из х в у, а также существует путь из у в х, а это означает, что в графе имеется контур,

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

Иногда этот вывод рассматривают как определение эквивалентности на графе, так как удовлетворяются все три условия: рефлексивности, симметричности, транзитивности.

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

На графе может быть введено отношение строго порядка. В этом случае для любых двух вершин (х и у), удовлетворяющих условию x < y, существует путь, идущий из х в у. Условие транзитивности x < y < z→ x < z, означает, что вершины x, y, z встречаются последовательно на одном и том же пути. Условие антирефлексивности (х<x ложно) говорит об отсутствии петель на графе, а условие несимметрии (x<y, y<x взаимоисключаются) говорит об отсутствии контуров. Таким образом отношения строго порядка определяют граф без контуров.