137
правок
Изменения
Нет описания правки
}}
==Разделенный матроид==
}}
==Matching Matroid==
* <tex>\exists xy: y \in B \setminus A \Rightarrow xy \notin P_A</tex>. Мы можем добавить в <tex>A</tex> вершину <tex>x</tex> (или <tex>y</tex>), а в <tex>P_A</tex> ребро <tex>xy</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>\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>
}}
==Бинарный матроид==
{{Определение
|definition=
Матроид <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>.
}}
{{Определение
|definition=
'''Регулярный матроид(regular matroid)''' - матроид, представимый над любым полем.
}}
{{Определение
|definition=
'''Бинарный матроид(binary matroid)''' - матроид, представимый над полем целых чисел по модулю 2.
}}
==Матроид с выкинутым элементом==
{{Определение
|definition=
Пусть <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> является матроидом.
}}
==Матроид, стянутый по элементу==
{{Определение
|definition=
Пусть <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> является матроидом.
}}
==Урезанный матроид==
{{Определение
|definition=
Пусть <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. Теория матроидов)
* [http://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture14.pdf Примеры матроидов]
*[[wikipedia:Matroid | Wikipedia {{---}} Matroid]]
