Матроид | это... Что такое Матроид? (original) (raw)
Матроид — классификация подмножеств некоторого множества, представляющая собой обобщение идеи независимости элементов, аналогично независимости элементов линейного пространства, на произвольное множество.
Содержание
- 1 Аксиоматическое определение
- 2 Определение в терминах циклов
- 3 Определение в терминах правильного замыкания
- 4 Примеры
- 5 Дополнительные понятия
- 6 Матроид Фано
- 7 Теоремы
- 8 Применение
- 9 Литература
- 10 Ссылки и примечания
Аксиоматическое определение
Матроид — пара , где — конечное множество, называемое носителем матроида, а — некоторое множество подмножеств , называемое семейством независимых множеств , то есть . При этом должны выполняться следующие условия:
Базами матроида называются максимальные по включению независимые множества. Подмножества не принадлежащие называются зависимыми множествами. Минимальные по включению зависимые множества называются циклами матроида, это понятие используется в альтернативном определении матроида.
Определение в терминах циклов
Матроид — пара , где — носитель матроида, а — семейство непустых подмножеств , называемое множеством циклов матроида, для которых выполняются следующие условия:[1]
- Ни один цикл не является подмножеством другого
- Если , то содержит цикл
Определение в терминах правильного замыкания
Пусть — частично упорядоченное множество. — замыкание в , если
- Для любого x из P :
- Для любых x, y из P :
- Для любого x из P :
Рассмотрим случай, когда частично упорядоченное множество — булева алгебра. Пусть — замыкание .
- Замыкание правильно (аксиома правильного замыкания), если
- для любого существует такое , что
Пара , где — правильное замыкание на , называется матроидом.
Примеры
- Универсальный матроид Un k. Множество X имеет мощность n, независимыми множествами являются подмножества мощностью не больше k. Базы — подмножества мощностью k.
- Матроид циклов графа. Множество X — множество ребер графа, независимые множества — ациклические подмножества этих ребер, циклы — простые циклы графа. Базами являются остовные леса графа. Матроид называется графическим, если он является матроидом циклов некоторого графа.[2]
- Матроид подмножеств множества ребер графа, таких что удаление подмножества оставляет граф связным.
- Матроид коциклов графа. Множество X — множество ребер, коциклы — минимальные множества, удаление которых приводит к потере связности графа. Матроид называется кографическим, если он является матроидом коциклов некоторого графа.[2]
- Матричный матроид. Семейство всех линейно независимых подмножеств любого конечного множества векторов произвольного непустого векторного пространства является матроидом.
Определим множество E, как множество состоящее из {1, 2, 3, .., n} — номеров столбцов некоторой матрицы, а множество I, как множество состоящее из подмножеств E, таких, что векторы, определяемые ими, являются линейно независимыми над полем вещественных чисел R. Зададимся вопросом — какими свойствами обладает построенное множество I?
- Множество I непусто. Даже если исходное множество E было пусто — E = ∅, то I будет состоять из одного элемента — множества, содержащего пустое. I = { {∅} }.
- Любое подмножество любого элемента множества I также будет элементом этого множества. Это свойство понятно — если некоторый набор векторов линейно независим над полем, то линейно независимым будет также любой его поднабор.
- Если A, B ∈ I, причем |A| = |B| + 1, тогда существует элемент x ∈ A − B , такой что B ∪ {x} ∈ I.
Докажем, что в рассмотренном примере множество линейно независимых столбцов действительно является матроидом. Для этого достаточно доказать третье свойство из определения матроида. Проведем доказательство методом от противного.
Доказательство. Пусть A, B ∈ I и |A| = |B| + 1. Пусть W будет пространством векторов, охватываемым A ∪ B . Понятно, что его размерность будет не менее |A|. Предположим, что B ∪ {x} будет линейно зависимо для всех x ∈ A − B (то есть третье свойство не будет выполняться). Тогда B образует базис в пространстве W. Из этого следует, что |A| ≤ dim W ≤ |B|. Но так как по условию A и B состоят из линейно независимых векторов и |A| > |B|, получаем противоречие. Такое множество векторов будет являться матроидом.
Дополнительные понятия
- Двойственным данному матроиду называется матроид, носитель которого совпадает с носителем данного матроида, а базы — дополнения баз данного матроида до носителя. То есть X*=X, а множество баз двойственного матроида — это множество таких B*, что B*=X\B, где B — база данного матроида.
- Циклом в матроиде называется такое множество A⊂X, что A∉I, и для любого B⊂A, если B≠A, то B∈I
- Рангом матроида называется мощность его баз. Ранг тривиального матроида равен нулю.
Матроид Фано
Матроид Фано
Матроиды с маленьким числом элементов часто изображают в виде диаграмм. Точки — это элементы основного множества, а кривые «протянуты» через каждую трёхэлементную цепь (3-element circuit). Диаграмма показывает 3-ранговый матроид, называемый матроидом Фано, пример, который появился в 1935 в статье Уитни (Whitney).
Название возникло из того факта, что матроид Фано представляет собой проективную плоскость второго порядка, известная как плоскость Фано, чьё координатное поле — это двух-элементное поле. Это означает, что матроид Фано — это векторный матроид, связанный с семью ненулевыми векторами в трехмерном векторном пространстве над полем двух элементов.
Из проективной геометрии известно, что матроид Фано непредставим произвольным множеством векторов в вещественном или комплексном векторном пространстве (или в любом векторном пространстве над полем, чьи характеристики отличаются от 2).
Теоремы
Применение
- Матроиды хорошо описывают класс задач, допускающих «жадное» решение. См. жадный алгоритм Радо — Эдмондса
- Матроиды в комбинаторной оптимизации
Литература
- Асанов М.О. и др. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001. — С. 288.
- Ф. Харари Теория графов. — Москва: УРСС, 2003. — С. 300. ISBN 5-354-00301-6
Ссылки и примечания
http://rain.ifmo.ru/cat/view.php/theory/unsorted/matroids-2004/