ОПРЕДЕЛЕНИЕ. Рефлексивное, антисимметричное и транзитивное отношение на некотором множестве называется отношением порядка.

Рефлексивное, антисимметричное и транзитивное отношение на некотором множестве называется отношением порядка.

Отношение порядка на некотором множестве А можно интерпретировать как отношение старшинства или подчиненности между элементами A.

Например, если A - множество сотрудников некоторого учреждения, то отношение "руководить" является отношением порядка на этом множестве. То есть, если обозначить данное отношение как r, то соотношение ar bозначает, что сотрудник a руководит сотрудником b, или, что то же самое, aявляетсяначальником b.

Упражнение. Показать, что если r - это отношение порядка, то отношение r^-1 также отношение порядка.

Множество A, на котором задано отношение порядка, называется упорядоченным. Для обозначения множества A с заданным на нем отношением порядка r применяется запись
(A, r).

Элементы a и b упорядоченного множества (A, r) называются сравнимыми, если выполняется одно из двух соотношений: a r b или b r a.

Если (A, r) - это упорядоченное множество и множество A - конечное, то возможно наглядное представление отношения r в виде специальной диаграммы. На таких диаграммах элементы A изображаются точками. Из точки, соответствующей a, проводится дуга в точку, соответствующую b в том и только в том случае, когда выполняется условие: ar bи не существует такого элемента c, отличного отaиb, что ar c и cr b. Кроме того, концы всякой дуги соединяют только пары разных вершин.

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

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

Действительно, справедливость соотношения ar b означает, что в диаграмме существует цепочка ребер, ведущая из aв b. Если a= b, то такая цепочка пустая.