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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (См.также)
Строка 12: Строка 12:
 
== См.также ==
 
== См.также ==
 
*[[Аксиоматизация матроида базами]]
 
*[[Аксиоматизация матроида базами]]
 +
 +
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Матроиды]]

Версия 13:27, 2 мая 2014

Определение:
Двойственный матроид к [math] M = \; \langle X, B \rangle[/math] - это матроид [math]M^* = \; \langle X, B^* \rangle[/math], где [math] B^* = \; ({\overline {\beta} |\; \beta \in 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]

См.также