Cтраница 2
Иначе говоря, пусть D есть ориентированный граф, с: E ( G) - R является функцией пропускной способности, a s и t - выделенные вершины, называемые источником и стоком соответственно. Для каждого подмножества X С V ( G) - s - t пусть f ( X) с ( Х U s) обозначает пропускную способность ( s, 1) - разреза, определяемого подмножеством XUs. Тогда / есть субмодулярная функция множеста, и проблема минимизации функции / эквивалентна отысканию наименьшего ( s, ) - разреза. [16]
К сожалению, этот подход к минимизации субмодулярной функции непрактичен, поскольку в нем используется метод эллипсоидов. Другой недостаток состоит в том, что он не дает какого-либо комбинаторного проникновения в структуру субмодулярных функций множеств. Поиск алгоритма минимизации субмодулярной функции множества, основанного на комбинаторных идеях, является важной открытой проблемой. [17]
Какое все это имеет отношение к алгоритмам о паросочетаниях. Мы видели в разд. Эта задача, в свою очередь, может быть сведена к минимизации без ограничений субмодулярной функции множества с применением алгоритма, аналогичного жадному алгоритму. [18]