Матроид
- гиперграф специального вида. М. Определяется заданием множества 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. А. А. Сапоженко..
Дополнительный поиск Матроид
На нашем сайте Вы найдете значение "Матроид" в словаре Математическая энциклопедия, подробное описание, примеры использования, словосочетания с выражением Матроид, различные варианты толкований, скрытый смысл.
Первая буква "М". Общая длина 7 символа