Матроид

- гиперграф специального вида. М. определяется заданием множества Vэлементов и семейства [img: http://localhost:8080/file/031408-356.jpg] подмножеств множества У, называемых независимыми множествами, для к-рых выполняются следующие аксиомы: 1) пустое множество независимо; 2) каждое подмножество независимого множества независимо; 3) для всякого подмножества [img: http://localhost:8080/file/031408-357.jpg] все независимые множества М., содержащиеся в A и являющиеся максимальными по включению относительно А, имеют одинаковое число элементов. Примеры. 1) Множество Vстрок произвольной прямоугольной матрицы и семейство [img: http://localhost:8080/file/031408-358.jpg] всех подмножеств множества V, составленных из линейно независимых строк, образуют М. 2) Пусть [img: http://localhost:8080/file/031408-359.jpg] - множество всех остовных лесов (см. Дерево)графа G,a R(Li).- множество ребер леса Li, i=l, 2,.... Тогда множество ребер Vграфа Gи семейство [img: http://localhost:8080/file/031408-360.jpg] = [img: http://localhost:8080/file/031408-361.jpg] образуют М. 3) Пусть G- граф двудольный с долями [img: http://localhost:8080/file/031408-362.jpg]. Подмножество [img: http://localhost:8080/file/031408-363.jpg] вершин, для к-рого существует паросочетание Рграфа Gтакое, что каждая вершина [img: http://localhost:8080/file/031408-364.jpg] инцидентна нек-рому ребру паросочетания Р, наз. трансверсалью. Множество Vи множество всех трансверсалей графа Gобразуют т. н. трансверсальный матроид. М. можно задать также множеством V элементов и семейством [img: http://localhost:8080/file/031408-365.jpg] непустых подмножеств [img: http://localhost:8080/file/031408-366.jpg], называемых циклами и удовлетворяющих следующим аксиомам: никакое собственное подмножество цикла не является циклом; если [img: http://localhost:8080/file/031408-367.jpg], то [img: http://localhost:8080/file/031408-368.jpg] содержит цикл. Независимыми множествами этого М. являются подмножества [img: http://localhost:8080/file/031408-369.jpg] не содержащие циклов. Если G - граф, то множество его ребер и семейство простых циклов образуют т. н. циклический матроид. Если в качестве циклов М. взять коциклы (разрезы, см. Графа связность)графа G, то полученный таким образом М. наз. коциклическим. М. двух последних типов наз. графическими. Понятие "М." используется в теории графов и комбинаторике при доказательстве нек-рых утверждений о покрытиях и упаковках, паросочетаниях.