Матроид

Матроид (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.