Речь идет о ситуациях, когда объекты некоторого множества соотносятся по взаимному старшинству, по важности, по «первичности» и т.д. подобные отношения, по видимому, не симметричны.
Поскольку имеется возможность двоякого введения упорядочивания (как в случае нестрого неравенства <=, так и строгого неравенства <), то имеются отношения строгого и нестрогого порядка.
Отношение R на множестве М называется отношением строгого порядка, если оно антирефлексивно и транзитивно.
Отношение R строго порядка :
Имеет интерпретации: «элемент х предпочтительнее у», «х больше у», «х предшествует у», «х включает в себя у».
Множество М с заданным на нем отношением строгого порядка R называют упорядоченным множеством.
Отношение R на множество М называется отношением нестрогого порядка, если оно может быть представлено в виде:, где R1- строгий порядок на М, а Е– диагональное отношение.
Любое отношение нестрогого порядка – рефлексивно, антисимметрично и транзитивно.
Важный специальный класс отношений порядка - так называемые древесные порядки.
Определение.Отношение строгого порядка < на множество М называется отношением древесного порядка если:
1) из того, что x < y и x < z следует, что y и z сравнимы;
2) на множестве М существует наибольший элемент.
Элемент x0 мы будем называть наибольшим, если для всякого элемента , отличного от х0, выполнено соотношение у<х0 . Можно видеть, что наибольший элемент единственен.
Множество М с заданным на нем древесным порядком – называется деревом, а наибольший элемент – корнемдерева.
Дерево задается с помощью графов.
Назовем окрестностью элемента y совокупность элементов Z , для которых выполняется yRZ. Дерево изображается по ярусам.
В первом ярусе поместим корень дерева – наибольший элемент x0. Во втором ярусе элементы, входящие в окрестность x0. В третьем ярусе поместим элементы, входящие в окрестности элементов второго яруса и т.д., стрелки в графе могут идти только от яруса к ярусу.
При этом от каждого элемента к верхнему ярусу идет ровно одно ребро, а к нижнему может идти сколько угодно ребер.
Общее число ярусов называется высотойдерева - h. Максимальное число элементов в одной окрестности (максимально число ростков, выходящих из одной вершины) называется шириной дерева – d.
Очевидно, когда речь идет о системе, математической моделью которого является дерево, то корень дерева отождествляется с собственно системой как с чем-то целостным. Выделение первого яруса вершин означает выделение подсистем первого уровня, второго уровня и т.д.
При этом подсистемы выступают опять как нечто целостное.