Определение матроида — различия между версиями
Sergej (обсуждение | вклад) (→Аксиоматическое определение) |
м (rollbackEdits.php mass rollback) |
||
| (не показано 37 промежуточных версий 8 участников) | |||
| Строка 1: | Строка 1: | ||
== Аксиоматическое определение == | == Аксиоматическое определение == | ||
{{Определение | {{Определение | ||
| + | |id=def_matroid | ||
|definition= | |definition= | ||
| − | '''Матроид''' {{---}} пара <tex>\langle X,I \rangle</tex>, где <tex>X</tex> {{---}} конечное множество, называемое '''носителем матроида''', а <tex>I</tex> {{---}} некоторое множество подмножеств <tex>X</tex>, называемое семейством '''независимых множеств''' , то есть <tex>I \subset 2^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>\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>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= | ||
| − | '''Зависимое множество''' {{---}} подмножество носителя матроида, не являющееся независимым. | + | '''Зависимое множество''' (англ. ''dependent'' ''set'') {{---}} подмножество носителя матроида, не являющееся независимым. |
}} | }} | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | '''Цикл матроида''' {{---}} минимальное по включению зависимое множество. | + | '''Цикл матроида''' (англ. ''circuit'') {{---}} минимальное по включению зависимое множество. |
| + | }} | ||
| + | |||
| + | {{Определение | ||
| + | |id = def5 | ||
| + | |definition= | ||
| + | Матроиды <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>. | ||
}} | }} | ||
| Строка 27: | Строка 41: | ||
== Источники информации == | == Источники информации == | ||
| − | ''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2''' | + | *''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2''' |
| − | [[Wikipedia | + | *[[wikipedia:Matroid | Wikipedia {{---}} Matroid]] |
| − | [[ | + | *[[wikipedia:ru:Матроид | Википедия {{---}} Матроид]] |
| − | + | ||
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Матроиды]] | [[Категория:Матроиды]] | ||
| + | [[Категория:Основные факты теории матроидов]] | ||
Текущая версия на 19:10, 4 сентября 2022
Аксиоматическое определение
| Определение: |
Матроид (англ. matroid) — пара , где — конечное множество, называемое носителем матроида (англ. ground set), а — некоторое множество подмножеств , называемое семейством независимых множеств (англ. independent sets), то есть . При этом должны выполняться следующие условия:
|
| Определение: |
| База матроида (англ. base) — максимальное по включению независимое множество. |
| Определение: |
| Рангом матроида называется мощность его баз. Ранг тривиального матроида равен нулю. |
| Определение: |
| Зависимое множество (англ. dependent set) — подмножество носителя матроида, не являющееся независимым. |
| Определение: |
| Цикл матроида (англ. circuit) — минимальное по включению зависимое множество. |
| Определение: |
| Матроиды и называются изоморфными (англ. isomorphic matroids), если существует биекция (взаммно-однозначное отображение) , сохраняющая независимость, то есть множество является независимым в матроиде тогда и только тогда, когда образ этого множества при заданном отображении есть независимое множество в матроиде . |
См. также
Источники информации
- Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
- Wikipedia — Matroid
- Википедия — Матроид
