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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Пусть даны два матроида <tex>M_1 = \langle X, I_1\rangle</tex> и <tex>M_2 = \langle X, I_2 \rangle</tex>. '''Пересечением матроидов''' <tex>M_1</tex> и <tex>M_2</tex> называется пара <tex>M_1 \cap M_2 = \langle X, I \rangle</tex>, где <tex>X</tex> - носитель исходных матроидов, а <tex> I = I_1 \cap I_2</tex>.
+
Пусть даны два матроида <tex>M_1 = \langle X, I_1\rangle</tex> и <tex>M_2 = \langle X, I_2 \rangle</tex>. '''Пересечением матроидов''' <tex>M_1</tex> и <tex>M_2</tex> называется пара <tex>M_1 \cap M_2 = \langle X, I \rangle</tex>, где <tex>X</tex> носитель исходных матроидов, а <tex> I = I_1 \cap I_2</tex>.
 
}}
 
}}
  
 
==Примеры==
 
==Примеры==
  
1) <tex>M_1</tex> - графовый матроид, <tex>M_2</tex> - "разноцветный" матроид (Множество независимо, если в нём нет двух ребер одного цвета). Тогда их пересечение - это разноцветный лес (англ. Rainbow forests)
+
# <tex>M_1</tex> графовый матроид, <tex>M_2</tex> "разноцветный" матроид (Множество независимо, если в нём нет двух ребер одного цвета). Тогда их пересечение это разноцветный лес (англ. rainbow forests).
 
+
# Пусть <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>. Тогда их пересечение это множество всевозможных паросочетаний графа.
2) Пусть <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>. Тогда их пересечение - это множество всевозможных паросочетаний графа.
 
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Матроиды]]
 
[[Категория:Матроиды]]

Версия 07:35, 12 октября 2011

Определение:
Пусть даны два матроида [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]. Тогда их пересечение — это множество всевозможных паросочетаний графа.