|
|
| Строка 19: |
Строка 19: |
| | |definition= | | |definition= |
| | '''Цикл матроида''' — минимальное по включению зависимое множество. | | '''Цикл матроида''' — минимальное по включению зависимое множество. |
| − | }}
| |
| − |
| |
| − | ==Определение в терминах баз==
| |
| − | {{Определение
| |
| − | |definition=
| |
| − | '''Матроид''' — пара <tex>(X, B)</tex>, где <tex>X</tex> — конечное множество, называемое '''носителем матроида''', <tex>B</tex> — семейство подмножеств <tex>X</tex>, называемое множеством '''баз матроида''', для которых выполняются условия:
| |
| − | #<tex>B \ne \varnothing</tex>
| |
| − | #Если <tex>B_1, B_2 \in B</tex> и <tex>B_1 \ne B_2</tex>, то <tex>B_1 \not\subset B_2</tex> и <tex>B_2 \not\subset B_1</tex>
| |
| − | #Если <tex>B_1, B_2 \in B</tex>, то <tex>\forall \, b_1 \in B_1 \: \exists \, b_2 \in B_2 : (B_1 \setminus b_1) \cup b_2 \in B</tex>
| |
| − | }}
| |
| − |
| |
| − | ==Определение в терминах циклов==
| |
| − | {{Определение
| |
| − | |definition=
| |
| − | '''Матроид''' — пара <tex>(X, C)</tex>, где <tex>X</tex> — конечное множество, называемое '''носителем матроида''', <tex>C</tex> — семейство подмножеств <tex>X</tex>, называемое множеством '''циклов матроида''', для которых выполняются условия:
| |
| − | #<tex>\varnothing \notin C</tex>
| |
| − | #Если <tex>C_1, C_2 \in C</tex> и <tex>C_1 \subset C_2</tex>, то <tex>C_1 = C_2</tex>
| |
| − | #Если <tex>C_1, C_2 \in C, \, C_1 \ne C_2, \, x \in C_1 \cap C_2</tex>, то <tex>\exists \, C_3 \in C : C_3 \subset (C_1 \cup C_3 \setminus x)</tex>
| |
| | }} | | }} |
| | | | |
Аксиоматическое определение
| Определение: |
Матроид — пара [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] и [math]|A| \gt |B|[/math], то [math] \exists \, x \in A \setminus B[/math] такой, что [math]B \cup \{x\} \in I[/math]
|
| Определение: |
| База матроида — максимальное по включению независимое множество. |
| Определение: |
| Зависимое множество — подмножество носителя матроида, не являющееся независимым. |
| Определение: |
| Цикл матроида — минимальное по включению зависимое множество. |
См. также
Литература
Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
