Аксиоматизация матроида циклами — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(Добавлено утверждение)
Строка 34: Строка 34:
 
Следствие 1 из теоремы
 
Следствие 1 из теоремы
 
|statement=  
 
|statement=  
Пусть <tex>M = \langle X, I \rangle</tex> {{---}} [[Определение матроида|матроид]]. Если <tex>X \in I</tex> и <tex>y \notin X</tex>, тогда <tex>X \cup y \in I</tex> или существует единственный цикл <tex>C \subseteq X \cup y.</tex> Более того, для любого <tex> \widehat{y} \in C, (X \cup y) \setminus \widehat{y} \in I.</tex>
+
Пусть <tex>M = \langle X, I \rangle</tex> {{---}} [[Определение матроида|матроид]]. Если <tex>A \in I</tex> и <tex>y \notin A, y \in X</tex>, тогда <tex>A \cup y \in I</tex> или существует единственный цикл <tex>C \subseteq A \cup y.</tex> Более того, для любого <tex> \widehat{y} \in C, (A \cup y) \setminus \widehat{y} \in I.</tex>
 
|proof=
 
|proof=
Если <tex>X \cup y \notin I, </tex> тогда в нем должен существовать цикл <tex>C_1.</tex> Предположим, что существует другой цикл <tex>C_2 \subseteq X \cup y, </tex> и <tex>C_1 \ne C_2.</tex> Поскольку <tex>X \in I,</tex> тогда и <tex>C_1</tex>, и <tex>C_2</tex> одновременно содержат <tex>y</tex>. По 3 пункту теоремы, <tex>(C_1 \cup C_2) \setminus y</tex> содержит цикл <tex>C.</tex> Возникает противоречие, так как <tex>(C_1 \cup C_2) \setminus y \subseteq X.</tex> Поэтому, <tex>X \cup y</tex> содержит единственный цикл <tex>C.</tex>
+
Если <tex>A \cup y \notin I, </tex> тогда в нем должен существовать цикл <tex>C_1.</tex> Предположим, что существует другой цикл <tex>C_2 \subseteq A \cup y, </tex> и <tex>C_1 \ne C_2.</tex> Поскольку <tex>A \in I,</tex> тогда и <tex>C_1</tex>, и <tex>C_2</tex> одновременно содержат <tex>y</tex>. По 3 пункту теоремы, <tex>(C_1 \cup C_2) \setminus y</tex> содержит цикл <tex>C.</tex> Возникает противоречие, так как <tex>(C_1 \cup C_2) \setminus y \subseteq A.</tex> Поэтому, <tex>A \cup y</tex> содержит единственный цикл <tex>C.</tex>
Если для какого-либо <tex>\widehat{y} \in C, (X \cup y) \setminus \widehat{y} \notin I, </tex> то <tex>(X \cup y) \setminus \widehat{y}</tex> не является независимым и содержит цикл <tex>\widehat{C}.</tex> Более того, <tex>\widehat{C} \ne C,</tex> так как <tex>\widehat{y} \notin \widehat{C}, </tex> что противоречит единственности <tex>C.</tex>
+
Если для какого-либо <tex>\widehat{y} \in C, (A \cup y) \setminus \widehat{y} \notin I, </tex> то <tex>(A \cup y) \setminus \widehat{y}</tex> не является независимым и содержит цикл <tex>\widehat{C}.</tex> Более того, <tex>\widehat{C} \ne C,</tex> так как <tex>\widehat{y} \notin \widehat{C}, </tex> что противоречит единственности <tex>C.</tex>
 
}}
 
}}
  
Строка 43: Строка 43:
 
|about=  
 
|about=  
 
Следствие 2 из теоремы
 
Следствие 2 из теоремы
 +
|statement=
 +
Пусть <tex>M = \langle X, I \rangle</tex> {{---}} матроид и <tex>\mathcal{B}</tex> {{---}} семейство его баз. Тогда для любой <tex>B \in \mathcal{B}</tex> и для любого <tex>x \in X, x \notin B</tex> существует единственный цикл <tex>C \subseteq B \cup x</tex>.
 +
|proof=
 +
Пусть, напротив, <tex>B \cup x</tex> не содержит циклов. Значит, <tex>B \cup x \in I</tex>. <tex>B</tex> {{---}} база, следовательно не существует независимых множеств большей мощности, а <tex>|B \cup x| > |B|,</tex> так как <tex>x \notin B</tex> по условию. Противоречие.
 +
