Изменения
Новая страница: «== Аксиоматическое определение == '''Матроид''' — пара <math>(X,I)</math>, где <math>X</math> — конечное множ…»
== Аксиоматическое определение ==
'''Матроид''' — пара <math>(X,I)</math>, где <math>X</math> — конечное множество, называемое носителем
матроида, а <math>I</math> — некоторое множество подмножеств <math>X</math>, называемое
семейством ''независимых'' множеств , то есть <math>I \subset 2^X </math>. При этом должны
выполняться следующие условия:
# <math>\varnothing \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>X \notin I</math> называются ''зависимыми'' множествами.
Минимальные по включению зависимые множества называются ''циклами'' матроида, это понятие используется в альтернативном определении матроида.
== Определение в терминах правильного замыкания ==
'''Матроид''' — пара <math>(X, A\to H(A))</math>, где <math>X</math> — конечное множество, называемое носителем
матроида, а <math>A \to H(A)</math> — правильное замыкание на <math>(2^X,\le)</math>
'''Матроид''' — пара <math>(X,I)</math>, где <math>X</math> — конечное множество, называемое носителем
матроида, а <math>I</math> — некоторое множество подмножеств <math>X</math>, называемое
семейством ''независимых'' множеств , то есть <math>I \subset 2^X </math>. При этом должны
выполняться следующие условия:
# <math>\varnothing \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>X \notin I</math> называются ''зависимыми'' множествами.
Минимальные по включению зависимые множества называются ''циклами'' матроида, это понятие используется в альтернативном определении матроида.
== Определение в терминах правильного замыкания ==
'''Матроид''' — пара <math>(X, A\to H(A))</math>, где <math>X</math> — конечное множество, называемое носителем
матроида, а <math>A \to H(A)</math> — правильное замыкание на <math>(2^X,\le)</math>
