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

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


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


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


Существуют другие эквивалентные определения матроида, например, через
Существуют другие эквивалентные определения матроида, например, через
Строка 20: Строка 20:


==См. также ==
==См. также ==
''[[Бинарный матроид]], [[Графический матроид]], [[Кографический матроид]], [[Планарный матроид]]''.
* ''[[Бинарный матроид]],''
* ''[[Графический матроид]],''
* ''[[Кографический матроид]],''
* ''[[Планарный матроид]].''
==Литература==
==Литература==
[Лекции],  
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
 
[Липский],
* Липский В. Комбинаторика для программистов. —  М.: Мир, 1988.
 
 
[Свами-Тхуласираман]
* Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.

Текущая версия от 12:47, 11 мая 2011

Матроид (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] — также база.

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

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

См. также

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
  • Липский В. Комбинаторика для программистов. — М.: Мир, 1988.
  • Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.