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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 6: Строка 6:
  
 
{{Теорема
 
{{Теорема
|statement= Множество <tex>B^*</tex> удовлетворяет [[Аксиоматизация_матроида_базами | аксиомам баз]].
+
|statement= Множество <tex>\mathcal B^*</tex> удовлетворяет [[Аксиоматизация_матроида_базами | аксиомам баз]].
 
|proof=
 
|proof=
  
* 1. Пусть <tex>B_1, B_2 \in \mathcal B.</tex> <tex>B_1 \subseteq B_2 \Leftrightarrow \overline {B_1} \supseteq \overline {B_2}.</tex> Тогда по первой аксиоме для <tex>B_{1,2} </tex> <tex>: \ \overline {B_2} = \overline {B_1}.</tex>
+
# Следует из <tex> | \mathcal B | = | \mathcal B^* | </tex>.
* 2. Пусть <tex> \overline{B_1}, \overline {B_2} \in \mathcal 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> То есть выполняется вторая аксиома баз.
+
# Пусть <tex>B_1, B_2 \in \mathcal B, \ \overline {B_1} \subseteq \overline {B_2} </tex> Тогда по второй аксиоме баз для <tex> B_{1,2}:\ </tex> <tex> \overline {B_1} \subseteq \overline {B_2} \Rightarrow B_2 \subseteq B_1 \Rightarrow B_1 = B_2 \Rightarrow \overline {B_1} = \overline {B_2} </tex>
 +
# Пусть <tex> \overline{B_1}, \overline {B_2} \in \mathcal 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> То есть выполняется третья аксиома баз.
 
}}
 
}}
 
{{В разработке}}
 
  
 
{{Определение
 
{{Определение
Строка 34: Строка 33:
 
*:: Предположим <tex> C \in I </tex> - множество максимального размера среди таких, что <tex> A \in C </tex>, причём <tex> C </tex> {{---}} не база. Возмём также какое-нибудь  <tex> B \in \mathcal B</tex>.  
 
*:: Предположим <tex> C \in I </tex> - множество максимального размера среди таких, что <tex> A \in C </tex>, причём <tex> C </tex> {{---}} не база. Возмём также какое-нибудь  <tex> B \in \mathcal B</tex>.  
 
*:: Раз <tex> C </tex> не база, то <tex> |C| < |B| </tex>. В таком случае по [[Определение_матроида | 3-ему свойству матроида]] <tex> \exists b \in B: \ C \cap b \in I </tex>. Получили противоречие, поскольку <tex> C \cap b </tex> имеет большую мощность чем <tex> C </tex>.
 
*:: Раз <tex> C </tex> не база, то <tex> |C| < |B| </tex>. В таком случае по [[Определение_матроида | 3-ему свойству матроида]] <tex> \exists b \in B: \ C \cap b \in I </tex>. Получили противоречие, поскольку <tex> C \cap b </tex> имеет большую мощность чем <tex> C </tex>.
*: Итак, возьмём <tex> B </tex> {{---}} базу <tex> M_1^* </tex>,  включающую в себя <tex> A </tex>. По '''определению 1''' <tex>B \in \mathcal B_1 \Rightarrow \overline B \in \mathcal B </tex>. Поскольку <tex> B \cap \overline B = \varnothing, A \in B </tex>, то <tex> A \cap \overline B = \varnothing </tex>. В таком случае по '''определению 2''' <tex> A \in I_2 </tex>  
+
*: Итак, возьмём <tex> B </tex> {{---}} базу <tex> M_1^* </tex>,  включающую в себя <tex> A </tex>. По '''определению 1''' <tex>B \in \mathcal B_1 \Rightarrow \overline B \in \mathcal B </tex>. Поскольку <tex> B \cap \overline B = \varnothing, A \subseteq B </tex>, то <tex> A \cap \overline B = \varnothing </tex>. В таком случае по '''определению 2''' <tex> A \in I_2 </tex>  
 
   
 
   
 
* <tex> A \in I_2 \Rightarrow A \in I_1 </tex>
 
* <tex> A \in I_2 \Rightarrow A \in I_1 </tex>
 
*: <tex> A \in I_2 </tex> означает что <tex> \exists B \in \mathcal B: \ A \cap B = \varnothing </tex>. Последнее можно записать иначе: <tex> A \subseteq \overline B </tex>.  
 
*: <tex> A \in I_2 </tex> означает что <tex> \exists B \in \mathcal B: \ A \cap B = \varnothing </tex>. Последнее можно записать иначе: <tex> A \subseteq \overline B </tex>.  
*: Кроме того <tex> B \in \mathcal B \Rightarrow \overline B \in \mathcal B_1 </tex> по определению <tex> M_1^* </tex>. Подытожив вышесказанное можем написать <tex> A \subseteq \overline B \in \mathcal B_1 </tex>, откуда следует <tex> A \in I_1 </tex>  
+
*: Кроме того <tex> B \in \mathcal B \Rightarrow \overline B \in \mathcal B_1 </tex> по определению <tex> M_1^* </tex>. То есть <tex> A \subseteq \overline B \in \mathcal B_1 </tex>, откуда следует <tex> A \in I_1 </tex>  
 
}}
 
}}
  

Версия 19:06, 25 мая 2014

Определение:
Двойственный матроид к [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]
  1. Следует из [math] | \mathcal B | = | \mathcal B^* | [/math].
  2. Пусть [math]B_1, B_2 \in \mathcal B, \ \overline {B_1} \subseteq \overline {B_2} [/math] Тогда по второй аксиоме баз для [math] B_{1,2}:\ [/math] [math] \overline {B_1} \subseteq \overline {B_2} \Rightarrow B_2 \subseteq B_1 \Rightarrow B_1 = B_2 \Rightarrow \overline {B_1} = \overline {B_2} [/math]
  3. Пусть [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]


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

См.также