Двойственный матроид — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(См.также)
(не показано 12 промежуточных версий 4 участников)
Строка 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, \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>
 
}}
 
}}
  
Строка 37: Строка 37:
 
   
 
   
 
* <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'''
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Матроиды]]
 
[[Категория:Матроиды]]
 +
[[Категория:Основные факты теории матроидов]]

Версия 17:45, 11 декабря 2018

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


Определение:
Двойственный матроид к [math] M = \; \langle X, I \rangle[/math] — это матроид [math]M^*_2 = \langle X, I^*_2 \rangle[/math], где [math]I^*_2 = \{A\ |\ \exists B \in \mathcal B: \ A \cap B = \varnothing\}[/math]


Теорема:
Множество [math]\mathcal B^*_1[/math] удовлетворяет аксиомам баз.
Доказательство:
[math]\triangleright[/math]
  1. Следует из [math] | \mathcal B | = | \mathcal B^*_1 | [/math].
  2. Предположим [math]\overline B_1, \overline B_2 \in \mathcal B^*_1, \ \overline B_1 \ne \overline B_2, \ \overline {B_1} \subseteq \overline {B_2} [/math]. Тогда по второй аксиоме баз для [math] B_{1,2} \ (B_1, B_2 \in \mathcal B):\ \overline {B_1} \subseteq \overline {B_2} \Rightarrow B_2 \subseteq B_1 [/math], а определение базы гласит, что в таком случае [math] B_1 = B_2, [/math] пришли к противоречию.
  3. Пусть [math] \overline{B_1}, \overline {B_2} \in \mathcal B^*_1[/math] и [math] p\in \overline{B_1}.[/math]
    Покажем, что в [math] B_1 \cup p [/math] содержится ровно один цикл.
    Так как [math] p\notin {B_1}, [/math] то по определению базы [math] B_1 \cup p \notin I [/math], а значит существует цикл [math]C \subseteq B_1 \cup p [/math].
    Убедимся также, что он единственный. Положим [math] \exists C_1, C_2 \in \mathfrak{C}: \ C_1, C_2 \subseteq B_1 \cup p,\ C_1 \ne C_2 [/math]. Заметим, что [math] p \in C_1, C_2 [/math], в противном случае цикл не содержащий [math] p [/math] был бы подмножеством [math] B_1 [/math], что невозможно. Следовательно по 3-му свойству циклов [math] \exists C_3 \in \mathfrak{C}: \ C_3 \subseteq (C_1 \cup C_2) \setminus p [/math]. Но помимо этого выполнено [math] (C_1 \cup C_2) \setminus p \subseteq B_1 [/math] — противоречие.
    Поскольку цикл [math]C[/math] не лежит в [math]B_2[/math], существует [math]q \in C \cap \overline {B_2}.[/math] Множество [math](B_1 \cup p) \setminus q[/math] не содержит циклов, так как разрушен единственный цикл. Поэтому оно независимо и [math]|(B_1 \cup p) \setminus q| = |B_1|.[/math] Следовательно, [math] (B_1 \cup p) \setminus q[/math] — база. Тогда [math]\overline {(B_1 \cup p \setminus q)} = \overline {(B_1 \cup p)} \cup q = (\overline {B_1} \setminus p) \cup q,[/math] где [math]q \in \overline {B_2}.[/math] То есть выполняется третья аксиома баз.
[math]\triangleleft[/math]
Теорема:
Матроиды [math] M^*_1 [/math] и [math] M^*_2 [/math] совпадают.
Доказательство:
[math]\triangleright[/math]

Требуется доказать: [math] I^*_1 = I^*_2. [/math]

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

См.также

Примечания

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