Изменения

Перейти к: навигация, поиск

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

61 байт убрано, 12:05, 13 июня 2018
Универсальный матроид
# <tex>A \subset B, \ B \in I \Rightarrow A \in I</tex>
#:<tex> \left\vert A \right\vert \leqslant \left\vert B \right\vert \leqslant k \Rightarrow \left\vert A \right\vert \leqslant k \Rightarrow A \in I </tex>
# <tex>A \in I, \ B \in I, \ \left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \mathcal {9} \exists ~ x \in B \setminus A, \ A \cup \mathcal{f} x \mathcal {g} \in I</tex>
#:Так как <tex>\left\vert A \right\vert < \left\vert B \right\vert </tex> и числа в каждом множестве различны, найдётся такое число <tex> x \in B </tex>, которое не будет принадлежать меньшему по мощности множеству <tex> A </tex>.
#:Рассмотрим <tex> A \cup \mathcal{f} x \mathcal {g\} </tex>. <tex>\left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \left\vert A \cup \mathcal{f} x \mathcal {g} \right\vert = \left\vert A \right\vert + 1 \leqslant \left\vert B \right\vert \leqslant k \Rightarrow A \cup \mathcal{f} x \mathcal {g} \in I</tex>
}}
Анонимный участник

Навигация