Матроид
Материал из WikiGrapp
Матроид (Matroid) —
комбинаторный объект, представляющий собой пару , где
— конечное непустое множество элементов матроида, а
— непустое множество его подмножеств (называемых базами),
удовлетворяющее следующим двум условиям (аксиомы баз):
B1. Никакая из баз не содержится в другой базе.
B2. Если и
— базы, то для любого элемента
существует такой элемент
, что
— также база.
Существуют другие эквивалентные определения матроида, например, через семейства независимых множеств, через ранговую функцию, через циклы и т.д.
Понятие матроида является естественным обобщением понятия линейной зависимости и поэтому играет важную роль в комбинаторной теории.
См. также
Литература
- Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
- Липский В. Комбинаторика для программистов. — М.: Мир, 1988.
- Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984.