Отрицательные циклы во взвешенных орграфах: различия между версиями

Нахождение отрицательных циклов в орграфах представляет собой фундаментальную задачу комбинаторной и сетевой оптимизации, охватывающую широкий спектр приложений, включая следующие: нахождение кратчайшего пути, элементов двумерной упаковки, потоков минимальной стоимости, минимального соотношения стоимости и времени, а также верификация модели, создание компиляторов, разработка программного обеспечения, проектирование СБИС, планирование, производство интегральных схем, программирование с учетом ограничений и обработка изображений. Скажем, изоляция циклов отрицательной обратной связи исключительно важна при проектировании СБИС. Оказывается, такие циклы соответствуют циклам с отрицательной стоимостью в так называемом «графе коэффициентов усиления» схемы. В процессе программирования с учетом ограничений необходимо проверять применимость множеств ограничений. Системы разностных ограничений могут быть представлены в виде графов ограничений, и можно показать, что такая система является применимой в том и только том случае, если в соответствующем графе ограничений не имеется циклов с отрицательной стоимостью. В планировании с нулевым уровнем предварительных знаний задача определения того факта, существует ли для данной системы достоверный план, может быть сведена к нахождению отрицательных циклов в соответствующим образом определенном графе. Дополнительную информацию об этом и других вариантах применения можно найти в [1, 12, 14].