Изменения

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

Пересечение матроидов, определение, примеры

831 байт добавлено, 22:13, 8 июня 2015
Нет описания правки
{{Определение
|definition =
Пусть даны два матроида <tex>M_1 = \langle X, I_1\mathcal{I}_1\rangle</tex> и <tex>M_2 = \langle X, I_2 \mathcal{I}_2 \rangle</tex>. '''Пересечением матроидов''' (англ. ''matroid intersection'') <tex>M_1</tex> и <tex>M_2</tex> называется пара <tex>M_1 \cap M_2 = \langle X, \mathcal{I } \rangle</tex>, где <tex>X</tex> {{---}} носитель исходных матроидов, а <tex> \mathcal{I } = I_1 \mathcal{I}_1 \cap I_2\mathcal{I}_2</tex>.
}}
 
 
# Пересечение матроидов не всегда является матроидом.
# Пересечение трех и более матроидов {{---}} это NP-полная задача.
==Примеры==
# <tex>M_1</tex> {{---}} графовый матроид, <tex>M_2</tex> {{---}} '''разноцветный матроид''' (англ. ''multicolored matroid'') (Множество независимо, если в нём нет двух ребер одного цвета). Тогда их пересечение {{---}} это разноцветный лес (англ. ''rainbow forests'').
# Пусть <tex>G</tex> {{---}} двудольный граф и заданы два матроида <tex>M_1 = \langle X, I_1 \mathcal{I}_1 \rangle</tex>, <tex>M_2 = \langle X, I_2 \mathcal{I}_2 \rangle</tex>, где <tex>X</tex> {{---}} множество ребёр графа, <tex>I_1 \mathcal{I}_1 = \{F \subseteq X: \deg(v) \le leqslant 1 \: \forall v \in L \}</tex>, <tex>I_2 \mathcal{I}_2 = \{F \subseteq X: \deg(v) \le leqslant 1 \: \forall v \in R \}</tex>. Тогда их пересечение {{---}} это множество всевозможных паросочетаний графа. Заметим, что пересечение данных матроидов не является матроидом.# Пусть <tex>D = \langle V, A \rangle </tex> {{---}} [https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%28%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2%29|<tex>r</tex>-ориентированное дерево]. Пусть граф <tex>G</tex> {{---}} неориентированный граф, соответствующий графу <tex>D</tex>. Тогда рассмотрим два матроида <tex>M_1 = \langle A, I_1 \mathcal{I}_1 \rangle, M_2 = \langle A, I_2 \mathcal{I}_2 \rangle</tex>, где <tex>A</tex> {{---}} множество ребёр графа, <tex>M_1</tex> {{---}} графовый матроид <tex>G</tex>, <tex>I_2 \mathcal{I}_2 = \{F \subseteq X: \deg^-(v) \le leqslant 1 \: \forall v \in V \setminus \{r\} \}</tex>. Пересечения данных матроидов является ориентированным деревом. == См. также==* [[Примеры_матроидов]]* [[Алгоритм_построения_базы_в_пересечении_матроидов]]* [[Алгоритм_построения_базы_в_объединении_матроидов]]
==Источникиинформации ==
* Асанов М. О., Баранский В. А., Расин В. В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы (глава 4. Матроиды)
* [http://www-math.mit.edu/~goemans/18433S09/matroid-intersect-notes.pdf Lecture notes on matroid intersection]
170
правок

Навигация