5.8. Графы отношений порядка

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

Так как отношение порядка транзитивно, то его граф обычно •вменяется графом редукции, причем в графе нестрогого порядка петли не изображаются. Граф квазипорядка можно упростить, заменив его графом строгого порядка на множестве вершин, соответ­ствующих классам эквивалентности. При этом каждая такая вершина изображает все множество элементов данного класса.

На рис. 5.1 показан упрощенный граф отношения «быть делителем» из (9). На графе наглядно прослеживается структура упорядоченного множества. Так, для подмножества Q = {4, 6, 14, 28, 42} мажорантой является элемент 84, а минорантами - эле­менты 1 и 2. Максимума и минимума Q не имеет, но sup Q = 84, inf Q = 2. Для всего множества единственная мажоранта 84 является одновременно максимальным элементом, а миноранта 1 - минимальным элементом.

На рис. 5.2, а показан граф отношения квазипорядка, a на рис. 5.2, б - упрощенный граф отношения порядка на множестве классов эквивалентности индуциро­ванного этим квазипорядком.

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

Рис. 5.1. Упрощенный граф отношения «быть делителем»	Рис. 51. Граф отношения квазипорядка (а) и его упрощенное изображение (б).