Вложенный набор - Википедия - Nested set

А вложенный набор из Русские куклы.

Вложенный набор, представляющий биологическая таксономия пример. Снаружи: отряд, семейство, род, вид.

В наивная теория множеств, а вложенный набор^{[сомнительный – обсуждать]} представляет собой набор, содержащий цепочку подмножеств, образующих иерархическую структуру, например Русские куклы.

Он используется в качестве эталона во всех научная иерархия определения и многие технические подходы, такие как дерево в вычислительные структуры данных или же модель вложенного множества из реляционные базы данных.

Иногда это понятие путают с "набором наборов" с наследственная собственность (как конечность в наследственно конечное множество ).

Формальное определение

Некоторые авторы предпочитают использовать термин Коллекция вложенных наборов, потому что это формальное определение коллективного свойства множества множеств. Другие^[1] предпочитают классифицировать это отношение как порядок включения. Коллекция - это «набор наборов».

Позволять B быть непустым множеством и C быть набором подмножеств B. потом C является вложенным набором наборов, если:

• ${ displaystyle B in C}$ (и ${ Displaystyle emptyset notin C}$)
• ${ displaystyle forall H, K in C ~: ~ H cap K neq emptyset ~ Rightarrow ~ H subset K ~ lor ~ K subset H}$

Первое условие гласит, что набор B, который содержит все элементы любого подмножества, должен принадлежать к коллекции вложенных наборов. Некоторые авторы^[1] также заявить, что B не является пустым или пустое не является подмножеством C.

Второе условие гласит, что пересечение каждой пары наборов в коллекции вложенных наборов не является пустым набором, только если один набор является подмножеством другого.^[2]

В частности, при сканировании всех пар подмножеств при втором условии это верно для любой комбинации с B.

Пример

Выражая пример как частично заказанный набор своим Диаграмма Хассе.

Используя набор атомные элементы, как набор масти игральных карт:

B = {♠, ♥, ♦, ♣};     B₁ = {♠, ♥};   B₂ = {♦, ♣};   B₃ = {♣};
C = {B, B₁, B₂, B₃}.

Второе условие (формального определения) можно проверить, объединив все пары:

B₁ ∩ B₂ = ∅;  B₁ ∩ B₃ = ∅;  B₃ ⊂ B₂.

Существует иерархия, которая может быть выражена двумя ветвями и их порядком вложенности: B₃ ⊂ B₂ ⊂ B;  B₁ ⊂ B.

Производные концепции

Как наборы, являющиеся общей абстракцией и основанием для многих концепций, вложенный набор является основой для «вложенной иерархии», «иерархии включения» и других.

Вложенная иерархия

Вложенная иерархия или иерархия включения это иерархическое упорядочение вложенный наборс.^[3] Понятие гнездования проиллюстрировано на русском языке. матрешки. Каждая кукла окружена другой куклой, вплоть до внешней куклы. Внешняя кукла содержит все внутренние куклы, следующая внешняя кукла содержит все оставшиеся внутренние куклы и так далее. Матрешки представляют собой вложенную иерархию, где каждый уровень содержит только один объект, т.е. есть только одна кукла каждого размера; Обобщенная вложенная иерархия допускает наличие нескольких объектов внутри уровней, но каждый объект имеет только одного родителя на каждом уровне. Иллюстрируя общую концепцию:

${ displaystyle { text {square}} subset { text {четырехугольник}} subset { text {polygon}} subset { text {shape}} ,}$

Квадрат всегда можно назвать четырехугольником, многоугольником или формой. Таким образом, это иерархия. Однако рассмотрите набор полигонов с использованием этой классификации. Квадратная банка Только быть четырехугольником; это никогда не может быть треугольник, шестиугольник, так далее.

Вложенные иерархии - это организационные схемы, лежащие в основе таксономии и систематические классификации. Например, используя оригинал Линнеевская таксономия (версия, которую он выложил в 10-м издании Systema Naturae ) человека можно сформулировать как:^[4]

${ displaystyle { text {H. sapiens}} subset { text {Homo}} subset { text {Primates}} subset { text {Mammalia}} subset { text {Animalia}}}$

Таксономии могут часто меняться (как показано на биологическая таксономия ), но основная концепция вложенных иерархий всегда одна и та же.

Иерархия сдерживания

Иерархия сдерживания - это прямая экстраполяция вложенная иерархия концепция. Все упорядоченные наборы по-прежнему вложены, но каждый набор должен быть "строгий "- никакие два набора не могут быть идентичными. Приведенный выше пример фигур можно изменить, чтобы продемонстрировать это:

${ displaystyle { text {square}} subsetneq { text {четырехугольник}} subsetneq { text {polygon}} subsetneq { text {shape}} ,}$

Обозначение ${ Displaystyle х subsetneq у ,}$ средства Икс это подмножество у но не равноу.

Иерархия сдерживания используется в наследование классов из объектно-ориентированного программирования.

Смотрите также

• Наследственно счетное множество
• Наследственная собственность
• Иерархия (математика)
• Модель вложенного множества для хранения иерархической информации в реляционных базах данных

Рекомендации