Матроид (стр. 2 из 2)

Теперь предположим, что X линейно зависимый. Возьмем минимальное линейно зависимое подмножество D из X (то есть такое подмножество, что удаление из него любого элемента приводит к тому, что оно будет линейно независимым). Если D будет состоять из нулевого вектора, то тогда X содержит петлю и, соответственно, цикл.

Если D не содержит нулевого вектора: так как в поле {0,1} существует единственный ненулевой элемент — 1, то сумма векторов из D будет нулевым вектором, из-за того, что D — минимальное линейно зависимое подмножество. Из этого следует, что D содержит ребра из цикла, и если какой-то вершине инцидентно ребро из D, то существует как минимум еще одно ребро, инцидентное ей. Действительно, возьмем ребро

и пусть вершины и соответствуют этому ребру. Пусть вершине инцидентно еще какое-то ребро . Пусть вершина будет другим концом ребра . Продолжим этот процесс. В результате будут получены две последовательности — и . Так как количество вершин в D конечно, то какая-то из вершин v должна повториться. Когда это произойдет, то в D будет найден цикл. Соответственно цикл будет найден и в X.

Матроиды и комбинаторная оптимизация

Матроиды имеют широкое применение в задачах, связанных с комбинаторной оптимизацией, а также с задачами, решение которых основано на жадных алгоритмах.

Рассмотрим такую задачу: у менеджера есть m однодневных работ для одного человека

. Также он располагает n рабочими, каждый из которых умеет выполнять какой-то поднабор работ. Менеджер хочет знать, какое максимальное количество работ способны выполнить его рабочие за один день. Как позже выяснится, это будет рангом некоего матроида.

Пусть A — множество подмножеств некоего множества E. К примеру, пусть A=({1,2,4},{2,3,5,6},{5,6},{7}), при множестве E={1,2,3,4,5,6,7}. Подмножество E —

называется частичным трансверсалем A, если есть взаимооднозначное соответствие Ф между {1,2,…,k} и {1,2,…,m}, причем для любых i. Если m = k, то такой частичный трансверсаль называется трансверсалем. Если взять множество {2,3,6,7}, то оно будет трансверсалем для A, как это видно из рисунка слева.

Теоремы

Все базы матроида имеют одинаковую мощность.

Матроид однозначно задается носителем и базами.

Цикл не может быть подмножеством другого цикла.

Если

и — циклы, то для любого содержит цикл

Если B — база и x∉B, то B∪{x} содержит ровно один цикл.

Список литературы

1. Асанов М.О. и др. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001. — С. 288.

2. Ковалев М.М. Матроиды в дискретной оптимизации. Изд.2, 2003. 224 с. 142 руб.