Изменения

Пусть <tex>V</tex> {{---}} векторное пространство над телом <tex>F</tex>, пусть набор векторов <tex>V_i = \mathcal{f} v_1,\ \dots,\ v_n\mathcal {g}</tex> из пространства <tex>V</tex> является носителем <tex>X</tex>. Элементами независимого множества <tex>I</tex> данного матроида являются множества линейно-независимых векторов из набора <tex>v_ 1,\ \dots,\ v_n</tex>.Тогда <tex>M = \langle V_i, I \rangle </tex>, называется '''матричным матроидом ''' (англ. ''vector matroid)''')

{{ЛеммаУтверждение

2) <tex>A \subset B, \ B \in I \Rightarrow A \in I</tex>

3) <tex>A \in I, \ B \in I, \ \left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \mathcal {9} x \in B \setminus A, \ A \cup \mathcal{f} x \mathcal {g} \in I</tex>

Так как <tex>A \in I,</tex> , то <tex>\dim \mathcal{L}(A) = \left\vert A \right\vert</tex>. По условию <tex>\left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \exists x \in B: x \notin \mathcal{L}(A)</tex>, то есть <tex>x \notin A</tex>. Тогда множество <tex> A \cup \mathcal{f} x \mathcal {g}</tex> линейно-независимо по определению линейной оболочки.

Пусть <tex>G = \langle V, E \rangle</tex> — {{---}} неориентированный граф. Тогда <tex>M = \langle E, I \rangle </tex>, где <tex>I</tex> состоит из всех ацикличных множеств ребер (то есть являющихся лесами), называют '''графовым (графическим) матроидом ''' (англ. ''graphic matroid)''').

{{ЛеммаУтверждение

2) <tex>A \subset B, \ B \in I \Rightarrow A \in I</tex>

3) <tex>A \in I, \ B \in I, \ \left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \mathcal {9} x \in B \setminus A, \ A \cup \mathcal{f} x \mathcal {g} \in I</tex>

Пусть <tex>G = \langle X, Y, E \rangle</tex> — {{---}} двудольный граф. <tex>I = \mathcal{f} A \subset X \mid \exists </tex> паросочетание <tex> P</tex>, покрывающее <tex>A \mathcal {g} </tex>. Тогда <tex>M = \langle X, I \rangle </tex> называют '''трансверсальным матроидом ''' (англ. ''transversal matroid'').'''

{{ЛеммаУтверждение

2) <tex>A \subset B, \ B \in I \Rightarrow A \in I</tex>

3) <tex>A \in I, \ B \in I, \ \left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \mathcal {9} x \in B \setminus A, \ A \cup \mathcal{f} x \mathcal {g} \in I</tex>

Раскрасим ребра из паросочетания, соответствующего <tex> B </tex> в синий цвет, а соответствующего <tex> A </tex> — {{---}} в красный. Причем ребра, соответствующие двум паросочетаниям, будут окрашены в пурпурный цвет. Таким образом, получится <tex> \left\vert B \setminus A \right\vert </tex> ребер синего цвета, <tex> \left\vert A \setminus B \right\vert </tex> ребер красного цвета, и будет выполняться соотношение <tex> \left\vert B \setminus A \right\vert > \left\vert A \setminus B \right\vert</tex>. Рассмотрим подграф <tex> H </tex>, индуцированный красными и синими ребрами из исходного графа. Каждая вершина соответствует либо двум ребрам — {{---}} синему и красному, либо одному — {{---}} синему или красному. Любая компонента связности представляет собой либо путь, либо цикл, состоящий из чередующихся красных и синих ребер. Так как граф двудольный, любой цикл состоит из четного числа ребер. Так как синих ребер больше, чем красных, то должен существовать путь, начинающийся и оканчивающийся синим ребром. Обозначим этот путь <tex> H' </tex>. Поменяем в <tex> H' </tex> синий и красный цвета. Получаем, что ребра, окрашенные в красный и пурпурный цвета образуют паросочетание в графе. Очевидно, что подмножество соответствующее этому новому паросочетанию имеет вид <tex>A \cup \mathcal{f} x \mathcal {g} </tex>, где <tex> x \in B \setminus A </tex>. Что значит, что <tex> A \cup \mathcal{f} x \mathcal {g} \in I</tex>.

'''Универсальным матроидом ''' (англ. ''uniform matroid)''' ) называют объект <tex>U_n,_k U_{nk} = \langle X, I \rangle </tex>, где <tex>X = \{1, 2, 3, \dots, n\}, I = \mathcal{f} A \subset X \mid \left\vert A \right\vert \leqslant k\}</tex>

{{ЛеммаУтверждение

2) <tex>A \subset B, \ B \in I \Rightarrow A \in I</tex>

3) <tex>A \in I, \ B \in I, \ \left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \mathcal {9} x \in B \setminus A, \ A \cup \mathcal{f} x \mathcal {g} \in I</tex>

