Изменения

Пусть даны два матроида <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]]

# {{Утверждение|statement = Пересечение данных матроидов не всегда является матроидом.# Пересечение трех и более матроидов |proof =Рассмотрим матроид пересечения <tex>M = \langle X, \mathcal{I} \rangle</tex>, <tex>A</tex> {{---}} это NP-полная задача.множество ребер, <tex>\mathcal{I} = \mathcal{I}_1 \cap \mathcal{I}_2</tex>

# 1) <tex>M_1</tex> \varnothing \in \mathcal{{---I}} графовый матроид, <tex>M_2</tex> {{---}} '''разноцветный матроид''' (англ. ''multicolored matroid'') (Множество независимо Пустое множество является ориентированным деревом, если а значит входит в нём нет двух ребер одного цвета). Тогда их пересечение {{---}} это разноцветный лес (англ. ''rainbow forests'').# Пусть <tex>G\mathcal{I}</tex> {{---}} двудольный граф и заданы два матроида . 2) <tex>M_1 = A \langle Xsubset B, \ B \in \mathcal{I}_1 \rangle</tex>, <tex>M_2 = Rightarrow A \langle X, in \mathcal{I}_2 \rangle</tex>Любой подграф ориентированного леса также является ориентированным лесом, так как во-первых, степень захода каждой вершины в подграфе могла только уменьшится, во-вторых, где <tex>X</tex> подграф ацикличного графа {{---}} множество ребёр графа, ацикличен. 3) <tex>A \in \mathcal{I}_1 = , \ B \in I, \ \left\vert A \right\{F vert < \subseteq X: left\deg(v) vert B \leqslant 1 right\: vert \forall v Rightarrow \in L exists \}</tex>, <tex>x \mathcal{I}_2 = in B \{F setminus A, \subseteq X: \deg(v) A \leqslant 1 cup \: { x \forall v } \in R \mathcal{I}</tex> Пусть количество вершин в множестве <tex>A</tex> равно <tex>k</tex>. Тогда их пересечение {{---}} это множество всевозможных паросочетаний графа. Заметим, что пересечение данных матроидов не является матроидом.# Пусть количество ребер в <tex>D = \langle V, A \rangle </tex> {{равно <tex>k ---}} [https:1<//rutex>.wikipedia.orgТак как <tex>|B| > |A|</wikitex>, следовательно количество ребер в множестве <tex>B</%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%28%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2%29|tex> не меньше <tex>rk</tex>-ориентированное дерево]. Пусть граф все ребра из множества <tex>B</tex> ведут в вершины множества <tex>GA</tex> {{---}} неориентированный граф, соответствующий графу значит в каждую вершину множества <tex>DA</tex> входит по одному ребру множества <tex>B</tex>. Тогда рассмотрим два матроида возьмем то ребро, которое указывает в корень (в вершину с нулевой степенью захода), получим ориентированное дерево с новым корнем.Пусть не все ребра множества <tex>M_1 = \langle A, \mathcal{I}_1 \rangle, M_2 = \langle A, \mathcal{I}_2 \rangleB</tex>, где указывают в вершины множества <tex>A</tex> {{---}} множество ребёр графа, тогда возьмем то ребро <tex>M_1uv</tex> {{---}} графовый матроид , которое указывает в вершину не принадлежащую <tex>GA</tex>. Покажем, что оно нам подойдет. Если <tex>u \mathcal{I}_2 = \{F \subseteq X: \deg^-in V(vA) </tex>, тогда наше текущее ориентированное дерево пополнится еще одной вершиной и ведущем к ней ребру.Если <tex>u \leqslant 1 \: \forall v \in notin V (A)</tex>, то мы получим еще одно ориентированное дерево.Таким образом, мы нашли ребро в множестве <tex>B \setminus \{r\} \}A</tex>, которое можем добавить в множество <tex>A</tex>с сохранением независимости. Пересечения данных матроидов является ориентированным деревом. }}

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