Матроид

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

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

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

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

См. также

Литература

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