В комбинаторной математике , система независимости S представляет собой пару ( V , I ), где V представляет собой конечное множество , и я представляет собой набор подмножеств из V (называемый независимые наборы или допустимые множества ) со следующими свойствами:
- Пустое множество является независимым, т.е. ∅ ∈ I . (В качестве альтернативы, по крайней мере, одно подмножество V является независимым, т. Е. I ≠ ∅.)
- Каждое подмножество независимого множества не зависит, то есть для каждого Y ⊆ X, мы имеем X ∈ I → Y ∈ I . Иногда это называют наследственным свойством или закрытостью вниз .
Другой термин для обозначения системы независимости - абстрактный симплициальный комплекс .
Отношение к другим концепциям
1. Пара ( V , I ), где V представляет собой конечное множество , и я представляет собой набор подмножеств из V, также называется Гиперграф . При использовании этой терминологии элементы множества V называются вершинами, а элементы семейства I - гиперребрами . Таким образом, систему независимости можно кратко определить как гиперграф, замкнутый вниз.
2. Система независимости с дополнительным свойством, называемым свойством увеличения или свойством обмена, дает матроид . Следующее выражение суммирует отношения между терминами:
ГИПЕРГРАФЫ ⊃ НЕЗАВИСИМОСТЬ-СИСТЕМЫ = АБСТРАКТ-ПРОСТО-КОМПЛЕКСЫ ⊃ МАТРОИДЫ.
Рекомендации
- Бонди, Адриан ; Мурти, USR (2008), Теория графов , Тексты для выпускников по математике, 244 , Springer, стр. 195, ISBN 9781846289699.