Двойственный матроид - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:15:04Z

rollbackEdits.php mass rollback

185.220.102.8 в 05:51, 1 сентября 2022

2022-09-01T05:51:59Z

188.242.29.236: /* См.также */

2018-12-11T14:45:29Z

‎См.также

188.242.29.236: /* См.также */

2018-12-11T14:44:40Z

‎См.также

Aksholokhov в 11:29, 21 мая 2015

2015-05-21T11:29:19Z

Aksholokhov в 11:27, 21 мая 2015

2015-05-21T11:27:57Z

Aksholokhov в 11:06, 21 мая 2015

2015-05-21T11:06:24Z

Aksholokhov в 10:59, 21 мая 2015

2015-05-21T10:59:53Z

Aksholokhov в 21:59, 19 мая 2015

2015-05-19T21:59:21Z

Aksholokhov в 18:25, 19 мая 2015

2015-05-19T18:25:37Z

← Предыдущая		Версия 16:15, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|about=1		\|about=1

← Предыдущая		Версия 05:51, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|about=1		\|about=1

@@ Строка 71: / Строка 71: @@
 * [[Аксиоматизация матроида базами]]
 * [[Аксиоматизация матроида циклами]]
-* [[Teopeма о базах]]
+* [[Теорема о базах]]
 == Примечания ==

@@ Строка 70: / Строка 70: @@
 == См.также ==
 * [[Аксиоматизация матроида базами]]
 == Примечания ==

@@ Строка 44: / Строка 44: @@
 |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 = \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>.

@@ Строка 68: / Строка 68: @@
 :<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>, что и требовалось доказать.
+::Теперь докажем в обратную сторону. Пусть система каких-либо <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>, что и требовалось доказать.
 }}

@@ Строка 45: / Строка 45: @@
 |proof=
 : Пусть <tex> M = \langle X, \mathcal{I} \rangle</tex> {{---}} произвольный матричный матроид над телом <tex>F</tex>, <tex> X = \{1,\ldots,m\} </tex>,  <tex>r</tex> {{---}} его [[Ранговая функция, полумодулярность|ранговая функция]]. Рассмотрим сначала крайний случай тривиального и (двойственного к нему) полного матроида.
-:* Матроид <tex> M = \langle X, \mathcal{I} \rangle</tex> является тривиальным, если <tex>\mathcal{I} = \varnothing </tex>. <tex>r(\mathcal{I}) = 0</tex>
+:* Матроид <tex> M = \langle X, \mathcal{I} \rangle</tex> является тривиальным, если <tex>\mathcal{I} = \varnothing </tex>.
-:* Матроид <tex> M = \langle X, \mathcal{I} \rangle</tex> является полным, если <tex>\mathcal{I} = 2^X</tex>. <tex>r(\mathcal{I}) = |X|</tex>
+:* Матроид <tex> M = \langle X, \mathcal{I} \rangle</tex> является полным, если <tex>\mathcal{I} = 2^X</tex>.
 :Они, очевидно, представимы над телом <tex>F</tex> нулевой и единичной матрицей соответственно.
@@ Строка 68: / Строка 68: @@
 :<tex>\Longleftarrow</tex>
-::Теперь докажем в обратную сторону. Пусть система каких-либо <tex>m - r</tex> строк матрицы <tex>Q</tex> линейно зависима. Для простоты обозначений будем считать, что эта система состоит из последних <tex> m - r </tex> строк матрицы <tex>Q</tex>. Тогда линейно зависима система (5) "урезанных" столбцов, составляющих матрицу <tex>Q_1</tex>. Следовательно, некоторая нетривиальная линейная комбинация (6) "урезанных" столбцов равна 0. С помощью равенства (4) определим столбец <tex>X</tex>. Поскольку система столбцов (2) линейно независима, имеем <tex>X \ne 0</tex>. Столбец Х является решением системы (1), так как он равен линейной комбинации базиса пространства решений этой системы. Тогда столбец <tex>Y</tex>, полученный из столбца <tex>x</tex> отбрасыванием последних m - r нулевых компонент, является ненулевым решением системы (3). Следовательно, линейно зависима система из первых <tex>r</tex> столбцов матрицы <tex>P_1</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>, что и требовалось доказать.
 }}

@@ Строка 47: / Строка 47: @@
 :* Матроид <tex> M = \langle X, \mathcal{I} \rangle</tex> является тривиальным, если <tex>\mathcal{I} = \varnothing </tex>.
 :* Матроид <tex> M = \langle X, \mathcal{I} \rangle</tex> является полным, если <tex>\mathcal{I} = 2^X</tex>.
