Абстрактное отношение зависимости (стр. 9 из 9)
Возникает вопрос, в каких же случаях жадный алгоритм действительно решает поставленную задачу? На поставленный вопрос поможет ответить теорема, сформулированная и доказанная в [4, с.75-76].
Теорема 7.
Для любой функции
жадный алгоритм находит независимое множество 
с наибольшим весом, тогда и только тогда, когда 
является матроидом.Действительно, в нашем примере в задачах 1 и 2 - матроид, а в задаче 3 таковым не является, так как не выполняется аксиома М3. Если рассмотреть
, тогда 
получили противоречие с независимостью хотя бы одного из множеств.1. Ван дер Варден Б.Л. Алгебра. – М.: Наука, 1976. – 648 с.
2. Кон П. Универсальная алгебра. – М.: Мир, 1968. – 352 с.
3. Курош А. Г. Курс высшей алгебры. – СПб: Лань, 2006. – 432 с.
4. Новиков Ф. А. Дискретная математика для программистов. – Спб: Питер, 2001. – 304 с.
5. Фрид Э. Элементарное введение в абстрактную алгебру. – М.: Мир, 1974. – 260 с.