Система независимости

В комбинаторной математике система независимости ⁠ $S$⁠ это пара $(V,{\mathcal {I}})$, где ⁠ $V$⁠ — конечное множество и ⁠ ${\mathcal {I}}$⁠ — совокупность подмножеств ⁠ это $V$⁠ (называемые независимыми множествами или допустимыми множествами ) со следующими свойствами:

1. Пустое множество независимо, т.е. $\emptyset \in {\mathcal {I}}$. (В качестве альтернативы, хотя бы одно подмножество ⁠ $V$⁠ независим, т. е. ${\mathcal {I}}\neq \emptyset$.)
2. Каждое подмножество независимого множества независимо, т. е. для каждого $Y\subseteq X$, у нас есть $X\in {\mathcal {I}}\Rightarrow Y\in {\mathcal {I}}$. Иногда это называют наследственной собственностью или нисходящей закрытостью .

Другой термин для системы независимости — абстрактный симплициальный комплекс .

Связь с другими понятиями

• Пара $(V,{\mathcal {I}})$, где ⁠ $V$⁠ — конечное множество и ⁠ ${\mathcal {I}}$⁠ — совокупность подмножеств ⁠ это $V$⁠ , также называется гиперграфом . При использовании этой терминологии элементы множества ⁠ $V$⁠ называются вершинами и элементами семейства ⁠ ${\mathcal {I}}$⁠ называются гиперребрами . Таким образом, систему независимости можно коротко определить как замкнутый вниз гиперграф.
• Система независимости с дополнительным свойством, называемым свойством увеличения или свойством обмена независимого множества, дает матроид . Следующее выражение суммирует отношения между терминами:

  ГИПЕРГРАФЫ ⊃ НЕЗАВИСИМОСТЬ-СИСТЕМЫ = АБСТРАКТНО-СИМПЛИЦИАЛЬНЫЕ КОМПЛЕКСЫ ⊃ МАТРОИДЫ.

Ссылки

• Бонди, Адриан ; Мурти, USR (2008), Теория графов , Тексты для выпускников по математике, том. 244, Спрингер, с. 195, ISBN  9781846289699 .