137
правок
Изменения
→Partition Matroid
==Бинарный матроид==
==Partition MatroidРазделенный матроид=={{Определение|definition=Пусть <tex>X = \bigcup\limits_{i=_1}^n X_i</tex>, при этом <tex> X_i \cap X_j = 0 \forall i \neq j,</tex> и <tex>k_1 \dots k_n</tex> — положительные целые числа. <tex>I = \mathcal{f} A \subset X \mid \left\vert A \cap X_i \right\vert \leqslant k_i, \forall i: 1 \leqslant i \leqslant n \mathcal {g}</tex>. Тогда <tex>M = \langle X, I \rangle </tex> называют '''разделенным матроидом (partition matroid)''' }} {{Лемма|statement = Разделенный матроид является матроидом.|proof = Проверим выполнение аксиом независимости: 1) <tex>\varnothing \in I</tex> <tex>\left\vert \varnothing \cap X_i \right\vert = 0 \leqslant k_i \Rightarrow \varnothing \in I</tex> 2) <tex>A \subset B, B \in I \Rightarrow A \in I</tex> <tex>A \subset B, \left\vert A \right\vert \leqslant \left\vert B \right\vert \Rightarrow \left\vert A \cap X_i \right\vert \leqslant \left\vert B \cap X_i \right\vert \leqslant k_i \Rightarrow A \in I</tex> 3) <tex>A \in I, B \in I, \left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \mathcal {9} x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \in I</tex> Предположим, что <tex>\forall x \in B \setminus A, A \cup \mathcal{f} x \mathcal {g} \notin I \Rightarrow \exists X_j, k_j: \left\vert A \cup \mathcal{f} x \mathcal {g} \cap X_j \right\vert > k_j</tex>, но так как <tex>A \in I</tex>, то есть <tex> \left\vert A \cap X_j \right\vert \leqslant k_j \Rightarrow x \in X_j</tex> ... }}
==Laminar Matroid==
