Матроиды и трансверсали

 

§ 16. Азбука теории матроидов

 

§ 17. Двойственный матроид

 

§ 18. Примеры матроидов

 

§ 19. Изоморфизм матроидов

 

§ 20. Представление матроида

 

Высота M

 

§ 21. Бинарные матроиды

 

§ 22. Трансверсали

 

§ 23. Жадный алгоритм

 

§ 24. Объединение и пересечение матроидов

 

УПРАЖНЕНИЯ

 

 — матроид, появляющийся в результате обобщения хорошо известного читателю понятия линейной зависимости. Хотя понятие «матроид» возникло относительно давно,— в 30-е годы нашего столетия (впервые это понятие ввел Уитни) — место теории матроидов в математике и, тем более, в математическом образовании первоначально не было осознано. Теперь же, когда открываются все новые и новые классы матроидов, объединяющая роль идеи матроида, позволяющая с возрастающим успехом применять к решению комбинаторных проблем методы алгебры, становится все более ясной.

Для нас матроиды интересны, прежде всего, по двум причинам. Первая — их связь с теорией графов. Фактически, именно соответствие между некоторыми теоретико-графовыми и алгебраическими понятиями привело к созданию теории матроидов. Вторая причина состоит в том, что задачи оптимизации на матроидных структурах решаются с помощью простого, так называемого «жадного» алгоритма, который является обобщением алгоритма Краскала для нахождения остовного дерева минимального веса в связном взвешенном графе (§ 15). «Жадный» алгоритм изучается в этой главе.