Прямая сумма матроидов

Прямая сумма матроидов

Определение:

Пусть $M_1 = \langle X_1, I_1 \rangle$ и $M_2 = \langle X_2, I_2 \rangle$ — матроиды с непересекающимися носителями ($X_1 \cap X_2 = \varnothing$) и $X = X_1 \cup X_2, \ I = \{ A \mid A = A_1 \cup A_2, A_1 \in I_1, A_2 \in I_2 \}$, тогда $M_1 \oplus M_2 = \langle X, I\rangle$ называется прямой суммой матроидов.

Утверждение:

Прямая сумма матроидов является матроидом.

$\triangleright$

Докажем аксиомы независимости для $I$. 1. $\varnothing \in I$ $A_1 = \varnothing \in I_1, \ A_2 = \varnothing \in I_2 \Rightarrow A_1 \cup A_2 = \varnothing \in I$ 2. $A \subset B, \ B \in I \Rightarrow A \in I$ Пусть $B = B_1 \cup B_2, \ B_1 \in I_1, \ B_2 \in I_2$, а $A = A_1 \cup A_2, \ A_1 \subset B_1, \ A_2 \subset B_2$. Так как $A_1 \subset B_1 \Rightarrow A_1 \in I_1$ (по второй аксиоме для $I_1$). Аналогично $A_2 \in I_2$. Значит $A_1 \cup A_2 \in I$. 3. $A \in I, \ B \in I, \ \left\vert A \right\vert \lt \left\vert B \right\vert \Rightarrow \exists ~ x \in B \setminus A, \ A \cup \{ x \} \in I$ Пусть $A = A_1 \cup A_2$, $B = B_1 \cup B_2$, тогда $\left\vert A_1 \right\vert \lt \left\vert B_1 \right\vert$ или $\left\vert A_2 \right\vert \lt \left\vert B_2 \right\vert$. В первом случае из третьей аксиомы для $I_1 \Rightarrow \exists~ x \in B_1 \setminus A_1, \ A_1 \cup \{ x \} \in I_1$. Значит $A_1 \cup \{ x \} \cup A_2 \in I$. Второй случай аналогичен первому.

$\triangleleft$

Пример разложения матроида в прямую сумму

Утверждение:

Разноцветный матроид $M = \langle X, I\rangle$ можно представить в виде прямой суммы универсальных матроидов.

$\triangleright$

Занумеруем все цвета элементов в множестве $X$ от $1$ до $n$. Пусть $X_i = \mathcal{f} x \mid color(x) = i \mathcal {g}$, $I_i = \mathcal{f} A \subset X_i \mid \left\vert A \right\vert \leqslant 1 \mathcal {g}$, где $i = 1 \dots n$, то есть в $X$ элементы одного цвета, а независимыми являются множества, состоящие не более чем из $1$-ого элемента. Тогда $M_i = \langle X_i, I_i\rangle$ является универсальным матроидом. Таким образом, $M = \bigoplus\limits_{i=1}^{n} M_i = \mathcal{f} X = \bigcup\limits_{i=_1}^n X_i, \ I = \bigcup\limits_{i=_1}^n A_i \mid A_i \in I_i \mathcal {g}$.

$\triangleleft$

См. также

• Определение матроида
• Примеры матроидов

Источники информации

• Victor Reiner — Lecture on matroids and oriented matroids, p.18
• Wikipedia — Matroid

LECTURES ON MATROIDS AND ORIENTED MATROIDS VICTOR REINER