Изменения
Нет описания правки
{{Определение
|definition =
Пусть даны два матроида <tex>M_1 = \langle X, \mathcal{I}_1\rangle</tex> и <tex>M_2 = \langle X, \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} = \mathcal{I}_1 \cap \mathcal{I}_2</tex>. }}* Пересечение матроидов не всегда является матроидом.* Пересечение трех и более матроидов является [[Примеры NP-полных языков| NP-полной задачей]]. == Разноцветный лес == <tex>M_1</tex> {{---}} [[Примеры_матроидов|графовый матроид]], <tex>M_2</tex> {{---}} '''разноцветный матроид''' (англ. ''multicolored matroid'') (Множество независимо, если в нём нет двух ребер одного цвета). Тогда их пересечение {{---}} это '''разноцветный лес''' (англ. ''rainbow forests'').[[Файл:Rainbow_forest_DY.png|500px|thumb|center|Пересечение матроидов, [[Алгоритм_построения_базы_в_пересечении_матроидов|база]] матроида]] {{Утверждение|statement =Пересечение данных матроидов не является матроидом.|proof =Рассмотрим пару <tex>\langle X, \mathcal{I}\rangle</tex>, <tex>X</tex> {{---}} ребра разноцветного леса, <tex> \mathcal{I} = \mathcal{I}_1 \cap \mathcal{I}_2</tex>.Данная пара не является матроидом, так как не выполняется третье свойство матроида, то есть <tex>\exists A, B \in \mathcal{I}, |A| > |B| </tex> и <tex>\nexists \, x \in A \setminus B : B \cup \{x\} \in \mathcal{I}</tex> (См. пример <tex>1</tex>)[[Файл:Example2_DY.png|300px|thumb|left|Пример 1]] }} == Двудольный граф ==Пусть <tex>G</tex> {{---}} [[Двудольные_графы_и_раскраска_в_2_цвета|двудольный граф]] и заданы два матроида <tex>M_1 = \langle X, \mathcal{I}_1 \rangle</tex>, <tex>M_2 = \langle X, \mathcal{I}_2 \rangle</tex>, где <tex>X</tex> {{---}} множество ребёр графа, <tex>\mathcal{I}_1 = \{F \subseteq X: \deg(v) \leqslant 1 \: \forall v \in L \}</tex>, <tex>\mathcal{I}_2 = \{F \subseteq X: \deg(v) \leqslant 1 \: \forall v \in R \}</tex>. Тогда их пересечение {{---}} это множество всевозможных паросочетаний графа. {{Утверждение|statement =Пересечение данных матроидов не является матроидом.|proof =Рассмотрим пару <tex>\langle X, \mathcal{I}\rangle</tex>, <tex>X</tex> {{---}} носитель, <tex> \mathcal{I} = \mathcal{I}_1 \cap \mathcal{I}_2</tex>.Данная пара не является матроидом, так как не выполняется третье свойство матроида, то есть <tex>\exists A, B \in \mathcal{I}, |A| > |B| </tex> и <tex>\nexists \, x \in A \setminus B : B \cup \{x\} \in \mathcal{I}</tex> (См. пример 2)[[Файл:Example_DY.png|300px|thumb|left|Пример 2]]
}}
== Ориентированный лес ==
{{Определение
|definition=
'''Ориентированное дерево''' (англ. ''arborescence'') {{---}} ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода <tex>1</tex> (в них ведёт ровно по одной дуге).
}}
Пусть <tex>D = \langle V, X \rangle </tex> {{---}} ориентированнный граф.
Граф <tex>G</tex> {{---}} неориентированный граф, соответствующий графу <tex>D</tex>.
Тогда рассмотрим два матроида <tex>M_1 = \langle X, \mathcal{I}_1 \rangle, M_2 = \langle X, \mathcal{I}_2 \rangle</tex>, где <tex>X</tex> {{---}} множество ребёр графа.
<tex>M_1</tex> {{---}} [[Примеры_матроидов|графовый матроид]] <tex>G</tex>,
<tex>\mathcal{I}_1 = \{X' \subseteq X: X'</tex> {{---}} лес в <tex>G \}</tex>.
<tex>M_2</tex> {{---}} [[Примеры_матроидов|матроид разбиений]] графа <tex>D</tex>,
<tex>\mathcal{I}_2 = \{X' \subseteq X: |\deg^-(v) \cap X'| \leqslant 1, \forall v \in V \}</tex>.
Пересечение данных матроидов являются множества ориентированных лесов.
== См. также==
* [[Примеры_матроидовПримеры матроидов]]* [[Алгоритм_построения_базы_в_пересечении_матроидовАлгоритм построения базы в пересечении матроидов]]* [[Алгоритм_построения_базы_в_объединении_матроидовАлгоритм построения базы в объединении матроидов]]
==Источники информации ==