Матроид: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Матроид''' (''Matroid'') - комбинаторный объект, представляющий собой пару <math>(E, ...)
 
Нет описания правки
Строка 1: Строка 1:
'''Матроид''' (''Matroid'') -  
'''Матроид''' (''[[Matroid]]'') -  
комбинаторный объект, представляющий собой пару <math>(E, {\cal
комбинаторный объект, представляющий собой пару <math>(E, {\mathcal
B})</math>, где
B})</math>, где
<math>E</math> --- конечное непустое множество элементов матроида, а <math>{\cal B}</math>
<math>E</math> --- конечное непустое множество элементов матроида, а <math>{\mathcal B}</math>
--- непустое множество его подмножеств (называемых ''базами''),
--- непустое множество его подмножеств (называемых ''[[база|базами]]''),
удовлетворяющее следующим двум условиям (аксиомы баз):
удовлетворяющее следующим двум условиям (аксиомы баз):


Строка 13: Строка 13:


Существуют другие эквивалентные определения матроида, например, через
Существуют другие эквивалентные определения матроида, например, через
семейства независимых множеств, через ранговую функцию, через циклы и т.д.
семейства независимых множеств, через [[ранговая функция|ранговую функцию]], через [[цикл|циклы]] и т.д.


Понятие матроида является естественным обобщением понятия линейной
Понятие матроида является естественным обобщением понятия линейной
Строка 19: Строка 19:
теории.
теории.


См. также ''Бинарный матроид, Графический матроид, Кографический матроид, Планарный матроид''.
==См. также ==
''[[Бинарный матроид]], [[Графический матроид]], [[Кографический матроид]], [[Планарный матроид]]''.
==Литература==
==Литература==
[Лекции],  
[Лекции],  

Версия от 20:26, 23 ноября 2009

Матроид (Matroid) - комбинаторный объект, представляющий собой пару [math]\displaystyle{ (E, {\mathcal B}) }[/math], где [math]\displaystyle{ E }[/math] --- конечное непустое множество элементов матроида, а [math]\displaystyle{ {\mathcal B} }[/math] --- непустое множество его подмножеств (называемых базами), удовлетворяющее следующим двум условиям (аксиомы баз):

B1. Никакая из баз не содержится в другой базе.

B2. Если [math]\displaystyle{ B_{1} }[/math]и [math]\displaystyle{ B_{2} }[/math] --- базы, то для любого элемента [math]\displaystyle{ b \in B_{1} }[/math] существует такой элемент [math]\displaystyle{ c \in B_{2} }[/math], что [math]\displaystyle{ (B_{1} \setminus b) \cup c }[/math] --- также база.

Существуют другие эквивалентные определения матроида, например, через семейства независимых множеств, через ранговую функцию, через циклы и т.д.

Понятие матроида является естественным обобщением понятия линейной зависимости и поэтому играет важную роль в комбинаторной теории.

См. также

Бинарный матроид, Графический матроид, Кографический матроид, Планарный матроид.

Литература

[Лекции],

[Липский],

[Свами-Тхуласираман]