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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Теорема |about= об аксиоматизации матроида базами |statement= Пусть семейство <tex>\mathcal B</tex> подмно…»)
 
м (rollbackEdits.php mass rollback)
 
(не показано 14 промежуточных версий 7 участников)
Строка 2: Строка 2:
 
|about=
 
|about=
 
об аксиоматизации матроида базами
 
об аксиоматизации матроида базами
|statement= Пусть семейство <tex>\mathcal B</tex> подмножеств конечного непустого множества <tex>E</tex> удовлетворяет условиям всем условиям [[Теорема о базах|теоремы о базах]], где играет роль <tex>B_s</tex>. Тогда <tex>\mathcal B</tex> является семейством баз однозначно определенного матроида на <tex>E</tex>.
+
|statement= Пусть семейство <tex>\mathcal B</tex> подмножеств конечного непустого множества <tex>E</tex> удовлетворяет условиям<br>
|proof= Покажем, что все множества из <tex>\mathcal B</tex> равномощны. Пусть <tex>B_1, B_2\in\mathcal B, |B_1|=t, B_1=\{b_1,b_2,\ldots ,b_t\}</tex>. По третьему условию существует <tex>c_1\in B_2</tex> такой, что <tex>\{c_1,b_2,\ldots,b_t\}\in\mathcal B</tex>.  <tex>c_1\notin\{b_2,\ldots,b_t\}</tex> в силу условия 2. Аналогично, существует <tex>c_2\in B_2</tex> такой, что <tex>\{c_1,c_2,b_3,\ldots,b_t\}\in\mathcal B</tex> и <tex>c_2\notin\{c_1,b_3,\ldots,b_t\}</tex>. Продолжая этот процесс, получим <tex>\{c_1,c_2,\ldots,c_t\}\in\mathcal B</tex> для некоторых попарно различных элементов <tex>c_1,c_2,\ldots,c_t\in B_2</tex>. В силу аксиомы 2 получаем <tex>\{c_1,c_2,\ldots,c_t\}=B_2</tex>, т.е. <tex>|B_2|=t=|B_1|</tex>.<br>
+
# <tex>\mathcal B \ne \varnothing</tex>.
 +
# Если <tex>B_1, B_2 \in \mathcal B</tex> и <tex>B_1 \ne B_2</tex>, то <tex>B_1 \nsubseteq B_2</tex> и <tex>B_2 \nsubseteq B_1</tex>.
 +
# Если <tex>B_1, B_2 \in \mathcal B</tex>, то для <tex>\forall b_1 \in B_1 \: \exists b_2 \in B_2 </tex> такой, что <tex>(B_1 \setminus b_1) \cup b_2 \in \mathcal B</tex>.
 +
Тогда <tex>\mathcal B</tex> является семейством баз однозначно определенного [[Определение матроида|матроида]] на <tex>E</tex>.
 +
|proof= Покажем, что все <tex>\mathcal B</tex>-множества равномощны. Пусть <tex>B_1, B_2\in\mathcal B, |B_1|=t, B_1=\{b_1,b_2,\ldots ,b_t\}</tex>. По третьему условию существует <tex>c_1\in B_2</tex> такой, что <tex>\{c_1,b_2,\ldots,b_t\}\in\mathcal B</tex>.  <tex>c_1\notin\{b_2,\ldots,b_t\}</tex> в силу условия 2. Аналогично, существует <tex>c_2\in B_2</tex> такой, что <tex>\{c_1,c_2,b_3,\ldots,b_t\}\in\mathcal B</tex> и <tex>c_2\notin\{c_1,b_3,\ldots,b_t\}</tex>. Продолжая этот процесс, получим <tex>\{c_1,c_2,\ldots,c_t\}\in\mathcal B</tex> для некоторых попарно различных элементов <tex>c_1,c_2,\ldots,c_t\in B_2</tex>. В силу второго условия получаем <tex>\{c_1,c_2,\ldots,c_t\}=B_2</tex>, т.е. <tex>|B_2|=t=|B_1|</tex>.<br>
 
Подмножество <tex>A</tex> из <tex>E</tex> будем называть <tex>\mathcal B</tex>''-независимым'', если оно содержится в некотором <tex>\mathcal B</tex>-множестве. Ясно, что <tex>\mathcal B</tex>-множества - это максимальные <tex>\mathcal B</tex>-независимые множества. Обозначим через <tex>\mathcal I</tex> совокупность всех <tex>\mathcal B</tex>-независимых множеств.<br>
 
