Пересечение матроидов, определение, примеры — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition = Пусть даны два матроида <tex>M_1 = (X, I_1)</tex> и <tex>M_2 = (X, I_2)</tex>. '''Пересечение…»)
(нет различий)

Версия 06:42, 7 июня 2011

Определение:
Пусть даны два матроида [math]M_1 = (X, I_1)[/math] и [math]M_2 = (X, I_2)[/math]. Пересечением матроидов [math]M_1[/math] и [math]M_2[/math] называется пара [math]M_1 \cap M_2 = (X, I)[/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 = (X, I_1)[/math], [math]M_2 = (X, I_2)[/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]. Тогда их пересечение - это множество паросочетаний графа.