Изменения

'''Двойственный матроид''' (англ. ''dual matroid'') к <tex> M = \; \langle X, \mathcal{B } \rangle</tex> {{---}} это [[Определение_матроида | матроид]] <tex>M^* _1 = \; \langle X, \mathcal B^* _1 \rangle</tex>, где <tex> \mathcal B^* _1 = \; \{ \overline B |\; B \in \mathcal B \} </tex> {{- --}} множество всех кобаз матроида <tex>M.</tex>

|statement= Множество <tex>\mathcal B^*_1</tex> удовлетворяет [[Аксиоматизация_матроида_базами Теорема_о_базах#base_theorem | аксиомам баз]].

* 1. Пусть # Следует из <tex>B_1, B_2 | \in mathcal B | = | \mathcal B.^*_1 | </tex> . # Предположим <tex>\overline B_1 , \overline B_2 \subseteq in \mathcal B^*_1, \ \overline B_1 \ne \overline B_2 , \Leftrightarrow \overline {B_1} \supseteq subseteq \overline {B_2}.</tex> . Тогда по первой второй аксиоме баз для <tex>B_{1,2} </tex> <tex>\ (B_1, B_2 \in \mathcal B): \ \overline {B_2B_1} = \subseteq \overline {B_2} \Rightarrow B_2 \subseteq B_1}.</tex>, а [[Теорема_о_базах#definition | определение базы]] гласит, что в таком случае <tex> B_1 = B_2, </tex> пришли к противоречию.* 2. # Пусть <tex> \overline{B_1}, \overline {B_2} \in \mathcal B^*_1</tex> и <tex> p\in \overline{B_1}.</tex> #: Покажем, что в <tex> B_1 \cup p </tex> содержится ровно один цикл.#:: Так как <tex> p\notin {B_1},</tex> то в по определению базы <tex> B_1 \cup p \notin I </tex>, а значит существует цикл <tex> C \subseteq B_1 \cup p </tex> имеется точно один . #:: Убедимся также, что он единственный. Положим <tex> \exists C_1, C_2 \in \mathfrak{C}: \ C_1, C_2 \subseteq B_1 \cup p,\ C_1 \ne C_2 </tex>. Заметим, что <tex> p \in C_1, C_2 </tex>, в противном случае цикл не содержащий <tex> p </tex> был бы подмножеством <tex>B_1 </tex>, что невозможно. Следовательно по [[Теорема_о_циклах | 3-му свойству циклов]] <tex> \exists C_3 \in \mathfrak{C}: \ C_3 \subseteq (C_1 \cup C_2) \setminus p </tex>. Но помимо этого выполнено <tex> (C_1 \cup C_2) \setminus p \subseteq B_1 </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> То есть выполняется вторая третья аксиома баз.

{{В разработке}}Теорема|statement=Матроиды <tex> M^*_1 </tex> и <tex> M^*_2 </tex> совпадают.|proof=

Требуется доказать: <tex> I^*_1 = I^*_2. </tex>* <tex> A \in I^*_1 \Rightarrow A \in I^*_2 </tex>*: Для начала покажем от противного, что <tex> \exists B \in \mathcal B: \ A \subseteq B </tex>.*:: Предположим <tex> S \in I </tex> {{---}} множество максимального размера среди таких, что <tex> A \subseteq S </tex>, причём <tex> S </tex> {{Определение---}} не база. Возмём также какое-нибудь <tex> B \in \mathcal B</tex>. *:: Раз <tex> S </tex> не база, то <tex> |S| < |B|about=2</tex>. В таком случае по [[Определение_матроида |definition='''Двойственный матроид''' к 3-ей аксиоме матроидов]] <tex> M = \; exists b \in B: \ S \cup b \langle Xin I </tex>. Получили противоречие, I поскольку <tex> S \ranglecup b </tex> имеет большую мощность чем <tex> S </tex>.*: Итак, возьмём <tex> B </tex> {{---}} это матроид базу <tex> M^*_1 </tex>, включающую в себя <tex> A </tex>. Согласно определению <tex>M^* _1 </tex> выполнено <tex>B \in \mathcal B_1 \Rightarrow \overline B \in \mathcal B </tex>. Поскольку <tex> B \cap \overline B = \langle Xvarnothing, A \subseteq B </tex>, то <tex> A \cap \overline B = \varnothing </tex>. В таком случае по определению <tex> M^*_2 </tex> выполняется <tex> A \in I^* \rangle_2 </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> 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>.

|statement=Определения 1 и 2 эквивалентны.[[Определение матроида|Матроид]], двойственный к [[Примеры матроидов|матричному]] над телом <tex>F</tex>, так же является матричным над телом <tex>F</tex>

Введём следующие обозначения: : Пусть <tex> M_1^* M = \; \langle X, I_1 \mathcal{I} \rangle </tex> {{---}} двойственный к произвольный матричный матроид над телом <tex> M F</tex> матроид по первому определению : , <tex> M_2^* X = \; {1,\langle Xldots, I_2 m\rangle } </tex>, <tex>r</tex> {{---}} по второмуего [[Ранговая функция, полумодулярность|ранговая функция]]. Рассмотрим сначала крайний случай [[Примеры матроидов|тривиального]] и (двойственного к нему) [[Примеры матроидов|полного]] матроида. Они, очевидно, представимы над телом <tex>F</tex> нулевой и единичной матрицей соответственно.

Необходимо показать: Пусть теперь <tex> I_1 M</tex> {{---}} произвольный нетривиальный и не полный матричный матроид. Тогда <tex>M</tex> изоморфен матроиду столбцов некоторой <tex>(t \times m)</tex>-матрицы <tex>P</tex> над телом <tex>F</tex>. Т.к. матроид нетривиален и не полный, то <tex>rg(P) = r</tex> и <tex>0 < r < m </tex>. : Рассмотрим следующую однородную систему уравнений над пространством векторов-столбцов <tex>F^m</tex>: :: <tex>(1): PX= I_2 0</tex> .* : Для задания базиса ФСР этой системы нам достаточно<ref>[https://ru.wikipedia.org/wiki/Решение_систем_линейных_алгебраических_уравнений Википедия {{---}} Решение систем линейных алгебраических уравнений]</ref> <tex>m - r</tex> линейно независимых векторов. Пусть :: <tex> A (2): X_1, X_2,\in I_1 ldots, X_{m-r}</tex>:{{---}} базис пространства решений системы (1). Составим из этих столбцов <tex>(m \Rightarrow A times (m - r))</tex>-матрицу <tex>Q=(X_1, X_2, \in I_2 ldots, X_{m-r})</tex>. Покажем, что матроид <tex>M^*: </tex> изоморфен матроиду строк матрицы <tex>Q</tex> над телом <tex>F</tex>. Для начала покажем от противногоэтого нам достаточно установить, что система каких-либо <tex>r</tex> столбцов матрицы <tex>P</tex> линейно независима тогда и только тогда, когда линейно независима дополняющая ее система <tex>m - r</tex> строк матрицы <tex>Q</tex>. Дополняющая система строк {{---}} это система строк, номера которых дополняют номера столбцов исходной системы столбцов до множества <tex> \exists B {1,\in ldots, m\mathcal B}</tex>.  : <tex>\ A \in B Longrightarrow</tex>.*:: Предположим Возьмем произвольную систему из r столбцов матрицы <tex> C \in I P</tex> - множество максимального размера среди таких. Для простоты обозначений будем считать, что взяты первые<tex> A \in C r</tex>столбцов (мы всегда можем переставить столбцы матрицы местами, причём не поменяв характера их линейной зависимости). Пусть <tex> C P_1(t\times r)</tex> {{---}} не базаподматрица матрицы <tex>P</tex>, составленная из взятых первых <tex>r</tex> столбцов. Возмём также какоеРассмотрим однородную систему линейных уравнений над пространством векторов-нибудь столбцов <tex> B \in \mathcal BF^r</tex>. : *:: Раз :<tex> C (3): P_1Y=0</tex> не база, то :: Пусть столбцы матрицы <tex>P_1</tex> |C| линейно зависимы. Тогда система (3) имеет ненулевое решение < |B| tex>Y</tex>. В таком случае по [[Определение_матроида | 3Добавим к нему снизу <tex>m -ему свойству матроида]] r</tex> нулей, получим ненулевое решение <tex>X</tex> системы (1). Выразим <tex>X</tex> через базис (2) пространства решений системы (1)::::<tex> (4): X=\exists b alpha_1 X_1 + \in B: alpha_2 X_2 + \ C ldots + \cap b alpha_{m-r} X_{m-r}</tex>:: где среди коэффициентов есть хотя бы один ненулевой элемент из <tex>F</tex>. Введем в рассмотрение столбцы :::<tex>(5): X'_1, X'_2, \in I ldots, X'_{m-r}</tex>:: из пространства <tex>F^{m-r}</tex>. Получили противоречие, поскольку полученные соответственно из столбцов <tex> C X_1, X_2, \cap b ldots, X_{m-r}</tex> имеет большую мощность чем отбрасыванием первых <tex> C r</tex>компонент.*: ИтакСоставим из этих "урезанных" столбцов <tex> ((m - r) \times (m - r))</tex>-матрицу <tex>Q_1 = (X'_1, X'_2, \ldots, возьмём X'_{m-r})</tex> B . Матрица <tex>Q_1</tex> {{---}} базу это квадратная матрица порядка <tex> M_1^* m-r</tex>, включающую в себя которая является подматрицей матрицы <tex>Q</tex> и расположена внизу матрицы <tex> A Q</tex>. По '''определению 1''' Из равенства (4) следует, что ::: <tex>B (6): 0=\in alpha_1 X'_1 + \mathcal B_1 alpha_2 X'_2 + \Rightarrow ldots + \overline B \in \mathcal B alpha_{m-r} X'_{m-r}</tex>:: т. Поскольку е. система столбцов квадратной матрицы <tex> B \cap \overline B = \varnothing, A \in B Q_1</tex>линейно зависима. Тогда линейно зависима и система строк этой матрицы, то т.е. линейно зависима система из <tex> A \cap \overline B = \varnothing m - r</tex>. В таком случае по '''определению 2''' последних строк матрицы <tex> A \in I_2 Q</tex> . Что и требовалось доказать. * :<tex> A \in I_2 \Rightarrow A \in I_1 Longleftarrow</tex>*: :Теперь докажем в обратную сторону. Пусть система каких-либо <tex>m - r</tex> A \in I_2 строк матрицы <tex>Q</tex> означает линейно зависима. Для простоты обозначений будем считать, что эта система состоит из последних <tex> \exists B \in \mathcal B: \ A \cap B = \varnothing m - r </tex> строк матрицы <tex>Q</tex>. Последнее можно записать иначе: Тогда линейно зависима система (5) "урезанных" столбцов, составляющих матрицу <tex> A \subseteq \overline B Q_1</tex>. *: Кроме того Следовательно, некоторая нетривиальная линейная комбинация (6) "урезанных" столбцов равна <tex> B \in \mathcal B \Rightarrow \overline B \in \mathcal B_1 0</tex> по определению . С помощью равенства (4) определим столбец <tex> M_1^* X</tex>. Подытожив вышесказанное можем написать Поскольку система столбцов (2) линейно независима, имеем <tex> A X \subseteq \overline B \in \mathcal B_1 ne 0</tex>. Столбец Х является решением системы (1), так как он равен линейной комбинации базиса пространства решений этой системы. Тогда столбец <tex>Y</tex>, полученный из столбца <tex>x</tex> отбрасыванием последних <tex>m - r</tex>нулевых компонент, является ненулевым решением системы (3). Следовательно, откуда следует линейно зависима система из первых <tex>r</tex> столбцов матрицы <tex> A \in I_1 P_1</tex> , что и требовалось доказать.

*[[Аксиоматизация матроида базами]]* [[Аксиоматизация матроида циклами]]* [[Теорема о базах]] == Примечания ==<references /> == Источники информации ==* [[wikipedia:ru:Матроид#Дополнительные_понятия | Википедия {{---}} Двойственный матроид]]* [[wikipedia:en:Dual matroid | Wikipedia {{---}} Dual matroid]]* ''Michel X. Goemans'' {{---}} Advanced Combinatorial Optimization, lection 8: Mathroids.* ''Асанов М. О., Баранский В. А., Расин В. В.'' {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''