По предыдущему утверждению, <tex>B \cup x</tex> содержит не более одного цикла, поэтому цикл единственный.
 +
}}
 +
 +
{{Утверждение
 +
|about=
 +
Следствие 3 из теоремы
 
|statement=  
 
|statement=  
 
Пусть <tex>M = \langle X, I \rangle</tex> {{---}} матроид и <tex>\mathcal{B}</tex> {{---}} семейство его баз. Тогда для всех <tex>B, \widehat{B} \in \mathcal{B}</tex> выполнено: для любого <tex>\widehat{x} \in \widehat{B} \setminus B</tex> существует такой <tex>x \in B \setminus \widehat{B}, </tex> что <tex>(B \cup \widehat{x}) \setminus x</tex> {{---}} база.
 
Пусть <tex>M = \langle X, I \rangle</tex> {{---}} матроид и <tex>\mathcal{B}</tex> {{---}} семейство его баз. Тогда для всех <tex>B, \widehat{B} \in \mathcal{B}</tex> выполнено: для любого <tex>\widehat{x} \in \widehat{B} \setminus B</tex> существует такой <tex>x \in B \setminus \widehat{B}, </tex> что <tex>(B \cup \widehat{x}) \setminus x</tex> {{---}} база.
Строка 48: Строка 58:
 
В случае, если существует <tex>x = \widehat{x}</tex>, утверждение очевидно. Рассмотрим противоположный.
 
В случае, если существует <tex>x = \widehat{x}</tex>, утверждение очевидно. Рассмотрим противоположный.
  
<tex>B</tex> {{---}} база, следовательно <tex>B \in I, </tex> при этом <tex>\widehat{x} \notin B,</tex> а <tex>B \cup \widehat{x} \notin I. </tex> Тогда, по прошлому утверждению, существует <tex>x \in C \subseteq B \cup \widehat{x}, </tex> а <tex>(B \cup \widehat{x}) \setminus x \in I.</tex>
+
<tex>B</tex> {{---}} база, следовательно <tex>B \in I, </tex> при этом <tex>\widehat{x} \notin B,</tex> а <tex>B \cup \widehat{x} \notin I, \exists !C \subseteq B \cup \widehat{x}</tex> (по предыдущему утверждению). Тогда, по утверждению 1, существует такой <tex>x \in C \subseteq B \cup \widehat{x}, </tex> что <tex>(B \cup \widehat{x}) \setminus x \in I.</tex>
 
<tex>x</tex> содержится в <tex>B \setminus \widehat{B}, </tex> так как <tex> \widehat{x} \notin B \setminus \widehat{B} \in I, </tex> а <tex>\widehat{x}</tex> и <tex>x</tex> содержатся в <tex>C, </tex> то есть принадлежат не являющемуся независимым множеству <tex>(B \setminus \widehat{B}) \cup \widehat{x}, </tex> при этом <tex>x \ne \widehat{x}. |B| = |(B \cup \widehat{x}) \setminus x|, </tex> следовательно <tex>(B \cup \widehat{x}) \setminus x</tex> {{---}} база.
 
<tex>x</tex> содержится в <tex>B \setminus \widehat{B}, </tex> так как <tex> \widehat{x} \notin B \setminus \widehat{B} \in I, </tex> а <tex>\widehat{x}</tex> и <tex>x</tex> содержатся в <tex>C, </tex> то есть принадлежат не являющемуся независимым множеству <tex>(B \setminus \widehat{B}) \cup \widehat{x}, </tex> при этом <tex>x \ne \widehat{x}. |B| = |(B \cup \widehat{x}) \setminus x|, </tex> следовательно <tex>(B \cup \widehat{x}) \setminus x</tex> {{---}} база.
 
}}
 
}}

Версия 15:14, 22 декабря 2018

Теорема (Аксиоматизация матроида циклами):
Пусть [math]\mathfrak C[/math] — семейство подмножеств конечного непустого множества [math]E[/math] такое, что:
  1. [math]\varnothing \notin \mathfrak C[/math]
  2. Если [math]C_1, C_2 \in \mathfrak C[/math] и [math]C_1 \ne C_2[/math], то [math]C_1 \nsubseteq C_2[/math] и [math]C_2 \nsubseteq C_1[/math].
  3. Если [math]C_1, C_2 \in \mathfrak C, C_1 \ne C_2[/math] и [math]p \in C_1 \cap C_2[/math], то существует [math]C \in \mathfrak C[/math] такой, что [math]C \subseteq (C_1 \cup C_2) \setminus p[/math].
Тогда семейство [math]\mathfrak C[/math] совпадает с семейством циклов однозначно определенного матроида на [math]E[/math].
Доказательство:
[math]\triangleright[/math]

Пусть семейство [math]\mathfrak C[/math] удовлетворяет условию теоремы. Множество [math]I \subseteq E[/math] назовем [math]\mathfrak C[/math]-независимым, если оно не содержит ни одного из множеств [math]C \in \mathfrak C[/math]. Через [math]\mathfrak I[/math] обозначим семейство всех [math]\mathfrak C[/math]-независимых множеств, подмножеств [math]E[/math]. Проверим, что семейство [math]\mathfrak I[/math] удовлетворяет аксиомам из определения матроида.

