Матроид

100

- гиперграф специального вида. М. Определяется заданием множества 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. А. А. Сапоженко..

Значения в других словарях
Матричной Факторизации Метод

метод матричной прогонки,- метод решения конечноразностных систем, аппроксимирующих краевые задачи для систем обыкновенных дифференциальных уравнений в одномерных задачах и для уравнений эллиптич. Типа в двумерных задачах. Решение трехточечной разностной схемы где - искомая сеточная вектор-функция, Fi- вектор правой части, - заданные квадратные матрицы, при краевых условиях ищется так же, как в скалярном случае, в виде Прогоночные коэффициенты, матрица и вектор определяются рекуррентным..

Матричный Метод Суммирования

- один из методов суммирования ряда и последовательности с помощью бесконечной матрицы. Посредством бесконечной матрицы данная последовательность {sn} преобразуется в последосательность Если ряд справа сходится для всех n=1, 2, . И последовательность имеет предел s при . то последовательность наз. Суммируемой методом, определенным матрицей , или просто суммируемой матрицей , а число s - ее пределом в смысле этого метода суммирования. Если {sn} рассматривается как последовательность части..

Матье Группа

- конечная группа, изоморфная одной из пяти групп, открытых Э. Матьё [1]. Серия М. Г. Состоит из групп, обозначаемых они представимы как группы подстановок на множествах из 11,12, 22, 23, 24 элементов соответственно. Группы М 12 и M24 являются пятикратно транзитивными. M11 реализуется естественным образом как стабилизатор в М 12 элемента множества, на к-ром действует М 12, М 23 - как стабилизатор элемента в M24 , М 22- как стабилизатор элемента в М 23. Порядки М. Г. Равны соответствен..

Матьё Уравнение

- обыкновенное линейное дифференциальное уравнение с действительными коэффициентами. Введено Э. Матьё [1] при исследовании колебаний эллиптич. Мембраны. Частный случай Хилла уравнения. Фундаментальная система решений М. У. Имеет вид при , п- целое, где есть -периодическая функция, а Ляпунова характеристический показательa. Либо действительный, либо чисто мнимый. При одно из решений неограниченно возрастает, а другое стремится к нулю для (зоны неустойчивости на плоскости ab параметров..

Дополнительный поиск Матроид Матроид

Добавить комментарий
Комментарии
Комментариев пока нет

На нашем сайте Вы найдете значение "Матроид" в словаре Математическая энциклопедия, подробное описание, примеры использования, словосочетания с выражением Матроид, различные варианты толкований, скрытый смысл.

Первая буква "М". Общая длина 7 символа