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

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

Пусть даны два матроида [math]M_1 = \langle X, I_1\rangle[/math] и [math]M_2 = \langle X, I_2 \rangle[/math]. Пересечением матроидов [math]M_1[/math] и [math]M_2[/math] называется пара [math]M_1 \cap M_2 = \langle X, I \rangle[/math], где [math]X[/math] — носитель исходных матроидов, а [math] I = I_1 \cap I_2[/math].

Примеры

1. [math]M_1[/math] — графовый матроид, [math]M_2[/math] — «разноцветный» матроид (Множество независимо, если в нём нет двух ребер одного цвета). Тогда их пересечение — это разноцветный лес (англ. rainbow forests).
2. Пусть [math]G[/math] — двудольный граф и заданы два матроида [math]M_1 = \langle X, I_1 \rangle[/math], [math]M_2 = \langle X, I_2 \rangle[/math], где [math]X[/math] — множество ребёр графа, [math]I_1 = \{F \subseteq X: deg(v) \le 1 \: \forall v \in L \}[/math], [math]I_2 = \{F \subseteq X: deg(v) \le 1 \: \forall v \in R \}[/math]. Тогда их пересечение — это множество всевозможных паросочетаний графа.