52. Отношение покрытия и диаграммы отношений порядка

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

Элемент D покрывает элемент C (записывается ), если D > C (элемент D доминирует над элементом C) и между элементами D и C нет некоторого элемента B, удовлетворяющего условию D > B > C. Из введенной операции покрывания следует, что отношение покрывания базируется на отношении порядка >. Особенно наглядно это видно на множестве чисел натурального ряда, где каждое последующее число больше любого из предыдущих, но покрывает только одно число, меньшее его на единицу.

Для построения диаграммы некоторого конечного упорядоченного множества (B, >) (или диаграммы отношения порядка > на множестве B) необходимо:

– отобразить элементы множества B точками на плоскости, расположив их так, чтобы для любых точек D, C Î B, для которых справедливо , точка D была расположена выше точки C;

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

Диаграммы отношения порядка очень наглядно демонстрируют доминирование одного элемента над другим. Например, если D > C, то это выполняется только в случае наличия пути в диаграмме от точки D к точке C по отрезкам прямых, идущих сверху вниз. Таким образом, диаграмма наглядно демонстрирует следующее утверждение.

Для того, чтобы в конечном упорядоченном множестве (B, >) для какой либо пары элементов D, C Î B выполнялось условие D > C Необходимо существование конечной последовательности элементов D, B1, B2, ¼, Bn–1, Bn, C, принадлежащих множеству B, причем в этой последовательности каждый предыдущий элемент покрывает последующий:

D > C Û существует последовательность .

Пример диаграммы отношения порядка приведен на рис. 5.4.

Рис. 5.4. Пример диаграммы отношения порядка

Из диаграммы имеем: A > B, A > C, A > F, A > G, B > F , C > F , C > G, D > C и т. д. Однако условия A > E и D > B не выполняются, поскольку нет пути из точки A в точку E и из точки D в точку B По отрезкам прямых, идущих только сверху вниз. Таким образом, по диаграмме отношения порядка легко определяются пары элементов, принадлежащие и не принадлежащие отображаемому геометрически отношению порядка.

На диаграмме отношения порядка (рис. 5.4) можно выделить два элемента A и D, которые в упорядоченные пары отношения (B, >) входят только на первом месте, то есть для них нет элементов, которые бы их превосходили или доминировали, или были большими их (если множество B является множеством целых или действительных чисел). Такие элементы множества B называются максимальными. Если элемент D упорядоченного множества (B, >) доминирует, превосходит любой другой элемент этого множества, то он называется наибольшим элементом этого упорядоченного множества. На диаграмме отношения порядка рис. 5.4 имеется два максимальных элемента, но нет наибольшего.

Между понятиями наибольший и максимальный элемент существует следующая взаимосвязь.

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

Рис. 5.5. Пример бесконечного множества с одним максимальным элементом

Если отношение порядка b на некотором множестве B обладает свойством линейности (т. е. в множестве B нет пар несравнимых элементов), то множество B называется линейно упорядоченным или цепью. Диаграмма отношения порядка такого конечного упорядоченного множества имеет вид линии (рис. 5.3). Из вида диаграмм линейно упорядоченных множеств следует, что для этих множеств понятия "наибольший элемент" и "максимальный элемент" эквивалентны.

< Предыдущая		Следующая >