Определение матроида — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Аксиоматическое определение)
(Аксиоматическое определение)
Строка 10: Строка 10:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''База матроида''' <tex>\mathrm{(basis matroid)}</tex> {{---}} максимальное по включению независимое множество .
+
'''База матроида''' <tex>\mathrm{(basis \ matroid)}</tex> {{---}} максимальное по включению независимое множество .
 
}}
 
}}
 
{{Определение
 
{{Определение

Версия 15:52, 6 мая 2014

Аксиоматическое определение

Определение:
Матроид [math]\mathrm{(matroid)}[/math] — пара [math]\langle X,I \rangle[/math], где [math]X[/math] — конечное множество, называемое носителем матроида [math]\mathrm{\ (ground \ set)}[/math], а [math]I[/math] — некоторое множество подмножеств [math]X[/math], называемое семейством независимых множеств [math]\mathrm{\ (independent \ sets)}[/math] , то есть [math]I \subset 2^X [/math]. При этом должны выполняться следующие условия:
  1. [math]\varnothing \in I[/math]
  2. если [math]A \in I [/math] и [math] B \subset A[/math], то [math]B \in I[/math]
  3. если [math]A,B \in I[/math] и [math]|A| \gt |B|[/math], то [math] \exists \, x \in A \setminus B : B \cup \{x\} \in I[/math]


Определение:
База матроида [math]\mathrm{(basis \ matroid)}[/math] — максимальное по включению независимое множество .


Определение:
Зависимое множество — подмножество носителя матроида, не являющееся независимым.


Определение:
Цикл матроида — минимальное по включению зависимое множество.


См. также

Источники информации