Определение матроида — различия между версиями
Sergej (обсуждение | вклад) (→Аксиоматическое определение) |
Sergej (обсуждение | вклад) (→Литература) |
||
Строка 25: | Строка 25: | ||
* [[Аксиоматизация матроида базами|Аксиоматизация матроида базами]] | * [[Аксиоматизация матроида базами|Аксиоматизация матроида базами]] | ||
* [[Аксиоматизация матроида циклами|Аксиоматизация матроида циклами]] | * [[Аксиоматизация матроида циклами|Аксиоматизация матроида циклами]] | ||
− | == | + | == Источники информации == |
+ | |||
''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br /> | ''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br /> | ||
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Матроиды]] | [[Категория:Матроиды]] |
Версия 15:05, 6 мая 2014
Аксиоматическое определение
Определение: |
Матроид — пара
| , где — конечное множество, называемое носителем матроида, а — некоторое множество подмножеств , называемое семейством независимых множеств , то есть . При этом должны выполняться следующие условия:
Определение: |
База матроида — максимальное по включению независимое множество. |
Определение: |
Зависимое множество — подмножество носителя матроида, не являющееся независимым. |
Определение: |
Цикл матроида — минимальное по включению зависимое множество. |
См. также
Источники информации
Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2