double arrow

Матроиды


Существование базиса в любом векторном пространстве принимается за аксиому. Практически важной задачей является выбор базиса E из некоторого множества векторов.

Алгоритм построения базиса. Пусть дано некоторое конечное множество векторов .

Выберем (произвольно) элемент v1 из Е. Положим v1ÎE. Выберем (опять произвольно) ещё один элемент из . Проверим его на линейную независимость с v1. Если вектора независимы, добавим v2 в E. Если вектора зависимы, выбросим v2 из Е и найдём следующий и опять проверим на независимость. Если независим, то добавим его в E. Через конечное число шагов процедура закончится. На выходе получается система вложенных множеств линейно независимых векторов из Е: . – Некоторая система подмножеств Е.

Результат зависит от правила (алгоритма) выбора векторов из Е.

Матроидом называется конечное множество Е, |E|=n и семейство его подмножеств таких, что:

М1: (матроид не пуст);

М2: ;

М3: .

Примеры.

1. Семейства линейно независимых векторов – матричный матроид.

2. М= <E,2E> – свободный матроид.

3. Матроид разбиений.

4. Матроид трансверсалей.

5. Матроид замыканий.

Циклы. Альтернативная система аксиом.




Эффективность матроидов.








Сейчас читают про: