Cтраница 1
Помечивание двух вершин графа: для одной КЭ обязательно попадает в тело сползания, для другой КЭ обязательно окажется вне тела сползания. [1]
Помечивание связанных компонентов в области объекта требует четкого определения связанности для представления в виде 4-дерева. [2]
Любая состоятельная процедура помечивания приводит к максимальному потоку за полиномиальное число шагов. [3]
Прежде всего укажем, что это правило удовлетворяет ранее изложенным условиям для допустимого помечивания множества точек S, если оно конечно и содержит все вершины S. Это же неравенство и высказанные выше утверждения о зависимости между положительными координатами точки и вершин ее носителя гарантируют выполнение и других условий допустимого помечивания. [4]
Алгоритм 2.2 может быть реализован с использованием очереди заданий, готовых к помечиванию, и списка LEX, который упорядочивает остальные задания по отношению к меткам, которые уже были приписаны. Пусть LEX; представляет собой список после того, как метка I приписана. Мы не заботились специально о тех предшественниках х, которых не было в LEX, и не говорили ничего о заданиях, готовых к помечиванию. [5]
Для того чтобы выявить такое задание, сравним множества непосредственных преемников заданий, готовых к помечиванию. Для каждого задания построим убывающую последовательность, используя метки его непосредственных преемников. [6]
Для того чтобы доказать теорему Брауэра о неподвижной точке, используя лемму Шпернера, мы должны указать систематический способ помечивания точек подразделения. Это может быть сделано геометрически, но это же можно сделать более просто и компактно в терминах координат. [7]
Брауэра о неподвижной точке: ни одна вершина выделенной грани симплекса S, не отображается в выделенную вершину. Таким образом помечивание описывает отображение вершин подразделения выделенной грани в вершины этой же выделенной грани. Обозначим эту грань через Sr 1 и отображение через fk-l. Этот индекс, однако, равен индексу К отображения - симплекса в себя и по фундаментальной теореме об индексе для любого такого отображения L K. Таким образом, мы показали, что если это предположение справедливо для размерности k - 1, то оно справедливо для размерности k, и индукция полностью проведена. [8]
Для алгоритма 2.1 удобно представлять данные в виде списка непосредственных предшественников каждой вершины. В дополнение к нему нужно иметь очередь Q заданий, готовых к помечиванию. Алгоритм состоит из следующих шагов. [9]
Прежде всего укажем, что это правило удовлетворяет ранее изложенным условиям для допустимого помечивания множества точек S, если оно конечно и содержит все вершины S. Это же неравенство и высказанные выше утверждения о зависимости между положительными координатами точки и вершин ее носителя гарантируют выполнение и других условий допустимого помечивания. [10]
Так как сумма барицентрических координат точки равна 1, то отсюда следует, что как только точка покидает ее носитель, то ее барицентрические координаты, прежде отличные от нуля, должны, вообще говоря, уменьшиться в то время как одна или более ее прежде нулевых координат становятся положительными. Мы должны отнестись к последнему из этих обстоятельств несколько более внимательно. Прежде, однако, изложим правило помечивания, связанное с отображением га-симплекса с барицентрическими координатами в себя. [11]
Алгоритм 2.2 может быть реализован с использованием очереди заданий, готовых к помечиванию, и списка LEX, который упорядочивает остальные задания по отношению к меткам, которые уже были приписаны. Пусть LEX; представляет собой список после того, как метка I приписана. Мы не заботились специально о тех предшественниках х, которых не было в LEX, и не говорили ничего о заданиях, готовых к помечиванию. [12]
Система AGE содержит удобный интерфейс, а также средства для пометки значений и записи хода работы системы. Интерфейс помогает пользователю проектировать и определять систему. Метки позволяют пользователю устанавливать временные или другие маркеры у значений, добавляемых к структуре гипотез. Помечивание и записывание истории работы были особенно полезны в модели AGE для генерации отчетов об утечках и для согласованности с затрагивающими временной фактор законодательными актами. [13]
Оказывается, дело здесь в том, что в следующих друг за другом итерациях помеченные вершины включались нами в множество просмотренных с использованием разных правил. Назовем процедуру помечивания состоятельной, если всякий раз, когда имеется некоторое множество помеченных, но не просмотренных вершин, выбор вершин для отнесения их к множеству просмотренных осуществляется по одному и тому же правилу. Таккер ( 1977) доказал, что если состоятельная процедура помечивания применяется вместе с потоковым алгоритмом Форда - Фалкерсона, то алгоритм завершает работу и приводит к максимальному потоку. Фалкерсоном сформулирована ( но не опубликована) следующая гипотеза. [14]
Из каждого подразделения выберем один симплекс, несущий все пометки, и в этом симплексе выберем единственную точку. Эта точка, очевидно, является предельной точкой последовательностей всех вершин всех симплексов, из которых только что выбраны точки сходящейся подпоследовательности. Так как в соответствии с нашим правилом помечивания для одной из этих вершин выполняется qj Cpj для каждого / и так как такие неравенства, очевидно, сохраняются в пределе, то справедливо, что не существует барицентрической координаты образа предельной точки выбранной подпоследовательности, превышающей барицентрическую координату самой предельной точки. Следовательно, поскольку барицентрические координаты должны быть в сумме равны I, то барицентрические координаты образа предельной точки должны быть в точности такие же, как барицентрические координаты самой предельной точки, и так как координаты в ( я 1) - мерном пространстве совпадают, то должны совпадать сами точки. [15]