Пусть <tex>X = \bigcup\limits_{i=_1}^n X_i</tex>, при этом <tex> X_i \cap X_j = 0</tex>, <tex>\forall i \neq j,</tex> , и <tex>k_1 \dots k_n</tex> — {{---}} положительные целые числа. <tex>I = \mathcal{f} A \subset X \mid \left\vert A \cap X_i \right\vert \leqslant k_i, \ \forall i: 1 \leqslant i \leqslant n \mathcal {g}</tex>. Тогда <tex>M = \langle X, I \rangle </tex> называют '''матроидом разбиений ''' (англ. ''partition matroid)''')

{{ЛеммаУтверждение

2) <tex>A \subset B, \ B \in I \Rightarrow A \in I</tex>

<tex>A \subset B, \ \left\vert A \right\vert \leqslant \left\vert B \right\vert \Rightarrow \left\vert A \cap X_i \right\vert \leqslant \left\vert B \cap X_i \right\vert \leqslant k_i \Rightarrow A \in I</tex>

3) <tex>A \in I, \ B \in I, \ \left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \mathcal {9} x \in B \setminus A, \ A \cup \mathcal{f} x \mathcal {g} \in I</tex>

Пусть <tex>\forall x \in B \setminus A, \ A \cup \mathcal{f} x \mathcal {g} \notin I \Rightarrow \exists X_j, \ k_j: \left\vert A \cup \mathcal{f} x \mathcal {g} \cap X_j \right\vert > k_j</tex>, но так как <tex>A \in I</tex>, то есть <tex> \left\vert A \cap X_j \right\vert \leqslant k_j \Rightarrow \left\vert A \cap X_j \right\vert = k_j</tex> и <tex>x \in X_j</tex>. Из последнего следует, что <tex>\left\vert B \setminus A \right\vert \subset X_j</tex>.

Пусть <tex>G = \langle V, E \rangle</tex> — {{---}} неориентированный граф. <tex>I = \mathcal{f} A \subset V \mid \exists</tex> паросочетание <tex>P</tex>, покрывающее <tex>A \mathcal {g}</tex>. Тогда <tex>M = \langle V, I \rangle </tex> называют '''матроидом паросочетаний ''' (англ. ''matching matroid)''').

{{ЛеммаУтверждение

2) <tex>A \subset B, \ B \in I \Rightarrow A \in I</tex>

3) <tex>A \in I, \ B \in I, \ \left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \mathcal {9} x \in B \setminus A, \ A \cup \mathcal{f} x \mathcal {g} \in I</tex>

Пусть паросочетание <tex>P_A</tex> покрывает множество <tex>A</tex>, <tex>P_B</tex> — {{---}} множество <tex>B</tex>.

* <tex>\exists xy \in P_A, \ y \in A \Rightarrow P_A</tex> покрывает <tex>A \cup \mathcal{f} x \mathcal {g} \Rightarrow A \cup \mathcal{f} x \mathcal {g} \in I</tex>

*Если первые два случая не выполнились, значит <tex>\forall x \in B \setminus A</tex> <tex>\exists y \notin A, \ \notin B: \exists xy \in P_B</tex>. Обозначим множество таких <tex>y</tex> за <tex>C, \ \left\vert C \right\vert = \left\vert B \setminus A \right\vert > \left\vert A \setminus B \right\vert</tex>. Таким образом в <tex>C</tex> найдется хотя бы одна вершина <tex>y</tex>, не покрытая паросочетанием <tex>P_A</tex>. Тогда паросочетание <tex>P_A \cup xy</tex> покрывает <tex>A \cup \mathcal{f} x \mathcal {g} \Rightarrow A \cup \mathcal{f} x \mathcal{g} \in I</tex>

Матроид <tex>M</tex> на множестве <tex>X</tex> будем называть '''представимым представим над полем <tex>F</tex>''', если существуют векторное пространство <tex>V</tex> он [[Определение матроида| изоморфен]] некоторому векторному матроиду над <tex>F</tex> и отображение <tex>\phi:X \rightarrow V</tex>, обладающее тем свойством, что подмножество <tex>A</tex> независимо тогда и только тогда, когда <tex>\phi</tex> взаимнооднозначно на <tex>A</tex> и <tex>\phi(A)</tex> линейно-независимо в <tex>V</tex>этим полем.

'''Бинарный матроид ''' (англ. ''binary matroid)''' — ) {{---}} матроид, представимый над полем целых чисел по модулю <tex>2</tex>.

Составим матрицу инцидентности <tex>A = (a_{ij})</tex> для графа <tex>G = \langle V, E \rangle</tex>. Строки этой матрицы соответствуют вершинам графа, а столбцы — {{---}} ребрам.

Если петли нет, то рассмотрим столбцы, отвечающие ребрам простого цикла. Любая строка матрицы <tex>A</tex> содержит в этих столбцах ровно 2 единицы. Поэтому сумма по модулю <tex>2 </tex> указанных столбцов равна нулевому столбцу, что означает линейную зависимость исходного множества столбцов.

==Матроид с выкинутым элементомДругие матроиды==Несложно доказать, что следующие конструкции тоже являются матроидами.

'''Матроид с выкинутым элементом'''. Пусть <tex>M = \langle X, I\rangle</tex> — {{---}} матроид. Определим <tex>M\setminus x = \langle X \setminus x, \ \{A | A \in I, \ x \not\in A\}\rangle</tex>. Для любых <tex>M</tex> и <tex>x</tex> получившаяся конструкция <tex>M\setminus x</tex> является матроидом.

'''Матроид, стянутый по элементу'''. Пусть <tex>M = \langle X, I\rangle</tex> — {{---}} матроид. Определим <tex>M/x = \langle X \setminus x, \ \{A \setminus x | A \in I, \ x \in A\}\rangle</tex>. Для любых <tex>M</tex> и <tex>x</tex>, таких что <tex>\{x\}\in I,</tex> получившаяся конструкция <tex>M/x</tex> является матроидом.

Пусть <tex>M = \langle X, I \rangle</tex> — {{---}} матроид. Обозначим как <tex>M|_k</tex> следующую констркуцию: <tex>M|_k = \langle X, \ \{A | A \in I, \ |A| \le k \}\rangle</tex>, тогда <tex>M|_k</tex> является называют '''урезанным матроидом'''.

* Асанов М. О., Баранский В. А., Расин В. В. — {{---}} Дискретная математика: Графы, матроиды, алгоритмы (глава 4. Матроиды)* Уилсон Р. — {{---}} Введение в теорию графов (глава 9. Теория матроидов)