Редактирование: Двойственный матроид

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 2: Строка 2:
 
|about=1
 
|about=1
 
|definition=
 
|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>
+
'''Двойственный матроид''' (англ. '''dual matroid''') к <tex> M = \; \langle X, B \rangle</tex> {{---}} это [[Определение_матроида | матроид]] <tex>M^* = \; \langle X, \mathcal B^* \rangle</tex>, где <tex> \mathcal B^* = \; \{ \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 | аксиомам баз]].
+
|statement= Множество <tex>\mathcal B^*</tex> удовлетворяет [[Теорема_о_базах#base_theorem | аксиомам баз]].
 
|proof=
 
|proof=
  
# Следует из <tex> | \mathcal B | = | \mathcal B^*_1 | </tex>.  
+
# Следует из <tex> | \mathcal B | = | \mathcal B^* | </tex>.  
# Предположим <tex>\overline B_1, \overline B_2 \in \mathcal B^*_1, \ \overline B_1 \ne \overline B_2, \ \overline {B_1} \subseteq \overline {B_2} </tex>. Тогда по второй аксиоме баз для <tex> B_{1,2} \ (B_1, B_2 \in \mathcal B):\ \overline {B_1} \subseteq \overline {B_2} \Rightarrow B_2 \subseteq B_1 </tex>, а [[Теорема_о_базах#definition | определение базы]] гласит, что в таком случае <tex> B_1 = B_2, </tex> пришли к противоречию.
+
# Предположим <tex>\overline B_1, \overline B_2 \in \mathcal B^*, \ \overline B_1 \ne \overline B_2, \ \overline {B_1} \subseteq \overline {B_2} </tex>. Тогда по второй аксиоме баз для <tex> B_{1,2} \ (B_1, B_2 \in \mathcal B):\ \overline {B_1} \subseteq \overline {B_2} \Rightarrow B_2 \subseteq B_1 </tex>, а [[Теорема_о_базах#definition | определение базы]] гласит, что в таком случае <tex> B_1 = B_2, </tex> пришли к противоречию.
# Пусть <tex> \overline{B_1}, \overline {B_2} \in \mathcal B^*_1</tex>  и  <tex> p\in \overline{B_1}.</tex>
+
# Пусть <tex> \overline{B_1}, \overline {B_2} \in \mathcal B^*</tex>  и  <tex> p\in \overline{B_1}.</tex>.
 
#: Покажем, что в <tex> B_1 \cup p </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> 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> \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> То есть выполняется третья аксиома баз.
 
#: Поскольку цикл <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> То есть выполняется третья аксиома баз.
 
}}
 
}}
 +
 +
{{Определение
 +
|about=2
 +
|definition=
 +
'''Двойственный матроид''' к <tex> M = \; \langle X, I \rangle</tex> {{---}} это матроид <tex>M^* = \langle X, I^* \rangle</tex>, где <tex>I^* = \{A\ |\ \exists B \in \mathcal B: \  A \cap B = \varnothing\}</tex>
 +
}}
 +
  
 
{{Теорема
 
{{Теорема
|statement=Матроиды <tex> M^*_1 </tex> и <tex> M^*_2 </tex> совпадают.
+
|statement=Определения 1 и 2 эквивалентны.
 
|proof=
 
|proof=
 +
Введём следующие обозначения:
 +
: <tex> M_1^* = \; \langle X, I_1 \rangle </tex> {{---}} двойственный к <tex> M </tex> матроид по первому определению
 +
: <tex> M_2^* = \; \langle X, I_2 \rangle </tex> {{---}} по второму.
  
Требуется доказать: <tex> I^*_1 = I^*_2. </tex>
+
Необходимо показать: <tex> I_1 = I_2 </tex>
* <tex> A \in I^*_1 \Rightarrow A \in 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> \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 \in I </tex> {{---}} множество максимального размера среди таких, что <tex> A \subseteq S </tex>, причём <tex> S </tex> {{---}} не база. Возмём также какое-нибудь  <tex> B \in \mathcal B</tex>.  
 
*:: Раз <tex> S </tex> не база, то <tex> |S| < |B| </tex>. В таком случае по [[Определение_матроида | 3-ей аксиоме матроидов]] <tex> \exists b \in B: \ S \cup b \in I </tex>. Получили противоречие, поскольку <tex> S \cup b </tex> имеет большую мощность чем <tex> S </tex>.
 
*:: Раз <tex> S </tex> не база, то <tex> |S| < |B| </tex>. В таком случае по [[Определение_матроида | 3-ей аксиоме матроидов]] <tex> \exists b \in B: \ S \cup b \in I </tex>. Получили противоречие, поскольку <tex> S \cup 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 = \varnothing, A \subseteq B </tex>, то <tex> A \cap \overline B = \varnothing </tex>. В таком случае по определению <tex> M^*_2 </tex> выполняется <tex> A \in I^*_2 </tex>.
+
*: Итак, возьмём <tex> B </tex> {{---}} базу <tex> M_1^* </tex>,  включающую в себя <tex> A </tex>. По '''определению 1''' <tex>B \in \mathcal B_1 \Rightarrow \overline B \in \mathcal B </tex>. Поскольку <tex> B \cap \overline B = \varnothing, A \subseteq B </tex>, то <tex> A \cap \overline B = \varnothing </tex>. В таком случае по '''определению 2''' <tex> A \in I_2 </tex>.
 
   
 
   
* <tex> A \in I^*_2 \Rightarrow A \in I^*_1 </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> 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>.
+
*: Кроме того <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>F</tex>, так же является матричным над телом <tex>F</tex>
 
|proof=
 
: Пусть <tex> M = \langle X, \mathcal{I} \rangle</tex> {{---}} произвольный матричный матроид над телом <tex>F</tex>, <tex> X = \{1,\ldots,m\} </tex>,  <tex>r</tex> {{---}} его [[Ранговая функция, полумодулярность|ранговая функция]]. Рассмотрим сначала крайний случай [[Примеры матроидов|тривиального]] и (двойственного к нему) [[Примеры матроидов|полного]] матроида. Они, очевидно, представимы над телом <tex>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>:
 
:::<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):
 
:::<tex>(4): X=\alpha_1 X_1 + \alpha_2 X_2 + \ldots + \alpha_{m-r} X_{m-r}</tex>
 
:: где среди коэффициентов есть хотя бы один ненулевой элемент из <tex>F</tex>. Введем в рассмотрение столбцы
 
:::<tex>(5): X'_1, X'_2, \ldots, X'_{m-r}</tex>
 
:: из пространства <tex>F^{m-r}</tex>, полученные соответственно из столбцов <tex>X_1, X_2, \ldots, X_{m-r}</tex> отбрасыванием первых <tex>r</tex> компонент. Составим из этих "урезанных" столбцов <tex> ((m - r) \times (m - r))</tex>-матрицу  <tex>Q_1 = (X'_1, X'_2, \ldots, X'_{m-r})</tex>. Матрица <tex>Q_1</tex> {{---}} это квадратная матрица порядка <tex>m-r</tex>, которая является подматрицей матрицы <tex>Q</tex> и расположена внизу матрицы <tex>Q</tex>. Из равенства (4) следует, что
 
::: <tex>(6): 0=\alpha_1 X'_1 + \alpha_2 X'_2 + \ldots + \alpha_{m-r} X'_{m-r}</tex>
 
:: т.е. система столбцов квадратной матрицы <tex>Q_1</tex> линейно зависима. Тогда линейно зависима и система строк этой матрицы, т.е. линейно зависима система из <tex>m - r</tex> последних строк матрицы <tex>Q</tex>. Что и требовалось доказать.
 
 
 
:<tex>\Longleftarrow</tex>
 
::Теперь докажем в обратную сторону. Пусть система каких-либо <tex>m - r</tex> строк матрицы <tex>Q</tex> линейно зависима. Для простоты обозначений будем считать, что эта система состоит из последних <tex> m - r </tex> строк матрицы <tex>Q</tex>. Тогда линейно зависима система (5) "урезанных" столбцов, составляющих матрицу <tex>Q_1</tex>. Следовательно, некоторая нетривиальная линейная комбинация (6) "урезанных" столбцов равна <tex>0</tex>. С помощью равенства (4) определим столбец <tex>X</tex>. Поскольку система столбцов (2) линейно независима, имеем <tex>X \ne 0</tex>. Столбец Х является решением системы (1), так как он равен линейной комбинации базиса пространства решений этой системы. Тогда столбец <tex>Y</tex>, полученный из столбца <tex>x</tex> отбрасыванием последних <tex>m - r</tex> нулевых компонент, является ненулевым решением системы (3). Следовательно, линейно зависима система из первых <tex>r</tex> столбцов матрицы <tex>P_1</tex>, что и требовалось доказать.  
 
 
}}
 
}}
  
 
== См.также ==
 
== См.также ==
 
* [[Аксиоматизация матроида базами]]
 
* [[Аксиоматизация матроида базами]]
* [[Аксиоматизация матроида циклами]]
 
* [[Теорема о базах]]
 
 
== Примечания ==
 
<references />
 
  
 
== Источники информации ==
 
== Источники информации ==
 
* [[wikipedia:ru:Матроид#Дополнительные_понятия | Википедия {{---}} Двойственный матроид]]
 
* [[wikipedia:ru:Матроид#Дополнительные_понятия | Википедия {{---}} Двойственный матроид]]
 
* [[wikipedia:en:Dual matroid | Wikipedia {{---}} Dual matroid]]
 
* [[wikipedia:en:Dual matroid | Wikipedia {{---}} Dual matroid]]
* ''Michel X. Goemans'' {{---}} Advanced Combinatorial Optimization, lection 8: Mathroids.
 
* ''Асанов М. О., Баранский В. А., Расин В. В.'' {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''
 
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Матроиды]]
 
[[Категория:Матроиды]]
[[Категория:Основные факты теории матроидов]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: