Определение матроида — различия между версиями
| Строка 4: | Строка 4: | ||
'''Матроид''' — пара <tex>(X,I)</tex>, где <tex>X</tex> — конечное множество, называемое '''носителем матроида''', а <tex>I</tex> — некоторое множество подмножеств <tex>X</tex>, называемое семейством '''независимых множеств''' , то есть <tex>I \subset 2^X </tex>. При этом должны выполняться следующие условия: | '''Матроид''' — пара <tex>(X,I)</tex>, где <tex>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,B \in I</tex> и <tex>|A| > |B|</tex>, то <tex> \exists \, x \in A \setminus B : B \cup \{x\} \in I</tex> |
}} | }} | ||
Версия 22:47, 26 июня 2011
Аксиоматическое определение
| Определение: |
Матроид — пара , где — конечное множество, называемое носителем матроида, а — некоторое множество подмножеств , называемое семейством независимых множеств , то есть . При этом должны выполняться следующие условия:
|
| Определение: |
| База матроида — максимальное по включению независимое множество. |
| Определение: |
| Зависимое множество — подмножество носителя матроида, не являющееся независимым. |
| Определение: |
| Цикл матроида — минимальное по включению зависимое множество. |
См. также
Литература
Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
