Определение матроида. Матроид $M=(E,\mathcal{I})$ — это конечное множетсво $E$ и система «независимых» подмножеств $\mathcal{I}\subseteq 2^E$, удовлетворяющая трём аксиомам:
$$\begin{array}{rl}& (\text{I1})\varnothing \in \mathcal{I};\\ & (\text{I2})\text{если}I\in \mathcal{I}\text{и}J\subseteq I,\text{то}J\in \mathcal{I}(\text{наследственность});\\ & (\text{I3})\text{если}I,J\in \mathcal{I}\text{и}|I|>|J|,\text{то}\exists e\in I\setminus J:J\cup \{e\}\in \mathcal{I}(\text{обменное свойство}).\end{array}$$
Формулировка задачи и жадный алгоритм. Пусть задана весовая функция $w:E\to \mathbb{R}$. Цель — найти базис (максимальное по включению независимое множество) максимального суммарного веса. Жадный алгоритм:
1. Упорядочить элементы так, чтобы $w(e_1)\ge w(e_2)\ge \cdots$.
2. Проходя в этом порядке, добавить текущий элемент в текущее множество $G$, если $G\cup \{e_i\}\in \mathcal{I}$.
3. В конце вернуть $G$ (это базис).
Доказательство корректности (идея и формальное доказательство). Пусть жадный алгоритм вернул $G=\{g_1,\dots ,g_r\}$ в порядке выбора, и пусть $B$ — любой базис (|B|=r) максимального суммарного веса. Покажем, что $w(G)\ge w(B)$.
Определим последовательность базисов $B_0=B,B_1,\dots ,B_r$ так: для $k=1,\dots ,r$ если $g_k\in B_{k-1}$, то $B_k=B_{k-1}$; иначе по обменному свойству (I3) применительно к независимым множствам $\{g_1,\dots ,g_k\}$ и $B_{k-1}$ существует элемент $b\in B_{k-1}\setminus \{g_1,\dots ,g_{k-1}\}$ такой, что
$$B_k=B_{k-1}-\{b\}+\{g_k\}\in \mathcal{I}.$$ Поскольку жадность выбирала $g_k$ раньше, чем любой невключённый в текущий $G$ элемент (в том числе $b$), выполняется $w(g_k)\ge w(b)$. Тогда
$$w(B_k)=w(B_{k-1})-w(b)+w(g_k)\ge w(B_{k-1}).$$ Итеративно получаем $w(B_r)\ge w(B_0)=w(B)$. Но по построению в конце $B_r$ содержит все $g_1,\dots ,g_r$, а так как размеры равны, получаем $B_r=G$. Значит $w(G)\ge w(B)$. Поскольку $B$ был произвольным максимальным базисом, $G$ — оптимален.
Два примера матроидов.
1) Графический матроид. Для неориентированного графа $G=(V,E)$ положим $\mathcal{I}$ — множество всех ациклических подмножеств рёбер (т.е. лесов). Тогда базисы — это максимальные леса (в связном графе — остовные деревья). Жадный алгоритм с сортировкой по неповышающим весам — это алгоритм Краскала для максимального остова (или минимального при обратном порядке).
2) Векторный (линейный) матроид. Пусть $E$ — конечное множество векторов в векторном пространстве, а $\mathcal{I}$ — все линейно независимые подмножества. Базисы — линейные базы. Жадный выбор по весу даёт базис максимального суммарного веса.
Почему жадный метод может дать неверный результат вне класса матроидов. Ключевой шаг в доказательстве — обменное свойство (I3). Если система независимости его не удовлетворяет, нельзя гарантировать, что любой выбранный жадно элемент можно заменить в оптимальном решении элементом не меньшего веса. Контрпример: $E=\{a,b,c\}$, веса $w(a)=5,w(b)=4,w(c)=3$. Пусть $\mathcal{I}=\{\varnothing ,\{a\},\{b\},\{c\},\{b,c\}\}$ (разрешены все одиночки и только пара $\{b,c\}$). Жадный алгоритм возьмёт сначала $a$ (вес 5) и затем не сможет добавить ни $b$ ни $c$ (пары с $a$ не независимы), получив вес 5. Но оптимум — $\{b,c\}$ с весом $7$. Здесь нарушено обменное свойство, поэтому жадность провалила.
Вывод: обменное свойство матроидов — необходимое условие, обеспечивающее монотонность суммарного веса при замене элементов и потому корректность жадного алгоритма; вне матроидов такого общего гаранта нет.