Матроид

Гиперграф специального вида. М. определяется заданием множества Vэлементов и семейства подмножеств множества У, называемых независимыми множествами, для к-рых выполняются следующие аксиомы: 1) пустое множество независимо; 2) каждое подмножество независимого множества независимо; 3) для всякого подмножества все независимые множества М., содержащиеся в A и являющиеся максимальными по включению относительно А, имеют одинаковое число элементов. Примеры. 1) Множество Vстрок произвольной прямоугольной матрицы и семейство всех подмножеств множества V, составленных из линейно независимых строк, образуют М. 2) Пусть — множество всех остовных лесов (см. Дерево )графа G,a R(Li).- множество ребер леса Li, i=l, 2, .... Тогда множество ребер Vграфа Gи семейство =образуют М. 3) Пусть G- граф двудольный с долями . Подмножество вершин, для к-рого существует паросочетание Рграфа Gтакое, что каждая вершина инцидентна нек-рому ребру паросочетания Р, наз. трансверсалью. Множество Vи множество всех трансверсалей графа Gобразуют т. н. трансверсальный матроид. М. можно задать также множеством V элементов и семейством непустых подмножеств , называемых циклами и удовлетворяющих следующим аксиомам: никакое собственное подмножество цикла не является циклом; если , то содержит цикл. Независимыми множествами этого М. являются подмножества не содержащие циклов. Если G — граф, то множество его ребер и семейство простых циклов образуют т. н. циклический матроид. Если в качестве циклов М. взять коциклы (разрезы, см. Графа связность )графа G, то полученный таким образом М. наз. коциклическим. М. двух последних типов наз. графическими. Понятие "М." используется в теории графов и комбинаторике при доказательстве нек-рых утверждений о покрытиях и упаковках, паросочетаниях. Лит.:[1] Whitney H., "Amer. J. Math.", 1935, v. 57, p. 509-33; [2] Tutte W. Т., "J. Res. Nat. Bur. Standards. Sec. B", 1965, v. 69, №1-2, p. 1-47; [3] Xapapи Ф., Теория графов, пер. с англ., М., 1973. А. А. Сапоженко.