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

В комбинаторной математике, система независимости S представляет собой пару (V, I ), где V является конечным набором и I является набором подмножеств V (называемых независимыми наборами или допустимыми наборами ) со следующими свойствами:

1. пустое множество является независимым, т. е. ∅ ∈ I . (В качестве альтернативы, по крайней мере, одно подмножество V является независимым, т. Е. I ≠ ∅.)
2. Каждое подмножество независимого набора является независимым, т.е. для каждого Y ⊆ X мы имеем X ∈ I → Y ∈ I . Иногда это называют наследственным свойством или закрытием вниз .

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

1. Пара (V, I ), где V - конечное множество и I - набор подмножеств V, также является называется гиперграф. При использовании этой терминологии элементы в множестве V называются вершинами, а элементы в семействе I называются гиперребрами . Таким образом, систему независимости можно кратко определить как замкнутый вниз гиперграф.

2. Система независимости с дополнительным свойством, называемым свойством увеличения или свойством обмена, дает матроид. Следующее выражение суммирует отношения между терминами:

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

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

.

.