Вложенный набор - 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{quadrilateral}}\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{quadrilateral}}\subsetneq {\text{polygon}}\subsetneq {\text{shape}}\,}$

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

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

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

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

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

1. Б. Корте, Дж. Выген (2012). Комбинаторная оптимизация. Спрингер, Гейдельберг.
2. (определение на странице 221) «Электронные библиотеки и архивы: 8-я Итальянская исследовательская конференция, IRCDL 2012 - Бари, Италия, 9–10 февраля 2012 г., Отредактированные избранные статьи»под редакцией Маристелла Агости, Флориана Эспозито, Стефано Ферилли, Никола Ферро. Опубликовано в 2013 году. ISBN  9783642358340.
3. Лейн, Дэвид (2006). «Иерархия, сложность, общество». В Pumain, Дениз (ред.). Иерархия в естественных и социальных науках. Нью Йорк, Нью Йорк: Springer-Verlag. С. 81–120. ISBN  978-1-4020-4126-6.
4. Линней, Карл фон (1959). Systema naturae per regna tria naturae: второстепенные классы, обыкновенные, роды, виды, cum characteribus, дифференцис, синонимы, локусы (на латыни) (10-е изд.). Стокгольм: Impensis Direct. ISBN  0-665-53008-0. Получено 2011-09-24.