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

Материал из Викиконспекты
Перейти к: навигация, поиск
(не показана 51 промежуточная версия 6 участников)
Строка 1: Строка 1:
 
== Аксиоматическое определение ==
 
== Аксиоматическое определение ==
 
{{Определение
 
{{Определение
 +
|id=def_matroid
 
|definition=
 
|definition=
−
'''Матроид''' — пара <tex>(X,I)</tex>, где <tex>X</tex> — конечное множество, называемое носителем
+
'''Матроид''' (англ. ''matroid'') {{---}} пара <tex>\langle X,I \rangle</tex>, где <tex>X</tex> {{---}} конечное множество, называемое '''носителем матроида''' (англ. ''ground'' ''set''), а <tex>I</tex> {{---}} некоторое множество подмножеств <tex>X</tex>, называемое семейством '''независимых множеств''' (англ. ''independent'' ''sets''), то есть <tex>I \subset 2^X </tex>. При этом должны выполняться следующие условия:
−
матроида, а <tex>I</tex> — некоторое множество подмножеств <tex>X</tex>, называемое
 
−
семейством ''независимых'' множеств , то есть <tex>I \subset 2^X </tex>. При этом должны
 
−
выполняться следующие условия:
 
 
# <tex>\varnothing \in I</tex>
 
# <tex>\varnothing \in I</tex>
−
# Если <tex>A \in I </tex> и <tex> B \subset A</tex>, то <tex>B \in I</tex>
+
# если <tex>A \in I </tex> и <tex> B \subset A</tex>, то <tex>B \in I</tex>
−
# Если <tex>A,B \in I</tex> и <tex>|A| > |B|</tex>, то <tex> \exists \, x \in A \setminus B</tex> такой, что <tex>B \cup \{x\} \in I</tex>
+
# если <tex>A,B \in I</tex> и <tex>|A| > |B|</tex>, то <tex> \exists \, x \in A \setminus B \mid B \cup \{x\} \in I</tex>
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''База матроида''' - максимальное по включению независимое множество.
+
'''База матроида''' (англ. ''base'') {{---}} максимальное по включению независимое множество.
 
}}
 
}}
 +
 
{{Определение
 
{{Определение
 +
|id=def_rank_of_matroid
 
|definition=
 
|definition=
−
'''Зависимое множество''' - подмножество носителя матроида, не являющееся независимым.
+
'''Рангом''' матроида называется мощность его баз. Ранг тривиального матроида равен нулю.
 
}}
 
}}
 +
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Цикл матроида''' - минимальное по включению зависимое множество.
+
'''Зависимое множество''' (англ. ''dependent'' ''set'')  {{---}} подмножество носителя матроида, не являющееся независимым.
 
}}
 
}}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Ранг матроида''' - мощность баз данного матроида.
+
'''Цикл матроида''' (англ. ''cicruit'') {{---}} минимальное по включению зависимое множество.
 
}}
 
}}
  
−
==Определение в терминах циклов==
 
 
{{Определение
 
{{Определение
 +
|id = def5
 
|definition=
 
|definition=
−
'''Матроид''' - пара <tex>(X, C)</tex>, где <tex>X</tex> - носитель матроида, <tex>C</tex> - семейство подмножеств <tex>X</tex>, называемое множеством '''циклов матроида''', для которых выполняются условия:
+
Матроиды <tex>M_1 = \langle X_1,I_1 \rangle</tex> и <tex>M_2 = \langle X_2,I_2 \rangle</tex> называются '''изоморфными''' (англ. ''isomorphic matroids''), если существует биекция (взаммно-однозначное отображение) <tex>\varphi\colon \ X_1 \rightarrow X_2</tex>, сохраняющая независимость, то есть множество <tex>A \subset I_1</tex> является независимым в матроиде <tex>M_1</tex> тогда и только тогда, когда образ этого множества при заданном отображении <tex>\varphi(A)</tex> есть независимое множество в матроиде <tex>M_2</tex>.
−
#<tex>\varnothing \notin C</tex>
 
−
#Если <tex>C_1, C_2 \in C</tex> и <tex>C_1 \subset C_2</tex>, то <tex>C_1 = C_2</tex>
 
−
#Если <tex>C_1, C_2 \in C, \, C_1 \ne C_2, \, x \in C_1 \cap C_2</tex>, то <tex>\exists \, C_3 \in C : C_3 \subset (C_1 \cup C_3 \setminus x)</tex>
 
 
}}
 
}}
  
−
==Определение в терминах баз==
+
==См. также==
−
{{Определение
+
* [[Примеры матроидов|Примеры матроидов]]
−
|definition=
+
* [[Аксиоматизация матроида базами|Аксиоматизация матроида базами]]
−
'''Матроид''' - пара <tex>(X, B)</tex>, где <tex>X</tex> - носитель матроида, <tex>B</tex> - семейство подмножеств <tex>X</tex>, называемое множеством '''баз матроида''', для которых выполняются условия:
+
* [[Аксиоматизация матроида циклами|Аксиоматизация матроида циклами]]
−
#<tex>B \ne \varnothing</tex>
+
== Источники информации ==
−
#Если <tex>B_1, B_2 \in B</tex> и <tex>B_1 \ne B_2</tex>, то <tex>B_1 \not\subset B_2</tex> и <tex>B_2 \not\subset B_1</tex>
+
 
−
#Если <tex>B_1, B_2 \in B</tex>, то <tex>\forall \, b_1 \in B_1 \: \exists \, b_2 \in B_2 : (B_1 \setminus b_1) \cup b_2 \in B</tex>
+
*''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''
−
}}
+
*[[wikipedia:Matroid | Wikipedia {{---}} Matroid]]
−
== Литература ==
+
*[[wikipedia:ru:Матроид | Википедия {{---}} Матроид]]
−
''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
+
 
 +
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Матроиды]]
 +
[[Категория:Основные факты теории матроидов]]

Версия 21:18, 8 июня 2019

Аксиоматическое определение

Определение:
Матроид (англ. matroid) — пара [math]\langle X,I \rangle[/math], где [math]X[/math] — конечное множество, называемое носителем матроида (англ. ground set), а [math]I[/math] — некоторое множество подмножеств [math]X[/math], называемое семейством независимых множеств (англ. independent sets), то есть [math]I \subset 2^X [/math]. При этом должны выполняться следующие условия:
  1. [math]\varnothing \in I[/math]
  2. если [math]A \in I [/math] и [math] B \subset A[/math], то [math]B \in I[/math]
  3. если [math]A,B \in I[/math] и [math]|A| \gt |B|[/math], то [math] \exists \, x \in A \setminus B \mid B \cup \{x\} \in I[/math]


Определение:
База матроида (англ. base) — максимальное по включению независимое множество.


Определение:
Рангом матроида называется мощность его баз. Ранг тривиального матроида равен нулю.


Определение:
Зависимое множество (англ. dependent set) — подмножество носителя матроида, не являющееся независимым.


Определение:
Цикл матроида (англ. cicruit) — минимальное по включению зависимое множество.


Определение:
Матроиды [math]M_1 = \langle X_1,I_1 \rangle[/math] и [math]M_2 = \langle X_2,I_2 \rangle[/math] называются изоморфными (англ. isomorphic matroids), если существует биекция (взаммно-однозначное отображение) [math]\varphi\colon \ X_1 \rightarrow X_2[/math], сохраняющая независимость, то есть множество [math]A \subset I_1[/math] является независимым в матроиде [math]M_1[/math] тогда и только тогда, когда образ этого множества при заданном отображении [math]\varphi(A)[/math] есть независимое множество в матроиде [math]M_2[/math].


См. также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Определение_матроида&oldid=71644»