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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 8: Строка 8:
 
# Пересечение трех и более матроидов {{---}} это NP-полная задача.
 
# Пересечение трех и более матроидов {{---}} это NP-полная задача.
  
==Примеры==
+
== Разноцветное дерево ==
  
# <tex>M_1</tex> {{---}} графовый матроид, <tex>M_2</tex> {{---}} '''разноцветный матроид''' (англ. ''multicolored matroid'') (Множество независимо, если в нём нет двух ребер одного цвета). Тогда их пересечение {{---}} это разноцветный лес (англ. ''rainbow forests'').
+
<tex>M_1</tex> {{---}} графовый матроид, <tex>M_2</tex> {{---}} '''разноцветный матроид''' (англ. ''multicolored matroid'') (Множество независимо, если в нём нет двух ребер одного цвета). Тогда их пересечение {{---}} это разноцветный лес (англ. ''rainbow forests'').
# Пусть <tex>G</tex> {{---}} двудольный граф и заданы два матроида <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>. Тогда их пересечение {{---}} это множество всевозможных паросочетаний графа. Заметим, что пересечение данных матроидов не является матроидом.
+
 
# Пусть <tex>D = \langle V, A \rangle </tex> {{---}} [https://ru.wikipedia.org/wiki/%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>r</tex>-ориентированное дерево]. Пусть граф <tex>G</tex> {{---}} неориентированный граф, соответствующий графу <tex>D</tex>. Тогда рассмотрим два матроида <tex>M_1 = \langle A, \mathcal{I}_1 \rangle, M_2 = \langle A, \mathcal{I}_2 \rangle</tex>, где <tex>A</tex> {{---}} множество ребёр графа, <tex>M_1</tex> {{---}} графовый матроид <tex>G</tex>, <tex>\mathcal{I}_2 = \{F \subseteq X: \deg^-(v) \leqslant 1 \: \forall v \in V \setminus \{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>G</tex> {{---}} двудольный граф и заданы два матроида <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 I, |A| > |B| </tex> и <tex>\nexists \, x \in A \setminus B : B \cup \{x\} \in I</tex> (См. пример 1)
 +
[[Файл:Example_DY.png|200px|thumb|left|Пример 1]]
 +
}}
 +
 
 +
== Ориентированное дерево ==
 +
{{Определение
 +
|definition=
 +
'''Ориентированное дерево''' (англ. ''arborescence'') {{---}} ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге).
 +
}}
 +
Пусть <tex>D = \langle V, A \rangle </tex> {{---}} <tex>r</tex>-ориентированное дерево. Пусть граф <tex>G</tex> {{---}} неориентированный граф, соответствующий графу <tex>D</tex>. Тогда рассмотрим два матроида <tex>M_1 = \langle A, \mathcal{I}_1 \rangle, M_2 = \langle A, \mathcal{I}_2 \rangle</tex>, где <tex>A</tex> {{---}} множество ребёр графа, <tex>M_1</tex> {{---}} графовый матроид <tex>G</tex>, <tex>\mathcal{I}_2 = \{F \subseteq X: \deg^-(v) \leqslant 1 \: \forall v \in V \setminus \{r\} \}</tex>. Пересечения данных матроидов является ориентированным деревом.
  
 
== См. также==
 
== См. также==

Версия 22:48, 8 июня 2015

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


  1. Пересечение матроидов не всегда является матроидом.
  2. Пересечение трех и более матроидов — это 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]\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 I, |A| \gt |B| [/math] и [math]\nexists \, x \in A \setminus B : B \cup \{x\} \in I[/math] (См. пример 1)

Пример 1
[math]\triangleleft[/math]

Ориентированное дерево

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

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

См. также

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

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