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

Def.35 Непустое упорядоченное множество М, любые два элемента которого сравнимы, называется линейно (совершенно, просто) упорядоченным множеством(цепью).

Реляционные системы.

Ниже рассматривается упорядоченные множества вида ‹М,£;› и ‹М,‹›

Пример. Пусть на задано отношение порядка , если , граф этого упорядоченного множества имеет вид:

Поскольку не все вершины этого графа сравнимы (например, v₁ и v₆), то множество вершин V есть частично упорядоченное множество. Подмножества , и т.д. – линейно упорядоченные подмножества множества вершин V (цепи). Цепи , – максимальные цепи.

Def.37 Неориентированный граф конечного упорядоченного множества, составленный из максимальных цепей, называется диаграммой Хассе. Иначе, диаграмма Хассе есть такой граф упорядоченного множества , в котором удалены петли и транзитивно замыкающие дуги.

Пример. Отношение "быть подмножеством" на множестве всех подмножеств множества М = {a,b,c}, может быть представлено как ориентированным графом упорядоченного множества , так и диаграммой Хассе:

Пример. Пусть М = {1,2,3,4,5,6} – линейно упорядоченное множество. В этом случае орграф и диаграмма Хассе следующие:

Дата добавления: 2014-01-06; Просмотров: 677; Нарушение авторских прав?; Мы поможем в написании вашей работы!