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

Определение:

Пусть даны два матроида [math]M_1 = \langle X, \mathcal{I}_1\rangle[/math] и [math]M_2 = \langle X, \mathcal{I}_2 \rangle[/math]. Пересечением матроидов (англ. matroid intersection) [math]M_1[/math] и [math]M_2[/math] называется пара [math]M_1 \cap M_2 = \langle X, \mathcal{I} \rangle[/math], где [math]X[/math] — носитель исходных матроидов, а [math] \mathcal{I} = \mathcal{I}_1 \cap \mathcal{I}_2[/math].

1. Пересечение матроидов не всегда является матроидом.
2. Пересечение трех и более матроидов — это NP-полная задача.

Примеры

1. [math]M_1[/math] — графовый матроид, [math]M_2[/math] — разноцветный матроид (англ. multicolored matroid) (Множество независимо, если в нём нет двух ребер одного цвета). Тогда их пересечение — это разноцветный лес (англ. rainbow forests).
2. Пусть [math]G[/math] — двудольный граф и заданы два матроида [math]M_1 = \langle X, \mathcal{I}_1 \rangle[/math], [math]M_2 = \langle X, \mathcal{I}_2 \rangle[/math], где [math]X[/math] — множество ребёр графа, [math]\mathcal{I}_1 = \{F \subseteq X: \deg(v) \leqslant 1 \: \forall v \in L \}[/math], [math]\mathcal{I}_2 = \{F \subseteq X: \deg(v) \leqslant 1 \: \forall v \in R \}[/math]. Тогда их пересечение — это множество всевозможных паросочетаний графа. Заметим, что пересечение данных матроидов не является матроидом.
3. Пусть [math]D = \langle V, A \rangle [/math] — [math]r[/math]-ориентированное дерево. Пусть граф [math]G[/math] — неориентированный граф, соответствующий графу [math]D[/math]. Тогда рассмотрим два матроида [math]M_1 = \langle A, \mathcal{I}_1 \rangle, M_2 = \langle A, \mathcal{I}_2 \rangle[/math], где [math]A[/math] — множество ребёр графа, [math]M_1[/math] — графовый матроид [math]G[/math], [math]\mathcal{I}_2 = \{F \subseteq X: \deg^-(v) \leqslant 1 \: \forall v \in V \setminus \{r\} \}[/math]. Пересечения данных матроидов является ориентированным деревом.

См. также

• Примеры_матроидов
• Алгоритм_построения_базы_в_пересечении_матроидов
• Алгоритм_построения_базы_в_объединении_матроидов

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

• Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы (глава 4. Матроиды)
• Lecture notes on matroid intersection