Двойственный матроид

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

Двойственный матроид к [math] M = \; \langle X, B \rangle[/math] — это матроид [math]M^* = \; \langle X, \mathcal B^* \rangle[/math], где [math] \mathcal B^* = \; \{ \overline B |\; B \in \mathcal B \} [/math] - множество всех кобаз матроида [math]M.[/math]

Теорема:

Множество [math]B^*[/math] удовлетворяет аксиомам баз.

Доказательство:

[math]\triangleright[/math]

1. Пусть [math]B_1, B_2 \in \mathcal B.[/math] [math]B_1 \subseteq B_2 \Leftrightarrow \overline {B_1} \supseteq \overline {B_2}.[/math] Тогда по первой аксиоме для [math]B_{1,2} [/math] [math]: \overline {B_2} = \overline {B_1}.[/math] 2. Пусть [math] \overline{B_1}, \overline {B_2} \in \mathcal B^*[/math] и [math] p\in \overline{B_1}.[/math] Так как [math] p\notin {B_1},[/math] то в [math] B_1 \cup p [/math] имеется точно один цикл [math]C[/math]. Поскольку цикл [math]C[/math] не лежит в [math]B_2[/math], существует [math]q \in C \cap \overline {B_2}.[/math] Множество [math](B_1 \cup p) \setminus q[/math] не содержит циклов, т.к. разрушен единственный цикл. Поэтому оно независимо и [math]|(B_1 \cup p) \setminus q| = |B_1|.[/math] Следовательно, [math] (B_1 \cup p) \setminus q[/math] - база. Тогда [math]\overline {(B_1 \cup p \setminus q)} = \overline {(B_1 \cup p)} \cup q = (\overline {B_1} \setminus p) \cup q,[/math] где [math]q \in \overline {B_2}.[/math] То есть выполняется вторая аксиома баз.

[math]\triangleleft[/math]

Эта статья находится в разработке!

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

Двойственный матроид к [math] M = \; \langle X, I \rangle[/math] — это матроид [math]M^* = \langle X, I^* \rangle[/math], где [math]I^* = \{A\ |\ \exists B \in \mathcal B: A \cap B = \varnothing\}[/math]

Лемма:

Пусть [math] A \in I [/math]. Тогда [math] \exists B \in \mathcal B: A \in B [/math]

Доказательство:

[math]\triangleright[/math]

Докажем от противного. Пускай [math] C \in I [/math] - множество максимального размера среди таких, что [math] A \in C [/math], причём [math] C [/math] не база. Возмём также какое-нибудь [math] B \in \mathcal B[/math]. Раз [math] C [/math] не база, то [math] |C| \lt |B| [/math]. В таком случае по 3-ему свойству матроида [math] \exists b \in B: C \cap b \in I [/math]. Получили противоречие, поскольку [math] C \cap b [/math] имеет большую мощность чем [math] C [/math].

[math]\triangleleft[/math]

Теорема:

Определения 1 и 2 эквивалентны.

Доказательство:

[math]\triangleright[/math]

Положим [math] M^* = \; \langle X, I \rangle [/math]; [math] M_1^* = \; \langle X, I_1 \rangle [/math] - двойственный к нему матроид по первому определению, [math] M_2^* = \; \langle X, I_2 \rangle [/math] - по второму. Требуется показать, что [math] I_1 = I_2 [/math] [math] A \in I_1 \Rightarrow A \in I_2 [/math] Дополним [math] A [/math] до базы ([math] B [/math]). [math]B \in I_1 \Rightarrow \overline B \in I [/math]. Поскольку [math] B \cap \overline B = \varnothing [/math], то [math] B \in I_2 [/math]. Так как [math] A \in B [/math], то [math] A \cap \overline B = \varnothing [/math] [math] A \in I_2 \Rightarrow A \in I_1 [/math] Возьмём [math] B: A \cap B = \varnothing [/math]. [math] \overline B \in I_1,\ I_2 [/math]. [math] A \in \overline B \Rightarrow A \in I_1[/math]

[math]\triangleleft[/math]

См.также

• Аксиоматизация матроида базами