Определение матроида — различия между версиями
| Строка 1: | Строка 1: | ||
== Аксиоматическое определение == | == Аксиоматическое определение == | ||
| + | {{Определение | ||
| + | |definition= | ||
'''Матроид''' — пара <math>(X,I)</math>, где <math>X</math> — конечное множество, называемое носителем | '''Матроид''' — пара <math>(X,I)</math>, где <math>X</math> — конечное множество, называемое носителем | ||
матроида, а <math>I</math> — некоторое множество подмножеств <math>X</math>, называемое | матроида, а <math>I</math> — некоторое множество подмножеств <math>X</math>, называемое | ||
семейством ''независимых'' множеств , то есть <math>I \subset 2^X </math>. При этом должны | семейством ''независимых'' множеств , то есть <math>I \subset 2^X </math>. При этом должны | ||
выполняться следующие условия: | выполняться следующие условия: | ||
| − | |||
# <math>\varnothing \in I</math> | # <math>\varnothing \in I</math> | ||
# Если <math>A \in I </math> и <math> B \subset A</math>, то <math>B \in I</math> | # Если <math>A \in I </math> и <math> B \subset A</math>, то <math>B \in I</math> | ||
# Если <math>A,B \in I</math> и мощность A больше мощности B, то существует <math>x \in A \setminus B</math> такой, что <math>B \cup \{x\} \in I</math> | # Если <math>A,B \in I</math> и мощность A больше мощности B, то существует <math>x \in A \setminus B</math> такой, что <math>B \cup \{x\} \in I</math> | ||
| − | + | }} | |
== Определение в терминах правильного замыкания == | == Определение в терминах правильного замыкания == | ||
| + | {{Определение | ||
| + | |definition= | ||
'''Матроидом''' называется непустое множество <math>E</math> вместе с [[Оператор_замыкания_для_матроидов | оператором замыкания]]<math>A \to \langle A \rangle</math> такое, что | '''Матроидом''' называется непустое множество <math>E</math> вместе с [[Оператор_замыкания_для_матроидов | оператором замыкания]]<math>A \to \langle A \rangle</math> такое, что | ||
#<math>\forall p,q \in E</math> и <math>A \subset E</math> из <math>q \notin \langle A \rangle</math> и <math> q \in \langle A \cup p \rangle \Rightarrow p \in \langle A \cup q \rangle</math> | #<math>\forall p,q \in E</math> и <math>A \subset E</math> из <math>q \notin \langle A \rangle</math> и <math> q \in \langle A \cup p \rangle \Rightarrow p \in \langle A \cup q \rangle</math> | ||
#<math>\forall A \subset E</math> существует такое множество <math>B \subset A</math>, что <math>\langle A \rangle = \langle B \rangle </math> | #<math>\forall A \subset E</math> существует такое множество <math>B \subset A</math>, что <math>\langle A \rangle = \langle B \rangle </math> | ||
| − | + | }} | |
== Дополнительные понятия == | == Дополнительные понятия == | ||
*'''Базами''' матроида называются максимальные по включению независимые множества. | *'''Базами''' матроида называются максимальные по включению независимые множества. | ||
*'''Рангом''' матроида называется мощность его баз. Ранг тривиального матроида равен нулю. | *'''Рангом''' матроида называется мощность его баз. Ранг тривиального матроида равен нулю. | ||
| − | + | *'''Зависимое множество''' - подмножество носителя, не являющееся независимым. | |
| + | *'''Циклами''' матроида называются минимальные по включению зависимые множества. | ||
== Литература == | == Литература == | ||
''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br /> | ''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br /> | ||
Версия 21:06, 26 июня 2011
Содержание
Аксиоматическое определение
| Определение: |
| Матроид — пара , где — конечное множество, называемое носителем
матроида, а — некоторое множество подмножеств , называемое семейством независимых множеств , то есть . При этом должны выполняться следующие условия:
|
Определение в терминах правильного замыкания
| Определение: |
Матроидом называется непустое множество вместе с оператором замыкания такое, что
|
Дополнительные понятия
- Базами матроида называются максимальные по включению независимые множества.
- Рангом матроида называется мощность его баз. Ранг тривиального матроида равен нулю.
- Зависимое множество - подмножество носителя, не являющееся независимым.
- Циклами матроида называются минимальные по включению зависимые множества.
Литература
Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