Поскольку [math]\varnothing \notin \mathfrak C[/math], имеем [math]\varnothing \in \mathfrak I[/math], и первая аксиома, очевидно, выполняется.

Очевидно, что если [math]A \in \mathfrak I[/math] и [math]B \subset A[/math] то [math]B \in \mathfrak I[/math], и, следовательно, вторая аксиома выполнена.

Проверим справедливость третьей аксиомы для семейства [math]\mathfrak I[/math]. Предположим, что существуют множества [math]I, J \in \mathfrak I[/math] такие, что [math]|I|\lt |J|[/math], для которых третья аксиома не выполнена. Среди всех таких пар [math]I, J[/math] выберем ту, у которой мощность [math]|I \cup J|[/math] минимальна. Положим [math]J \setminus I = \{p_1,...,p_t\}[/math]. Если [math]t = 1[/math], то, очевидно, [math]I \subset J[/math] и аксиома выполняется. Поэтому достаточно рассмотреть [math]t \geqslant 2[/math].

В силу нашего предположения [math]I \cup p_i \notin \mathfrak I[/math] для любого [math]i \in \{1,...,t\}[/math]. Следовательно, существует [math]C_i \in \mathfrak C[/math] такое, что [math]C_i \subseteq I \cup p_i[/math] и в силу [math]\mathfrak C[/math]-независимости множества [math]I[/math] имеем [math]p_i \in C_i[/math] для любого [math]i \in \{1,...,t\}[/math]. Ясно, что множества [math]C_1,...,C_t[/math] попарно различны.

Рассмотрим множество [math]C_1.[/math] Для него верно [math]p_1 \in C_1 \subseteq I \cup p_1.[/math] В силу [math]\mathfrak C[/math]-независимости [math]J[/math] существует [math]q_1 \in I \setminus J[/math] такой, что [math]q_1 \in C_1.[/math] Рассмотрим теперь множество [math](I \setminus q_1) \cup p_1.[/math]

Если [math](I \setminus q_1) \cup p_1 \notin \mathfrak I[/math], то существует [math]C' \in \mathfrak C[/math], для которого существует такое [math]C'' \in \mathfrak C,[/math] что [math]C'' \subseteq (C_1 \cup C') \setminus p_1 \subseteq I.[/math] Пришли к противоречию с условием [math]I \in \mathfrak I.[/math]

Пусть [math](I \setminus q_1) \cup p_1 \in \mathfrak I[/math]. Заметим, что [math]|((I \setminus q_1) \cup p_1) \cup J| \lt |I \cup J|[/math]. Поэтому в силу выбора пары [math]I, J[/math] для пары [math](I \setminus q_1) \cup p_1, J[/math] существует элемент [math]p_j[/math], где [math]j \geqslant 2[/math], такой, что [math](I \setminus q_1) \cup p_1 \cup p_j \in \mathfrak I[/math]. Возьмем множество [math]C_j \in \mathfrak C[/math]. Для него выполняется [math]p_j \in C_j \subseteq I \cup p_j.[/math] Если [math]q_1 \notin C_j[/math], то [math]C_j \subseteq (I \setminus q_1) \cup p_j \subseteq (I \setminus q1) \cup p_1 \cup p_j[/math], что невозможно. Следовательно, [math]q_1 \in C_j \cap C_1[/math] и [math]C_j \ne C_1[/math]. Тогда по 3 пункуту теоремы, существует [math]C \in \mathfrak C[/math], для которого [math]C \subseteq (C_j \cup C_1) \setminus q_1 \subseteq (C_j \setminus q_1) \cup (C_1 \setminus q_1) \subseteq ((I \setminus q_1) \cup p_j) \cup ((I \setminus q_1) \cup p_1)[/math], которое равно [math](I \setminus q_10) \cup p_1 \cup p_j \in \mathfrak I[/math], что невозможно.

Итак, семейство [math]\mathfrak I[/math] удовлетворяет аксиомам матроида. Следовательно, существует матроид [math]M[/math] на множестве [math]E[/math], для которого семейство [math]\mathfrak I[/math] является семейством независимых множеств. Из определения [math]\mathfrak C[/math]-независимости легко следует, что семейство [math]\mathfrak C[/math] совпадает с множеством циклов матроида [math]M[/math]

