Что такое матроид

Материал из Algocode wiki
Версия от 20:25, 4 февраля 2020; NekoKarp (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Определение:
Матроид —это пара множеств $\langle X,I\rangle$, где $X$ - некоторое множество, называемое носителем матроида, а $I$ - некоторое подмножество множества $X$ ($I\subset 2^X$). Для данной пары выполнены 3 аксиомы матроидов:

  • Пустое множество принадлежит $I$ ($\emptyset \in I$)
  • Подмножество множества, принадлежащего $I$ тоже принадлежит $I$ ($A \in I; B\subset A \Rightarrow B \in I$)
  • Если множества $A$ и $B$ принадлежат $I$ и мощность $A$ меньше мощности $B$, то существует хотя бы один элемент $b$ множества $B$ такой, что $A\cup b$ принадлежит $I$ ($A,B \in I, $|$A$|$<$|$B$|$ \Rightarrow \exists b \in B: A\cup b \in I$)

Определение:
Независимое множество —это множество $A \in I$ для данного $X$

Определение:
Зависимое множество —это множество $A \notin I$ для данного $X$


Определение:
Базис матроида —это любое независимое множество данного матроида, добавление в которое элемента всегда делает его зависимым ($A$ - базис $\langle X,I\rangle \Leftrightarrow \forall x \notin A: A\cup x \notin I$)

Свойства базиса матроида

Утверждение:
Все базисы матроида имеют одинаковую мощность

Доказательство:
Пусть $\exists A,B$ - базисы $\langle X,I \rangle$ такие, что |$ A $|$ < $|$ B $| $ \Rightarrow$ по третьей аксиоме матроидов $\exists b \in B:A\cup b \in I \Rightarrow A$ - не базис

Утверждение:
Никакой базис не является подмножеством другого базиса

Доказательство данного факта тривиально

Утверждение:
Любое множество $A\in I$ не являющееся базисом - подмножество хотя бы одного базиса

Доказательство данного факта тривиально

Утверждение:
Для описания матроида достаточно описания всех его базисов

Доказательство данного факта тривиально


Определение:
Цикл —это любое зависимое множество, каждое подмножество которого(исключая его самого) независимо

Свойства циклов

Утверждение:
Любое зависимое множество имеет хотя бы одно подмножество-цикл

Доказательство:
Пусть существует зависимое множество, ни одно подмножество которого(включая его самого) не является циклом, тогда рассмотрим наименьшее по размеру его подмножество, являющееся зависимым, заметим, что удаление любого элемента из него будет делать наше множество зависимым $\Rightarrow$ мы получили цикл

Утверждение:
Никакой цикл не является подмножеством другого цикла

Доказательство данного факта тривиально

Утверждение:
Для описания матроида достаточно описания всех его циклов

Доказательство данного факта тривиально

Утверждение:
Из объединения двух циклов можно удалить любой элемент и полученное множество будет всё равно содержать цикл

Доказательство остаётся читателю в качестве упражнения


Определение:
Ранг(также ранговая функция $r(S)$, где $S$ - подмножество $X$) —это максимальное независимое подмножество для данного подмножества

Свойства рангов

Утверждение:
Ранг множества не больше его размера

Доказательство данного факта тривиально

Утверждение:
Ранг независимого множества равен его размеру

Доказательство данного факта тривиально

Утверждение:
Ранг носителя матроида - размер базисов

Доказательство данного факта тривиально

Утверждение:
Ранг пустого множества = 0

Доказательство данного факта тривиально

Утверждение:
Ранг множества не меньше ранга любого его подмножества

Доказательство:
Любое подмножество подмножества тоже является подмножеством текущего множества $\Rightarrow$ наибольшее независимое подмножество подмножества данного множества является подмножеством исходного множества $\Rightarrow$ если предположить, что ранг данного множества меньше чем у его подмножества, то возникнет противоречие, тк наибольшее независимое подмножество того подмножества будет подмножеством исходного множества $\Rightarrow$ его размер учтётся при нахождении ранга, а значит он будет не меньше, чем ранг подмножества

Утверждение:
Добавление элемента в множество увеличивает его ранг не более, чем на 1 ($\forall S\in 2^X; x\notin S:r(S)\le r(S\cup x)\le r(S)+1$)

Доказательство данного факта тривиально


Определение:
Оракул независимости —это функция, определяющая зависимость множества(из-за экспоненциального кол-ва подмножеств не представляется возможным хранить эту информацию в явном виде)

Примеры матроидов

Определение:
Универсальный матроид —это матроид, все подмножества которого мощностью не более некоего $k$ и только они независимы

Определение:
Линейный матроид —это матроид на множестве векторов, подмножество которого независимо, если все вектора в нём линейно независимы, что значит, что нельзя представить никакой из векторов в множестве суммой остальных ни с какими коэффициентами С этого матроида и появилась сама концепция оного, а также больша́я часть терминов: зависимое/независимое множество, базис итд

Определение:
Цветной матроид —это матроид на множестве элементов, каждый из которых имеет свой цвет. Подмножество в нём независимо, если цвета всех его элементов различны

Определение:
Графовый матроид —это матроид на рёбрах данного неориентированного графа множество рёбер независимо, если не содержит цикла Именно из-за данного матроида зависимое множество, которое при удалении любого элемента становится независимым, называется циклом(несложно доказать, что в графовом матроиде циклы являютс яциклами в исходном графе)



Автор конспекта: Карп

По всем вопросам пишите в telegram @KS20031501