Пересечение матроидов, определение, примеры — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 35 промежуточных версий 8 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition =
 
|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>.
+
Пусть даны два матроида <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>.
 +
Пересечение данных матроидов являются множества ориентированных лесов.
 +
 
 +
{{Утверждение
 +
|statement = Пересечение данных матроидов является матроидом.
 +
|proof =
 +
Рассмотрим матроид пересечения <tex>M = \langle X, \mathcal{I} \rangle</tex>, <tex>A</tex> {{---}} множество ребер, <tex>\mathcal{I} = \mathcal{I}_1 \cap \mathcal{I}_2</tex>
 +
 
 +
Проверим выполнение аксиом независимости:
 +
 
 +
1) <tex>\varnothing \in \mathcal{I}</tex>
 +
 
 +
Пустое множество является ориентированным деревом, а значит входит в <tex>\mathcal{I}</tex>.
 +
 
 +
2) <tex>A \subset B, \ B \in \mathcal{I} \Rightarrow A \in \mathcal{I}</tex>
 +
Любой подграф ориентированного леса также является ориентированным лесом, так как во-первых, степень захода каждой вершины в подграфе могла только уменьшится, во-вторых, подграф ацикличного графа {{---}} ацикличен.
 +
 
 +
3) <tex>A \in \mathcal{I}, \ B \in I, \ \left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \exists \, x \in B \setminus A, \ A \cup \{ x \} \in \mathcal{I}</tex>
 +
 
 +
Пусть количество вершин в множестве <tex>A</tex> равно <tex>k</tex>.
 +
Тогда количество ребер в <tex>A</tex> равно <tex>k - 1</tex>.
 +
Так как <tex>|B| > |A|</tex>, следовательно количество ребер в множестве <tex>B</tex> не меньше <tex>k</tex>.
 +
Пусть все ребра из множества <tex>B</tex> ведут в вершины множества <tex>A</tex>, значит в каждую вершину множества <tex>A</tex> входит по одному ребру множества <tex>B</tex>.
 +
Тогда возьмем то ребро, которое указывает в корень (в вершину с нулевой степенью захода), получим ориентированное дерево с новым корнем ('''ну или же получим цикл lol''').
 +
Пусть не все ребра множества <tex>B</tex> указывают в вершины множества <tex>A</tex>, тогда возьмем то ребро <tex>uv</tex>, которое указывает в вершину не принадлежащую <tex>A</tex>. Покажем, что оно нам подойдет.
 +
Если <tex>u \in V(A)</tex>, тогда наше текущее ориентированное дерево пополнится еще одной вершиной и ведущем к ней ребру.
 +
Если <tex>u \notin V(A)</tex>, то мы получим еще одно ориентированное дерево.
 +
Таким образом, мы нашли ребро в множестве <tex>B \setminus A</tex>, которое можем добавить в множество <tex>A</tex> с сохранением независимости.
 +
 
 +
}}
 +
 
 +
{{Утверждение
 +
|statement = Пересечение данных матроидов не является матроидом.
 +
|proof =
 +
Не выполняется третье свойство матроидов, см. пример.
 +
 
 +
Дан граф <tex>D=(V,X)</tex>, где <tex>V = \{ 1, 2, 3, 4 \}</tex>, а <tex>X = \{ a=(1,2), b=(2,3), c=(3,4), d=(4,2) \}</tex>, тогда достаточно рассмотреть два множества $A=\{ a,b,c \}$ и $B=\{ b,d \}$, чтобы понять, что не выполняется третье свойство матроидов.
 
}}
 
}}
  
==Примеры==
+
== См. также==
 +
* [[Примеры матроидов]]
 +
* [[Алгоритм построения базы в пересечении матроидов]]
 +
* [[Алгоритм построения базы в объединении матроидов]]
  
1) <tex>M_1</tex> - графовый матроид, <tex>M_2</tex> - "разноцветный" матроид (Множество независимо, если в нём нет двух ребер одного цвета). Тогда их пересечение - это разноцветный лес (англ. Rainbow forests)
+
==Источники информации ==
 +
* Асанов М. О., Баранский В. А., Расин В. В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы (глава 4. Матроиды)
 +
* [http://www-math.mit.edu/~goemans/18433S09/matroid-intersect-notes.pdf Lecture notes on matroid intersection]
  
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>. Тогда их пересечение - это множество всевозможных паросочетаний графа.
+
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Матроиды]]

Текущая версия на 19:15, 4 сентября 2022

Определение:
Пусть даны два матроида [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] (См. пример [math]1[/math])

Пример 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 \exists \, x \in B \setminus A, \ A \cup \{ x \} \in \mathcal{I}[/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]. Тогда возьмем то ребро, которое указывает в корень (в вершину с нулевой степенью захода), получим ориентированное дерево с новым корнем (ну или же получим цикл lol). Пусть не все ребра множества [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]
Утверждение:
Пересечение данных матроидов не является матроидом.
[math]\triangleright[/math]

Не выполняется третье свойство матроидов, см. пример.

Дан граф [math]D=(V,X)[/math], где [math]V = \{ 1, 2, 3, 4 \}[/math], а [math]X = \{ a=(1,2), b=(2,3), c=(3,4), d=(4,2) \}[/math], тогда достаточно рассмотреть два множества $A=\{ a,b,c \}$ и $B=\{ b,d \}$, чтобы понять, что не выполняется третье свойство матроидов.
[math]\triangleleft[/math]

См. также

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

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