Докажем, что матроид [math]M[/math] определен однозначно. Пусть есть два матроида [math]M_1 \neq M_2[/math] с носителем [math]E[/math], семейством циклов [math]\mathfrak C[/math] и множествами баз [math]B_1, B_2[/math] соответственно. Не ограничивая общности можно считать, что существует [math]A \in B_1, A \notin B_2[/math]. Тогда для всех [math]e \in E, e \notin A: (A \cup e) = C \in \mathfrak C[/math], но [math]\mathfrak C[/math] — семейство циклов [math]M_2[/math], следовательно для всех [math]p \in C[/math] выполнено [math](C \setminus p) \in B_2[/math], что невозможно.
[math]\triangleleft[/math]
Утверждение (Следствие 1 из теоремы):
Пусть [math]M = \langle X, I \rangle[/math]матроид. Если [math]A \in I[/math] и [math]y \notin A, y \in X[/math], тогда [math]A \cup y \in I[/math] или существует единственный цикл [math]C \subseteq A \cup y.[/math] Более того, для любого [math] \widehat{y} \in C, (A \cup y) \setminus \widehat{y} \in I.[/math]
[math]\triangleright[/math]

Если [math]A \cup y \notin I, [/math] тогда в нем должен существовать цикл [math]C_1.[/math] Предположим, что существует другой цикл [math]C_2 \subseteq A \cup y, [/math] и [math]C_1 \ne C_2.[/math] Поскольку [math]A \in I,[/math] тогда и [math]C_1[/math], и [math]C_2[/math] одновременно содержат [math]y[/math]. По 3 пункту теоремы, [math](C_1 \cup C_2) \setminus y[/math] содержит цикл [math]C.[/math] Возникает противоречие, так как [math](C_1 \cup C_2) \setminus y \subseteq A.[/math] Поэтому, [math]A \cup y[/math] содержит единственный цикл [math]C.[/math]

Если для какого-либо [math]\widehat{y} \in C, (A \cup y) \setminus \widehat{y} \notin I, [/math] то [math](A \cup y) \setminus \widehat{y}[/math] не является независимым и содержит цикл [math]\widehat{C}.[/math] Более того, [math]\widehat{C} \ne C,[/math] так как [math]\widehat{y} \notin \widehat{C}, [/math] что противоречит единственности [math]C.[/math]
[math]\triangleleft[/math]
Утверждение (Следствие 2 из теоремы):
Пусть [math]M = \langle X, I \rangle[/math] — матроид и [math]\mathcal{B}[/math] — семейство его баз. Тогда для любой [math]B \in \mathcal{B}[/math] и для любого [math]x \in X, x \notin B[/math] существует единственный цикл [math]C \subseteq B \cup x[/math].
[math]\triangleright[/math]

Пусть, напротив, [math]B \cup x[/math] не содержит циклов. Значит, [math]B \cup x \in I[/math]. [math]B[/math] — база, следовательно не существует независимых множеств большей мощности, а [math]|B \cup x| \gt |B|,[/math] так как [math]x \notin B[/math] по условию. Противоречие.

По предыдущему утверждению, [math]B \cup x[/math] содержит не более одного цикла, поэтому цикл единственный.
[math]\triangleleft[/math]
Утверждение (Следствие 3 из теоремы):
Пусть [math]M = \langle X, I \rangle[/math] — матроид и [math]\mathcal{B}[/math] — семейство его баз. Тогда для всех [math]B, \widehat{B} \in \mathcal{B}[/math] выполнено: для любого [math]\widehat{x} \in \widehat{B} \setminus B[/math] существует такой [math]x \in B \setminus \widehat{B}, [/math] что [math](B \cup \widehat{x}) \setminus x[/math] — база.
[math]\triangleright[/math]

В случае, если существует [math]x = \widehat{x}[/math], утверждение очевидно. Рассмотрим противоположный.

[math]B[/math] — база, следовательно [math]B \in I, [/math] при этом [math]\widehat{x} \notin B,[/math] а [math]B \cup \widehat{x} \notin I, \exists !C \subseteq B \cup \widehat{x}[/math] (по предыдущему утверждению). Тогда, по утверждению 1, существует такой [math]x \in C \subseteq B \cup \widehat{x}, [/math] что [math](B \cup \widehat{x}) \setminus x \in I.[/math]

[math]x[/math] содержится в [math]B \setminus \widehat{B}, [/math] так как [math] \widehat{x} \notin B \setminus \widehat{B} \in I, [/math] а [math]\widehat{x}[/math] и [math]x[/math] содержатся в [math]C, [/math] то есть принадлежат не являющемуся независимым множеству [math](B \setminus \widehat{B}) \cup \widehat{x}, [/math] при этом [math]x \ne \widehat{x}. |B| = |(B \cup \widehat{x}) \setminus x|, [/math] следовательно [math](B \cup \widehat{x}) \setminus x[/math] — база.
[math]\triangleleft[/math]

См. также

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

  • Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2