Аксиоматизация матроида базами

Материал из Викиконспекты
Версия от 00:35, 7 июня 2011; 192.168.0.2 (обсуждение) (Новая страница: «{{Теорема |about= об аксиоматизации матроида базами |statement= Пусть семейство <tex>\mathcal B</tex> подмно…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Теорема (об аксиоматизации матроида базами):
Пусть семейство [math]\mathcal B[/math] подмножеств конечного непустого множества [math]E[/math] удовлетворяет условиям всем условиям теоремы о базах, где играет роль [math]B_s[/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]. В силу аксиомы 2 получаем [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]\mathcal 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]