Двойственный матроид — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (См.также)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 +
|about=1
 
|definition=
 
|definition=
'''Двойственный матроид к <tex> M = \; \langle X, B \rangle</tex>''' - это матроид <tex>M^* = \; \langle X, B^* \rangle</tex>, где <tex> B^* = \; ({\overline {\beta} |\; \beta \in B})</tex> - множество всех кобаз матроида <tex>M.</tex>
+
'''Двойственный матроид к <tex> M = \; \langle X, B \rangle</tex>''' - это матроид <tex>M^* = \; \langle X, B^* \rangle</tex>, где <tex> B^* = \; ({\overline {\beta} |\; \beta \in \mathcal B})</tex> - множество всех кобаз матроида <tex>M.</tex>
 
}}
 
}}
 
{{Теорема
 
{{Теорема
Строка 10: Строка 11:
 
* 2. Пусть <tex> \overline{B_1}, \overline {B_2} \in B^*</tex>  и  <tex> p\in \overline{B_1}.</tex> Так как <tex> p\notin {B_1},</tex> то в <tex> B_1 \cup p </tex> имеется точно один цикл <tex>C</tex>. Поскольку цикл <tex>C</tex> не лежит в <tex>B_2</tex>, существует <tex>q \in C \cap \overline {B_2}.</tex> Множество <tex>(B_1 \cup p) \setminus q</tex> не содержит циклов, т.к. разрушен единственный цикл. Поэтому оно независимо и <tex>|(B_1 \cup p) \setminus q| = |B_1|.</tex> Следовательно, <tex> (B_1 \cup p) \setminus q</tex> - база. Тогда <tex>\overline {(B_1 \cup p \setminus q)} = \overline {(B_1 \cup p)} \cup q = (\overline {B_1} \setminus p) \cup q,</tex> где <tex>q \in \overline {B_2}.</tex> То есть выполняется вторая аксиома баз.
 
* 2. Пусть <tex> \overline{B_1}, \overline {B_2} \in B^*</tex>  и  <tex> p\in \overline{B_1}.</tex> Так как <tex> p\notin {B_1},</tex> то в <tex> B_1 \cup p </tex> имеется точно один цикл <tex>C</tex>. Поскольку цикл <tex>C</tex> не лежит в <tex>B_2</tex>, существует <tex>q \in C \cap \overline {B_2}.</tex> Множество <tex>(B_1 \cup p) \setminus q</tex> не содержит циклов, т.к. разрушен единственный цикл. Поэтому оно независимо и <tex>|(B_1 \cup p) \setminus q| = |B_1|.</tex> Следовательно, <tex> (B_1 \cup p) \setminus q</tex> - база. Тогда <tex>\overline {(B_1 \cup p \setminus q)} = \overline {(B_1 \cup p)} \cup q = (\overline {B_1} \setminus p) \cup q,</tex> где <tex>q \in \overline {B_2}.</tex> То есть выполняется вторая аксиома баз.
 
}}
 
}}
 +
 +
{{Определение
 +
|about=2
 +
|definition=
 +
'''Двойственный матроид к <tex> M = \; \langle X, I \rangle</tex>''' - это матроид <tex>M^* = \langle X, I^* \rangle</tex>, где <tex>I^* = \{A\ |\ \exists B \in \mathcal B,  A \cap B = \varnothing\}</tex>
 +
}}
 +
 +
 +
{{Теорема
 +
|statement=Определения 1 и 2 эквивалентны.
 +
|proof=
 +
Положим <tex> M^* = \; \langle X, I \rangle </tex>; <tex> M_1^* = \; \langle X, I_1 \rangle </tex> - двойственный к нему матроид по первому определению, <tex> M_2^* = \; \langle X, I_2 \rangle </tex> - по второму.
 +
 +
Требуется показать, что <tex> I_1 = I_2 </tex>
 +
* <tex> A \in I_1 \Rightarrow A \in I_2 </tex>
 +
*: Дополним <tex> A </tex> до базы (<tex> B </tex>). <tex>B \in I_1 \Rightarrow \overline B \in I </tex>. Поскольку <tex> B \cap \overline B = \varnothing </tex>, то <tex> B \in I_2 </tex>. Так как <tex> A \in B </tex>, то <tex> A \cap \overline B = \varnothing </tex> 
 +
 +
* <tex> A \in I_2 \Rightarrow A \in I_1 </tex>
 +
*:
 +
}}
 +
 
== См.также ==
 
== См.также ==
 
*[[Аксиоматизация матроида базами]]
 
*[[Аксиоматизация матроида базами]]

Версия 23:33, 13 мая 2014

Определение:
Двойственный матроид к [math] M = \; \langle X, B \rangle[/math] - это матроид [math]M^* = \; \langle X, B^* \rangle[/math], где [math] B^* = \; ({\overline {\beta} |\; \beta \in \mathcal B})[/math] - множество всех кобаз матроида [math]M.[/math]
Теорема:
Множество [math]B^*[/math] удовлетворяет аксиомам баз.
Доказательство:
[math]\triangleright[/math]
  • 1. Пусть [math]B_1, B_2 \in 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 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]


Теорема:
Определения 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]\triangleleft[/math]

См.также