Пересечение матроидов, определение, примеры

Определение:

Пусть даны два матроида [math]M_1 = \langle X, \mathcal{I}_1\rangle[/math] и [math]M_2 = \langle X, \mathcal{I}_2 \rangle[/math]. Пересечением матроидов (англ. matroid intersection) [math]M_1[/math] и [math]M_2[/math] называется пара [math]M_1 \cap M_2 = \langle X, \mathcal{I} \rangle[/math], где [math]X[/math] — носитель исходных матроидов, а [math] \mathcal{I} = \mathcal{I}_1 \cap \mathcal{I}_2[/math].

• Пересечение матроидов не всегда является матроидом.
• Пересечение трех и более матроидов — это NP-полная задача.

Разноцветный лес

[math]M_1[/math] — графовый матроид, [math]M_2[/math] — разноцветный матроид (англ. multicolored matroid) (Множество независимо, если в нём нет двух ребер одного цвета). Тогда их пересечение — это разноцветный лес (англ. rainbow forests).

Утверждение:

Пересечение данных матроидов не является матроидом.

[math]\triangleright[/math]

Рассмотрим пару [math]\langle X, \mathcal{I}\rangle[/math], [math]X[/math] — ребра разноцветного леса, [math] \mathcal{I} = \mathcal{I}_1 \cap \mathcal{I}_2[/math]. Данная пара не является матроидом, так как не выполняется третье свойство матроида, то есть [math]\exists A, B \in \mathcal{I}, |A| \gt |B| [/math] и [math]\nexists \, x \in A \setminus B : B \cup \{x\} \in \mathcal{I}[/math] (См. пример 1) Пример 1

[math]\triangleleft[/math]

Двудольный граф

Пусть [math]G[/math] — двудольный граф и заданы два матроида [math]M_1 = \langle X, \mathcal{I}_1 \rangle[/math], [math]M_2 = \langle X, \mathcal{I}_2 \rangle[/math], где [math]X[/math] — множество ребёр графа, [math]\mathcal{I}_1 = \{F \subseteq X: \deg(v) \leqslant 1 \: \forall v \in L \}[/math], [math]\mathcal{I}_2 = \{F \subseteq X: \deg(v) \leqslant 1 \: \forall v \in R \}[/math]. Тогда их пересечение — это множество всевозможных паросочетаний графа.

Утверждение:

Пересечение данных матроидов не является матроидом.

[math]\triangleright[/math]

Рассмотрим пару [math]\langle X, \mathcal{I}\rangle[/math], [math]X[/math] — носитель, [math] \mathcal{I} = \mathcal{I}_1 \cap \mathcal{I}_2[/math]. Данная пара не является матроидом, так как не выполняется третье свойство матроида, то есть [math]\exists A, B \in \mathcal{I}, |A| \gt |B| [/math] и [math]\nexists \, x \in A \setminus B : B \cup \{x\} \in \mathcal{I}[/math] (См. пример 2) Пример 2

[math]\triangleleft[/math]

Ориентированный лес

Определение:

Ориентированное дерево (англ. arborescence) — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода [math]1[/math] (в них ведёт ровно по одной дуге).

Пусть [math]D = \langle V, X \rangle [/math] — ориентированнный граф. Граф [math]G[/math] — неориентированный граф, соответствующий графу [math]D[/math]. Тогда рассмотрим два матроида [math]M_1 = \langle X, \mathcal{I}_1 \rangle, M_2 = \langle X, \mathcal{I}_2 \rangle[/math], где [math]X[/math] — множество ребёр графа. [math]M_1[/math] — графовый матроид [math]G[/math], [math]\mathcal{I}_1 = \{X' \subseteq X: X'[/math] — лес в [math]G \}[/math]. [math]M_2[/math] — матроид разбиений графа [math]D[/math], [math]\mathcal{I}_2 = \{X' \subseteq X: |\deg^-(v) \cap X'| \leqslant 1, \forall v \in V \}[/math]. Пересечение данных матроидов являются множества ориентированных лесов.

Утверждение:

Пересечение данных матроидов является матроид.

[math]\triangleright[/math]

Рассмотрим матроид пересечения [math]M = \langle X, \mathcal{I} \rangle[/math], [math]A[/math] — множество ребер, [math]\mathcal{I} = \mathcal{I}_1 \cap \mathcal{I}_2[/math] Проверим выполнение аксиом независимости: 1) [math]\varnothing \in \mathcal{I}[/math] Пустое множество является ориентированным деревом, а значит входит в [math]\mathcal{I}[/math]. 2) [math]A \subset B, \ B \in \mathcal{I} \Rightarrow A \in \mathcal{I}[/math] Любой подграф ориентированного леса также является ориентированным лесом, так как во-первых, степень захода каждой вершины в подграфе могла только уменьшится, во-вторых, подграф ацикличного графа — ацикличен. 3) [math]A \in \mathcal{I}, \ B \in I, \ \left\vert A \right\vert \lt \left\vert B \right\vert \Rightarrow \mathcal {9} x \in B \setminus A, \ A \cup \mathcal{f} x \mathcal {g} \in \mathcal{I}[/math] Найдем такое ребро в множестве [math]B \setminus A[/math], которое не указывает ни в одну из вершин, в которые указывают ребра из множества [math]A[/math]. Пусть количество вершин в множестве [math]A[/math] равно [math]k[/math]. Тогда количество ребер в [math]A[/math] равно [math]k - 1[/math]. Так как [math]|B| \gt |A|[/math], следовательно количество ребер в множестве [math]B[/math] не меньше [math]k[/math]. Пусть все ребра из множества [math]B[/math] ведут в вершины множества [math]A[/math], значит в каждую вершину множества [math]A[/math] входит по одному ребру множества [math]B[/math]. Тогда возьмем то ребро, которое указывает в корень (в вершину с нулевой степенью захода), получим ориентированное дерево с новым корнем. Пусть не все ребра множества [math]B[/math] указывают в вершины множества [math]A[/math], тогда возьмем то ребро [math]uv[/math], которое указывает в вершину не принадлежащую [math]A[/math]. Покажем, что оно нам подойдет. Если [math]u \in V(A)[/math], тогда наше текущее ориентированное дерево пополнится еще одной вершиной и ведущем к ней ребру. Если [math]u \notin V(A)[/math], то мы получим еще одно ориентированное дерево. Таким образом, мы нашли ребро в множестве [math]B \setminus A[/math], которое можем добавить в множество [math]A[/math] с сохранением независимости.

[math]\triangleleft[/math]

См. также

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

Источники информации

• Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы (глава 4. Матроиды)
• Lecture notes on matroid intersection