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