1
правка
Изменения
м
→Ориентированный лес опечатка
}}
* Пересечение матроидов не всегда является матроидом.
* Пересечение трех и более матроидов {{---}} это является [[https://ru.wikipedia.org/wiki/Примеры NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0полных языков| NP-полная задачаполной задачей]].
|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]]
{{Утверждение
|statement = Пересечение данных матроидов является матроидматроидом.
|proof =
Рассмотрим матроид пересечения <tex>M = \langle X, \mathcal{I} \rangle</tex>, <tex>A</tex> {{---}} множество ребер, <tex>\mathcal{I} = \mathcal{I}_1 \cap \mathcal{I}_2</tex>
Любой подграф ориентированного леса также является ориентированным лесом, так как во-первых, степень захода каждой вершины в подграфе могла только уменьшится, во-вторых, подграф ацикличного графа {{---}} ацикличен.
3) <tex>A \in \mathcal{I}, \ B \in I, \ \left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \mathcal {9} exists \, x \in B \setminus A, \ A \cup \mathcal{f} x \mathcal {g} \in \mathcal{I}</tex>
Пусть количество вершин в множестве <tex>A</tex> равно <tex>k</tex>.
