Изменения
→См.также
|about=1
|definition=
'''Двойственный матроид''' (англ. ''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>
}}
{{Определение
|about=2
|definition=
'''Двойственный матроид''' к <tex> M = \; \langle X, I \rangle</tex> {{---}} это матроид <tex>M^*_2 = \langle X, I^*_2 \rangle</tex>, где <tex>I^*_2 = \{A\ |\ \exists B \in \mathcal B: \ A \cap B = \varnothing\}</tex>
}}
{{Теорема
|statement= Множество <tex>\mathcal B^*_1</tex> удовлетворяет [[Аксиоматизация_матроида_базами Теорема_о_базах#base_theorem | аксиомам баз]].
|proof=
}}
{{В разработке}}Теорема|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= Пусть [[Определение матроида|Матроид]], двойственный к [[Примеры матроидов|матричному]] над телом <tex> A \in I F</tex>. Тогда , так же является матричным над телом <tex> \exists B \in \mathcal B: A \in B F</tex> |proof= Докажем от противного.Пускай : Пусть <tex> C M = \in langle X, \mathcal{I } \rangle</tex> {{--- множество максимального размера среди таких, что }} произвольный матричный матроид над телом <tex> A \in C F</tex>, причём <tex> C </tex> не база. Возмём также какое-нибудь <tex> B X = \{1,\in ldots,m\mathcal B} </tex>. Раз , <tex> C r</tex> не база{{---}} его [[Ранговая функция, то <tex> полумодулярность|Cранговая функция]]. Рассмотрим сначала крайний случай [[Примеры матроидов| < тривиального]] и (двойственного к нему) [[Примеры матроидов|B| </tex>. В таком случае по 3-ему свойству полного]] матроида <tex> \exists b \in B: C \cap b \in I </tex>. Получили противоречиеОни, очевидно, поскольку представимы над телом <tex> C \cap b </tex> имеет большую мощность чем <tex> C F</tex>нулевой и единичной матрицей соответственно.}}
: Пусть теперь <tex>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=0</tex>.
: Для задания базиса ФСР этой системы нам достаточно<ref>[https://ru.wikipedia.org/wiki/Решение_систем_линейных_алгебраических_уравнений Википедия {{---}} Решение систем линейных алгебраических уравнений]</ref> <tex>m - r</tex> линейно независимых векторов. Пусть
:: <tex>(2): X_1, X_2,\ldots, X_{m-r}</tex>
:{{---}} базис пространства решений системы (1). Составим из этих столбцов <tex>(m \times (m - r))</tex>-матрицу <tex>Q=(X_1, X_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>\{1,\ldots, m\}</tex>.
:<tex>\Longrightarrow</tex>::Возьмем произвольную систему из r столбцов матрицы <tex>P</tex>. Для простоты обозначений будем считать, что взяты первые<tex>r</tex> столбцов (мы всегда можем переставить столбцы матрицы местами, не поменяв характера их линейной зависимости). Пусть <tex>P_1(t\times r)</tex> {{Теорема---}} подматрица матрицы <tex>P</tex>, составленная из взятых первых <tex>r</tex> столбцов. Рассмотрим однородную систему линейных уравнений над пространством векторов-столбцов <tex>F^r</tex>: |statement:::<tex>(3): P_1Y=Определения 0</tex>:: Пусть столбцы матрицы <tex>P_1</tex> линейно зависимы. Тогда система (3) имеет ненулевое решение <tex>Y</tex>. Добавим к нему снизу <tex>m - r</tex> нулей, получим ненулевое решение <tex>X</tex> системы (1 и ). Выразим <tex>X</tex> через базис (2 эквивалентны.) пространства решений системы (1):|proof=Положим :::<tex> M^* (4): X= \; alpha_1 X_1 + \langle alpha_2 X_2 + \ldots + \alpha_{m-r} X_{m-r}</tex>:: где среди коэффициентов есть хотя бы один ненулевой элемент из <tex>F</tex>. Введем в рассмотрение столбцы :::<tex>(5): X'_1, X'_2, I \rangle ldots, X'_{m-r}</tex>; :: из пространства <tex> M_1F^* = {m-r}</tex>, полученные соответственно из столбцов <tex>X_1, X_2, \; ldots, X_{m-r}</tex> отбрасыванием первых <tex>r</tex> компонент. Составим из этих "урезанных" столбцов <tex> ((m - r) \langle times (m - r))</tex>-матрицу <tex>Q_1 = (X'_1, X'_2, I_1 \rangle ldots, X'_{m-r})</tex> . Матрица <tex>Q_1</tex> {{---}} это квадратная матрица порядка <tex>m- двойственный к нему матроид по первому определениюr</tex>, которая является подматрицей матрицы <tex>Q</tex> и расположена внизу матрицы <tex>Q</tex>. Из равенства (4) следует, что ::: <tex> M_2^* (6): 0= \; alpha_1 X'_1 + \langle alpha_2 X, I_2 '_2 + \ldots + \rangle alpha_{m-r} X'_{m-r}</tex>:: т.е. система столбцов квадратной матрицы <tex>Q_1</tex> линейно зависима. Тогда линейно зависима и система строк этой матрицы, т.е. линейно зависима система из <tex>m - по второмуr</tex> последних строк матрицы <tex>Q</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'''
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
[[Категория:Основные факты теории матроидов]]