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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Примеры)
(Примеры)
Строка 9: Строка 9:
 
# Пусть <tex>G</tex> {{---}} двудольный граф и заданы два матроида <tex>M_1 = \langle X, I_1 \rangle</tex>, <tex>M_2 = \langle X, I_2 \rangle</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>. Тогда их пересечение {{---}} это множество всевозможных паросочетаний графа. Заметим, что пересечение данных матроидов не является матроидом.
 
# Пусть <tex>G</tex> {{---}} двудольный граф и заданы два матроида <tex>M_1 = \langle X, I_1 \rangle</tex>, <tex>M_2 = \langle X, I_2 \rangle</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>. Тогда их пересечение {{---}} это множество всевозможных паросочетаний графа. Заметим, что пересечение данных матроидов не является матроидом.
 
# Пусть <tex>D = \langle V, A \rangle </tex> {{---}}  <tex>r</tex>-ориентированное дерево. Пусть граф <tex>G</tex> {{---}} неориентированный граф, соответствующий графу <tex>D</tex>. Тогда рассмотрим два матроида <tex>M_1 = \langle A, I_1 \rangle</tex>, <tex>M_2 = \langle A, I_2 \rangle</tex>, где <tex>A</tex> {{---}} множество ребёр графа, <tex>M_1</tex> {{---}} графовый матроид <tex>G</tex>, <tex>I_2 = \{F \subseteq X: deg^-(v) \le 1 \: \forall v \in V \setminus \{r\} \}</tex>. Пересечения данных матроидов является ориентированным деревом.
 
# Пусть <tex>D = \langle V, A \rangle </tex> {{---}}  <tex>r</tex>-ориентированное дерево. Пусть граф <tex>G</tex> {{---}} неориентированный граф, соответствующий графу <tex>D</tex>. Тогда рассмотрим два матроида <tex>M_1 = \langle A, I_1 \rangle</tex>, <tex>M_2 = \langle A, I_2 \rangle</tex>, где <tex>A</tex> {{---}} множество ребёр графа, <tex>M_1</tex> {{---}} графовый матроид <tex>G</tex>, <tex>I_2 = \{F \subseteq X: deg^-(v) \le 1 \: \forall v \in V \setminus \{r\} \}</tex>. Пересечения данных матроидов является ориентированным деревом.
 +
 +
==Источники==
 +
* Асанов М. О., Баранский В. А., Расин В. В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы (глава 4. Матроиды)
 +
* [http://www-math.mit.edu/~goemans/18433S09/matroid-intersect-notes.pdf Lecture notes on matroid intersection]
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Матроиды]]
 
[[Категория:Матроиды]]

Версия 21:28, 7 июня 2015

Определение:
Пусть даны два матроида [math]M_1 = \langle X, I_1\rangle[/math] и [math]M_2 = \langle X, I_2 \rangle[/math]. Пересечением матроидов [math]M_1[/math] и [math]M_2[/math] называется пара [math]M_1 \cap M_2 = \langle X, I \rangle[/math], где [math]X[/math] — носитель исходных матроидов, а [math] I = I_1 \cap I_2[/math].


Примеры

  1. [math]M_1[/math] — графовый матроид, [math]M_2[/math] — «разноцветный» матроид (Множество независимо, если в нём нет двух ребер одного цвета). Тогда их пересечение — это разноцветный лес (англ. rainbow forests).
  2. Пусть [math]G[/math] — двудольный граф и заданы два матроида [math]M_1 = \langle X, I_1 \rangle[/math], [math]M_2 = \langle X, I_2 \rangle[/math], где [math]X[/math] — множество ребёр графа, [math]I_1 = \{F \subseteq X: deg(v) \le 1 \: \forall v \in L \}[/math], [math]I_2 = \{F \subseteq X: deg(v) \le 1 \: \forall v \in R \}[/math]. Тогда их пересечение — это множество всевозможных паросочетаний графа. Заметим, что пересечение данных матроидов не является матроидом.
  3. Пусть [math]D = \langle V, A \rangle [/math][math]r[/math]-ориентированное дерево. Пусть граф [math]G[/math] — неориентированный граф, соответствующий графу [math]D[/math]. Тогда рассмотрим два матроида [math]M_1 = \langle A, I_1 \rangle[/math], [math]M_2 = \langle A, I_2 \rangle[/math], где [math]A[/math] — множество ребёр графа, [math]M_1[/math] — графовый матроид [math]G[/math], [math]I_2 = \{F \subseteq X: deg^-(v) \le 1 \: \forall v \in V \setminus \{r\} \}[/math]. Пересечения данных матроидов является ориентированным деревом.

Источники

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