Комбинаторная структура, обеспечивающая применимость метода динамического программирования

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