
Матроид
| Категория реферата: Рефераты по математике
| Теги реферата: рефераты бесплатно скачать, наука реферат
| Добавил(а) на сайт: Амалиев.
Предыдущая страница реферата | 1 2 3 | Следующая страница реферата
Докажем, что в рассмотренном примере множество линейно независимых столбцов действительно является матроидом. Для этого достаточно доказать третье свойство из определения матроида. Проведем доказательство методом от противного. Доказательство.
Пусть Дополнительные понятия Двойственным данному матроиду называется матроид, носитель которого совпадает с носителем данного матроида, а базы — дополнения баз данного матроида до носителя. То есть X*=X, а множество баз двойственного матроида — это множество таких B*, что B*=XB, где B — база данного матроида. Циклом в матроиде называется такое множество A⊂X, что A∉I, и для любого B⊂A, если B≠A, то B∈I Рангом матроида называется мощность его баз. Ранг тривиального матроида равен нулю. Матроид Фано
Название возникло из того факта, что матроид Фано представляет собой проективную плоскость второго порядка, известная как плоскость Фано, чьё координатное поле — это двух-элементное поле. Это означает, что матроид Фано — это векторный матроид, связанный с семью ненулевыми векторами в трехмерном векторном пространстве над полем 2ух элементов. Из проективной геометрии известно, что матроид Фано непредставим произвольным множеством векторов в вещественном или комплексном векторном пространстве (или в любом векторном пространстве над полем, чьи характеристики отличаются от 2). Графовый матроид Граф
неориентированный и состоит из четырех вершин и семи ребер, одно из которых
является петлей. Пусть E будет множеством, состоящих из ребер этого графа, Теорема Пусть
G — граф, а Доказательство.
Необходимо доказать, что Теперь предположим, что X линейно зависимый. Возьмем минимальное линейно зависимое подмножество D из X (то есть такое подмножество, что удаление из него любого элемента приводит к тому, что оно будет линейно независимым). Если D будет состоять из нулевого вектора, то тогда X содержит петлю и, соответственно, цикл. Если
D не содержит нулевого вектора: так как в поле {0,1} существует единственный
ненулевой элемент — 1, то сумма векторов из D будет нулевым вектором, из-за
того, что D — минимальное линейно зависимое подмножество. Из этого следует, что
D содержит ребра из цикла, и если какой-то вершине инцидентно ребро из D, то
существует как минимум еще одно ребро, инцидентное ей. Действительно, возьмем
ребро Матроиды и комбинаторная оптимизация Матроиды имеют широкое применение в задачах, связанных с комбинаторной оптимизацией, а также с задачами, решение которых основано на жадных алгоритмах. Рассмотрим
такую задачу: у менеджера есть m однодневных работ для одного человека Пусть
A — множество подмножеств некоего множества E. К примеру, пусть
A=({1,2,4},{2,3,5,6},{5,6},{7}), при множестве E={1,2,3,4,5,6,7}. Подмножество
E — Теоремы Все базы матроида имеют одинаковую мощность. Рекомендуем скачать другие рефераты по теме: bestreferat, quality assurance design patterns системный анализ. Категории:Предыдущая страница реферата | 1 2 3 | Следующая страница реферата Поделитесь этой записью или добавьте в закладки |