-:Они, очевидно, представимы над телом <tex>F</tex> нулевой и единичной матрицей соответственно. <br>
+:Они, очевидно, представимы над телом <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>. <br>
+: Пусть теперь <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>: <br>
+: Рассмотрим следующую однородную систему уравнений над пространством векторов-столбцов <tex>F^m</tex>:
-:: <tex>(1): PX=0</tex>.<br>
+:: <tex>(1): PX=0</tex>.
-: Для задания базиса ФСР этой системы нам [[wikipedia:ru:Решение систем линейных алгебраических уравнений|достаточно]] <tex>m - r</tex> линейно независимых векторов. Пусть <br>
+: Для задания базиса ФСР этой системы нам [[wikipedia:ru:Решение систем линейных алгебраических уравнений|достаточно]] <tex>m - r</tex> линейно независимых векторов. Пусть
-:: <tex>(2): X_1, X_2,\ldots, X_{m-r}</tex><br>
+:: <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>. <br>
+:{{---}} базис пространства решений системы (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>.
-:Возьмем произвольную систему из r cстолбцов матрицы <tex>P</tex>. Для простоты обозначений будем считать, что взяты первые<tex>r</tex> столбцов (мы всегда можем переставить столбцы матрицы местами, не поменяв характера их линейной зависимости). Пусть <tex>P_1(t\times r)</tex> {{---}} подматрица матрицы <tex>P</tex>, составленная из взятых первых <tex>r</tex> столбцов. Рассмотрим однородную систему линейных уравнений над пространством векторов-столбцов <tex>F^r</tex>: <br>
+:Возьмем произвольную систему из r cстолбцов матрицы <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><br>
+::<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):<br>
+: Пусть столбцы матрицы <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><br>
+::<tex>(4): X=\alpha_1 X_1 + \alpha_2 X_2 + \ldots + \alpha_{m-r} X_{m-r}</tex>
-: где среди коэффициентов есть хотя бы один ненулевой элемент из <tex>F</tex>. Введем в рассмотрение столбцы <br>
+: где среди коэффициентов есть хотя бы один ненулевой элемент из <tex>F</tex>. Введем в рассмотрение столбцы
-::<tex>(5): X'_1, X'_2, \ldots, X'_{m-r}</tex><br>
+::<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) следует, что <br>
+: из пространства <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><br>
+:: <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>. Что и требовалось доказать. <br>
+: т.е. система столбцов квадратной матрицы <tex>Q_1</tex> линейно зависима. Тогда линейно зависима и система строк этой матрицы, т.е. линейно зависима система из <tex>m - r</tex> последних строк матрицы <tex>Q</tex>. Что и требовалось доказать.
 :Теперь докажем в обратную сторону. Пусть система каких-либо <tex>m - r</tex> строк матрицы <tex>Q</tex> линейно зависима. Для простоты обозначений будем считать, что эта система состоит из последних <tex> m - r </tex> строк матрицы <tex>Q</tex>. Тогда линейно зависима система (5) "урезанных" столбцов, составляющих матрицу <tex>Q_1</tex>. Следовательно, некоторая нетривиальная линейная комбинация (6) "урезанных" столбцов равна 0. С помощью равенства (4) определим столбец <tex>X</tex>. Поскольку система столбцов (2) линейно независима, имеем <tex>X \ne 0</tex>. Столбец Х является решением системы (1), так как он равен линейной комбинации базиса пространства решений этой системы. Тогда столбец <tex>Y</tex>, полученный из столбца <tex>x</tex> отбрасыванием последних m - r нулевых компонент, является ненулевым решением системы (3). Следовательно, линейно зависима система из первых <tex>r</tex> столбцов матрицы <tex>P_1</tex>, что и требовалось доказать.
@@ Строка 75: / Строка 75: @@
 * [[wikipedia:en:Dual matroid | Wikipedia {{---}} Dual matroid]]
 * ''Michel X. Goemans'' {{---}} Advanced Combinatorial Optimization, lection 8: Mathroids.
-* ''Асанов М. О., Баранский В. А., Расин В. В.'' {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2''' <br>
+* ''Асанов М. О., Баранский В. А., Расин В. В.'' {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''
 [[Категория:Алгоритмы и структуры данных]]
 [[Категория:Матроиды]]
 [[Категория:Основные факты теории матроидов]]