Что такое матроид: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
м (Добавлены категории)
(Изменено обозначение мощности множеств)
Строка 4: Строка 4:
 
* Пустое множество принадлежит $I$ ($\emptyset \in I$)
 
* Пустое множество принадлежит $I$ ($\emptyset \in I$)
 
* Подмножество множества, принадлежащего $I$ тоже принадлежит $I$ ($A \in I; B\subset A \Rightarrow B \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, \overline {\overline A}<\overline {\overline B} \Rightarrow \exists b \in B: A\cup b \in I$)
+
* Если множества $A$ и $B$ принадлежат $I$ и мощность $A$ меньше мощности $B$, то существует хотя бы один элемент $b$ множества $B$ такой, что $A\cup b$ принадлежит $I$ ($A,B \in I, $&#124;$A$&#124;$<$&#124;$B$&#124;$ \Rightarrow \exists b \in B: A\cup b \in I$)
 
}}
 
}}
 
{{Определение
 
{{Определение
Строка 21: Строка 21:
 
{{Утверждение
 
{{Утверждение
 
|Утверждение=Все базисы матроида имеют одинаковую мощность
 
|Утверждение=Все базисы матроида имеют одинаковую мощность
|Доказательство=Пусть $\exists A,B$ - базисы $\langle X,I \rangle$ такие, что $\overline{\overline A} < \overline{\overline B} \Rightarrow$ по третьей аксиоме матроидов $\exists b \in B:A\cup b \in I \Rightarrow A$ - не базис
+
|Доказательство=Пусть $\exists A,B$ - базисы $\langle X,I \rangle$ такие, что &#124;$ A  
 +
$&#124;$ < $&#124;$ B $&#124; $ \Rightarrow$ по третьей аксиоме матроидов $\exists b \in B:A\cup b \in I \Rightarrow A$ - не базис
 
}}
 
}}
 
{{Утверждение
 
{{Утверждение

Версия 16:47, 2 февраля 2020

Определение:
Матроид —это пара множеств $\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$ не являющееся базисом - подмножество хотя бы одного базиса

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

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

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



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

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