Отношение порядка

Речь идет о ситуациях, когда объекты некоторого множества соотносятся по взаимному старшинству, по важности, по «первичности» и т.д. подобные отношения, по видимому, не симметричны.

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

Отношение R на множестве М называется отношением строгого порядка, если оно антирефлексивно и транзитивно.

Отношение R строго порядка :

Имеет интерпретации: «элемент х предпочтительнее у», «х больше у», «х предшествует у», «х включает в себя у».

Множество М с заданным на нем отношением строгого порядка R называют упорядоченным множеством.

Отношение R на множество М называется отношением нестрогого порядка, если оно может быть представлено в виде: , где R₁- строгий порядок на М, а Е– диагональное отношение.

Любое отношение нестрогого порядка – рефлексивно, антисимметрично и транзитивно.

Важный специальный класс отношений порядка - так называемые древесные порядки.

Определение. Отношение строгого порядка < на множество М называется отношением древесного порядка если:

1) из того, что x < y и x < z следует, что y и z сравнимы;

2) на множестве М существует наибольший элемент.

Элемент x₀ мы будем называть наибольшим, если для всякого элемента , отличного от х₀, выполнено соотношение у<х₀ . Можно видеть, что наибольший элемент единственен.

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

Дерево задается с помощью графов.

Назовем окрестностью элемента y совокупность элементов Z , для которых выполняется yRZ. Дерево изображается по ярусам.

В первом ярусе поместим корень дерева – наибольший элемент x₀. Во втором ярусе элементы, входящие в окрестность x₀. В третьем ярусе поместим элементы, входящие в окрестности элементов второго яруса и т.д., стрелки в графе могут идти только от яруса к ярусу.

При этом от каждого элемента к верхнему ярусу идет ровно одно ребро, а к нижнему может идти сколько угодно ребер.

Общее число ярусов называется высотой дерева - h. Максимальное число элементов в одной окрестности (максимально число ростков, выходящих из одной вершины) называется шириной дерева – d.

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

При этом подсистемы выступают опять как нечто целостное.

Лекция № 12