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

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

Двойственный матроид (англ. dual matroid) к [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]\mathcal B^*[/math] удовлетворяет аксиомам баз.

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

[math]\triangleright[/math]

Следует из [math] | \mathcal B | = | \mathcal B^* | [/math]. Предположим [math]\overline B_1, \overline B_2 \in \mathcal B^*, \ \overline B_1 \ne \overline B_2, \ \overline {B_1} \subseteq \overline {B_2} [/math]. Тогда по второй аксиоме баз для [math] B_{1,2} \ (B_1, B_2 \in \mathcal B):\ \overline {B_1} \subseteq \overline {B_2} \Rightarrow B_2 \subseteq B_1 [/math], а определение базы гласит, что в таком случае [math] B_1 = B_2, [/math] пришли к противоречию. Пусть [math] \overline{B_1}, \overline {B_2} \in \mathcal B^*[/math] и [math] p\in \overline{B_1}.[/math]. Покажем, что в [math] B_1 \cup p [/math] содержится ровно один цикл. Так как [math] p\notin {B_1}, [/math] то по определению базы [math] B_1 \cup p \notin I [/math], а значит существует цикл [math]C \subseteq B_1 \cup p [/math]. Убедимся также, что он единственный. Положим [math] \exists C_1, C_2 \in \mathfrak C: \ C_1, C_2 \subseteq B_1 \cup p,\ C_1 \ne C_2 [/math]. Заметим, что [math] p \in C_1, C_2 [/math], в противном случае цикл не содержащий [math] p [/math] был бы подмножеством [math] B_1 [/math], что невозможно. Следовательно по 3-му свойству циклов [math] \exists C_3 \in \mathfrak C: \ C_3 \subseteq (C_1 \cup C_2) \setminus p [/math]. Но помимо этого выполнено [math] (C_1 \cup C_2) \setminus p \subseteq B_1 [/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]

Теорема:

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

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

[math]\triangleright[/math]

Введём следующие обозначения: [math] M_1^* = \; \langle X, I_1 \rangle [/math] — двойственный к [math] M [/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] \exists B \in \mathcal B: \ A \subseteq B [/math]. Предположим [math] S \in I [/math] — множество максимального размера среди таких, что [math] A \subseteq S [/math], причём [math] S [/math] — не база. Возмём также какое-нибудь [math] B \in \mathcal B[/math]. Раз [math] S [/math] не база, то [math] |S| \lt |B| [/math]. В таком случае по 3-ей аксиоме матроидов [math] \exists b \in B: \ S \cup b \in I [/math]. Получили противоречие, поскольку [math] S \cup b [/math] имеет большую мощность чем [math] S [/math]. Итак, возьмём [math] B [/math] — базу [math] M_1^* [/math], включающую в себя [math] A [/math]. По определению 1 [math]B \in \mathcal B_1 \Rightarrow \overline B \in \mathcal B [/math]. Поскольку [math] B \cap \overline B = \varnothing, A \subseteq B [/math], то [math] A \cap \overline B = \varnothing [/math]. В таком случае по определению 2 [math] A \in I_2 [/math]. [math] A \in I_2 \Rightarrow A \in I_1 [/math] [math] A \in I_2 [/math] означает что [math] \exists B \in \mathcal B: \ A \cap B = \varnothing [/math]. Последнее можно записать иначе: [math] A \subseteq \overline B [/math]. Кроме того [math] B \in \mathcal B \Rightarrow \overline B \in \mathcal B_1 [/math] по определению [math] M_1^* [/math]. Получили [math] A \subseteq \overline B \in \mathcal B_1 [/math], откуда следует [math] A \in I_1 [/math].

[math]\triangleleft[/math]

См.также

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

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

• Википедия — Двойственный матроид
• Wikipedia — Dual matroid