Изменения
Новая страница: «{{Определение |definition = Пусть даны два матроида <tex>M_1 = (X, I_1)</tex> и <tex>M_2 = (X, I_2)</tex>. '''Пересечение…»
{{Определение
|definition =
Пусть даны два матроида <tex>M_1 = (X, I_1)</tex> и <tex>M_2 = (X, I_2)</tex>. '''Пересечением матроидов''' <tex>M_1</tex> и <tex>M_2</tex> называется пара <tex>M_1 \cap M_2 = (X, I)</tex>, где <tex>X</tex> - носитель исходных матроидов, а <tex> I = I_1 \cap I_2</tex>.
}}
'''Примеры'''
1) <tex>M_1</tex> - графовый матроид, <tex>M_2</tex> - "разноцветный" матроид (Множество независимо, если в нём нет двух ребер одного цвета). Тогда их пересечение - это разноцветный лес (англ. Rainbow forests)
2) Пусть <tex>G</tex> - двудольный граф и заданы два матроида <tex>M_1 = (X, I_1)</tex>, <tex>M_2 = (X, I_2)</tex>, где <tex>X</tex> - множество ребёр графа, <tex>I_1 = \{F \subseteq X: deg(v) \le 1 \: \forall v \in L \}</tex>, <tex>I_2 = \{F \subseteq X: deg(v) \le 1 \: \forall v \in R \}</tex>. Тогда их пересечение - это множество паросочетаний графа.
|definition =
Пусть даны два матроида <tex>M_1 = (X, I_1)</tex> и <tex>M_2 = (X, I_2)</tex>. '''Пересечением матроидов''' <tex>M_1</tex> и <tex>M_2</tex> называется пара <tex>M_1 \cap M_2 = (X, I)</tex>, где <tex>X</tex> - носитель исходных матроидов, а <tex> I = I_1 \cap I_2</tex>.
}}
'''Примеры'''
1) <tex>M_1</tex> - графовый матроид, <tex>M_2</tex> - "разноцветный" матроид (Множество независимо, если в нём нет двух ребер одного цвета). Тогда их пересечение - это разноцветный лес (англ. Rainbow forests)
2) Пусть <tex>G</tex> - двудольный граф и заданы два матроида <tex>M_1 = (X, I_1)</tex>, <tex>M_2 = (X, I_2)</tex>, где <tex>X</tex> - множество ребёр графа, <tex>I_1 = \{F \subseteq X: deg(v) \le 1 \: \forall v \in L \}</tex>, <tex>I_2 = \{F \subseteq X: deg(v) \le 1 \: \forall v \in R \}</tex>. Тогда их пересечение - это множество паросочетаний графа.