Подмножество <tex>A</tex> из <tex>E</tex> будем называть <tex>\mathcal B</tex>''-независимым'', если оно содержится в некотором <tex>\mathcal B</tex>-множестве. Ясно, что <tex>\mathcal B</tex>-множества - это максимальные <tex>\mathcal B</tex>-независимые множества. Обозначим через <tex>\mathcal I</tex> совокупность всех <tex>\mathcal B</tex>-независимых множеств.<br>
Заметим, что семейство <tex>\mathcal I</tex> удовлетворяет условиям 1 и 2 [[Определение матроида|определения матроида]]. Осталось проверить, что семейство <tex>\mathcal I</tex> удовлетворяет третьему условию. Пусть <tex>I,J\in\mathcal I, |I|<|J|</tex>. Зафиксируем <tex>\mathcal B</tex>-множество <tex>B_2</tex>, содержащее <tex>J</tex>. Среди <tex>\mathcal B</tex>-множеств, содержащих <tex>\mathcal I</tex>, выберем такое <tex>\mathcal B</tex>-множество <tex>B_1</tex>, для которого пересечение <tex>B_1\cap B_2</tex> содержит наибольшее возможное число элементов. Покажем, что <tex>B_1\backslash I\subseteq B_2</tex>. Действительно, если существует <tex>b_1\in B_1\backslash I</tex> такой, что <tex>b_1\notin B_2</tex>, то по условию 3 [[Теорема о базах|теоремы о базах]] существует <tex>b_2\in B_2</tex>, для которого <tex>B=(B_1\backslash b_1)\cup b_2\in\mathcal B</tex> и <tex>b_1\neq b_2</tex>, т.к. <tex>b_1\notin B_2</tex>, а <tex>b_2\in B_2</tex>. Тогда <tex>|B\cap B_2|>|B_1\cap B_2|</tex>, что невозможно, поскольку <tex>I\subseteq B</tex>.<br>
+
Заметим, что семейство <tex>\mathcal I</tex> удовлетворяет [[Определение матроида|аксиомам 1 и 2]] матроида. Осталось проверить, что семейство <tex>\mathcal I</tex> удовлетворяет третьей аксиоме. Пусть <tex>I,J\in\mathcal I, |I|<|J|</tex>. Зафиксируем <tex>\mathcal B</tex>-множество <tex>B_2</tex>, содержащее <tex>J</tex>. Среди <tex>\mathcal B</tex>-множеств, содержащих <tex>I</tex>, выберем такое <tex>\mathcal B</tex>-множество <tex>B_1</tex>, для которого пересечение <tex>B_1\cap B_2</tex> содержит наибольшее возможное число элементов. Покажем, что <tex>B_1\backslash I\subseteq B_2</tex>. Действительно, если существует <tex>b_1\in B_1\backslash I</tex> такой, что <tex>b_1\notin B_2</tex>, то по условию 3 существует <tex>b_2\in B_2</tex>, для которого <tex>B=(B_1\backslash b_1)\cup b_2\in\mathcal B</tex> и <tex>b_1\neq b_2</tex>, т.к. <tex>b_1\notin B_2</tex>, а <tex>b_2\in B_2</tex>. Тогда <tex>|B\cap B_2|>|B_1\cap B_2|</tex>, что невозможно, поскольку <tex>I\subseteq B</tex>.<br>
 
Таким образом, <tex>B_1\backslash I,J\subseteq B_2</tex>, причем <tex>|B_1\backslash I|+|J|=|B_1|-|I|+|J|>|B_1|=|B_2|</tex>. Следовательно, существует <tex>p\in(B_1\backslash I)\cap J</tex>. Так как <tex>I\cup p\subseteq B_1</tex> и <tex>p\in J\backslash I</tex>, элемент <tex>p</tex> является искомым.
 
Таким образом, <tex>B_1\backslash I,J\subseteq B_2</tex>, причем <tex>|B_1\backslash I|+|J|=|B_1|-|I|+|J|>|B_1|=|B_2|</tex>. Следовательно, существует <tex>p\in(B_1\backslash I)\cap J</tex>. Так как <tex>I\cup p\subseteq B_1</tex> и <tex>p\in J\backslash I</tex>, элемент <tex>p</tex> является искомым.
 
}}
 
}}
 +
 +
== См. также ==
 +
* [[Теорема о базах|Теорема о базах]]
 +
* [[Аксиоматизация матроида циклами|Аксиоматизация матроида циклами]]
 +
 +
== Источники информации ==
 +
* [https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture14.pdf Chandra Chekuri: Combinatorial Optimization, Lecture 14 - Introduction to Matroids]
 +
* Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: Графы, матроиды, алгоритмы — стр. 86 — ISBN 978-5-8114-1068-2
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Матроиды]]
 +
[[Категория: Основные факты теории матроидов]]

Текущая версия на 19:22, 4 сентября 2022

Теорема (об аксиоматизации матроида базами):
Пусть семейство [math]\mathcal B[/math] подмножеств конечного непустого множества [math]E[/math] удовлетворяет условиям
  1. [math]\mathcal B \ne \varnothing[/math].
  2. Если [math]B_1, B_2 \in \mathcal B[/math] и [math]B_1 \ne B_2[/math], то [math]B_1 \nsubseteq B_2[/math] и [math]B_2 \nsubseteq B_1[/math].
  3. Если [math]B_1, B_2 \in \mathcal B[/math], то для [math]\forall b_1 \in B_1 \: \exists b_2 \in B_2 [/math] такой, что [math](B_1 \setminus b_1) \cup b_2 \in \mathcal B[/math].
Тогда [math]\mathcal B[/math] является семейством баз однозначно определенного матроида на [math]E[/math].
Доказательство:
[math]\triangleright[/math]

Покажем, что все [math]\mathcal B[/math]-множества равномощны. Пусть [math]B_1, B_2\in\mathcal B, |B_1|=t, B_1=\{b_1,b_2,\ldots ,b_t\}[/math]. По третьему условию существует [math]c_1\in B_2[/math] такой, что [math]\{c_1,b_2,\ldots,b_t\}\in\mathcal B[/math]. [math]c_1\notin\{b_2,\ldots,b_t\}[/math] в силу условия 2. Аналогично, существует [math]c_2\in B_2[/math] такой, что [math]\{c_1,c_2,b_3,\ldots,b_t\}\in\mathcal B[/math] и [math]c_2\notin\{c_1,b_3,\ldots,b_t\}[/math]. Продолжая этот процесс, получим [math]\{c_1,c_2,\ldots,c_t\}\in\mathcal B[/math] для некоторых попарно различных элементов [math]c_1,c_2,\ldots,c_t\in B_2[/math]. В силу второго условия получаем [math]\{c_1,c_2,\ldots,c_t\}=B_2[/math], т.е. [math]|B_2|=t=|B_1|[/math].
Подмножество [math]A[/math] из [math]E[/math] будем называть [math]\mathcal B[/math]-независимым, если оно содержится в некотором [math]\mathcal B[/math]-множестве. Ясно, что [math]\mathcal B[/math]-множества - это максимальные [math]\mathcal B[/math]-независимые множества. Обозначим через [math]\mathcal I[/math] совокупность всех [math]\mathcal B[/math]-независимых множеств.
Заметим, что семейство [math]\mathcal I[/math] удовлетворяет аксиомам 1 и 2 матроида. Осталось проверить, что семейство [math]\mathcal I[/math] удовлетворяет третьей аксиоме. Пусть [math]I,J\in\mathcal I, |I|\lt |J|[/math]. Зафиксируем [math]\mathcal B[/math]-множество [math]B_2[/math], содержащее [math]J[/math]. Среди [math]\mathcal B[/math]-множеств, содержащих [math]I[/math], выберем такое [math]\mathcal B[/math]-множество [math]B_1[/math], для которого пересечение [math]B_1\cap B_2[/math] содержит наибольшее возможное число элементов. Покажем, что [math]B_1\backslash I\subseteq B_2[/math]. Действительно, если существует [math]b_1\in B_1\backslash I[/math] такой, что [math]b_1\notin B_2[/math], то по условию 3 существует [math]b_2\in B_2[/math], для которого [math]B=(B_1\backslash b_1)\cup b_2\in\mathcal B[/math] и [math]b_1\neq b_2[/math], т.к. [math]b_1\notin B_2[/math], а [math]b_2\in B_2[/math]. Тогда [math]|B\cap B_2|\gt |B_1\cap B_2|[/math], что невозможно, поскольку [math]I\subseteq B[/math].

Таким образом, [math]B_1\backslash I,J\subseteq B_2[/math], причем [math]|B_1\backslash I|+|J|=|B_1|-|I|+|J|\gt |B_1|=|B_2|[/math]. Следовательно, существует [math]p\in(B_1\backslash I)\cap J[/math]. Так как [math]I\cup p\subseteq B_1[/math] и [math]p\in J\backslash I[/math], элемент [math]p[/math] является искомым.
[math]\triangleleft[/math]

См. также

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