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

Матрицы отношений порядка

Структура упорядоченных множеств

Приведем несколько определений, относящихся к структуре множества М, упорядочен­ного некоторым отношением порядка А. Мажорантой (верхней гра­ницей) подмножества Q Í М называют такой элемент т Î М, что для всех qÎQ справедливо соотношение qAm. Минорантой (нижней границей) подмножества Q Í М называют такой элемент пÎ М, что для всех qÎQ справедливо соотношение nAq.

Если мажоранта т (миноранта п) принадлежит Q, то т называ­ется максимумом (п называется минимумом) множества Q и обозначается max Q (min Q). Максимум, как и минимум, если он су­ществует, единственен; поэтому, когда говорят о минимуме или мак­симуме множества М, имеют в виду вполне определенный элемент.

Множество Q Í М может иметь много мажорант и минорант. Если множество мажорант (минорант) имеет минимум (максимум), то этот элемент единственен. Его называют верхней (нижней) гранью или супремумом (инфинумом) множества Q и обозначают sup Q (inf Q).

Отношению порядка соответ­ствует матрица, у которой главная диагональ заполнена единицами (рефлексивность). Для каждой пары единичных элементов, один из которых расположен в i-м столбце и j-й строке, а второй – в j-м столбце и k-й строке, обязательно существует единичный элемент в i-м столбце и k-й строке (транзитивность). Кроме того, ни одни единичный элемент не имеет симметричного относительно главной диагонали (антисимметричность). Например, матрица отношения «быть делителем» на множестве (1,2, 3, 4, 6, 7, 12, 14, 21, 28,42,84} имеет вид:

 

 

Матрица отношения строгого порядка отличается тем, что все элементы главной диагонали нулевые (антирефлексивность), а квази­порядка — допустимостью симметричных единичных элементов.

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

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

На рис. 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. Граф отношения квазипорядка (а) и его упрощенное изображение (б).