Cтраница 2
Для практических применений указанных решеток необходимы также алгоритмы для пометки точек решетки. Необходимы эффективные кодирующие алгоритмы, переводящие i ( l i M) в с - и обратно. Первая из этих проблем может быть решена с помощью описанных в этой главе алгоритмов, а вторая ( см. [ Con 35 ]) - с использованием двойственного базиса решетки. [16]
Однако ( 17) включает пропускные способности по всем разрезам между этими парами узлов, так что неравенств все же остается много. Конечно, для данного ( i, j) еГ, если минимальный разрез удовлетворяет ( 17), то все сделано, так как для любого множества дуг должны быть проверены только п - 1 ограничений. Однако то, какую п - 1 пару надо рассматривать, изменяется при изменении пропускных способностей. Для того чтобы увидеть, какие из различных подмножеств ограничений могут быть выбраны эффективно, напишем двойственную задачу, в которой выбор ограничений или строк, вводимых в исходной задаче, становится выбором столбцов, вводимых в двойственный базис. [17]