Cтраница 2
Все фиктивные дуги построенного графа можно разделить на два класса - фиктивные дуги, соединяющие вход в вершину и выход из вершины исходного графа, и фиктивные дуги, описывающие ненепосредственные предшествования. Дуги второго типа по самому своему происхождению имеют обходные пути. Дуги первого типа ( после того как исключены все дуги, второго типа) исключаются по второму правилу, так как после этого из каждой вершины выходит не более одной фиктивной дуги. [16]
Далее начинается редукция графа, которая приводит к графу, изображенному на рис 44 Фиктивные дуги изображены на этих двух графах штриховыми линиями. В реальных задачах фиктивных дут обычно оказывается значительно меньше. [17]
Когда определен некоторый поток в сети, величина f ( u, v) может трактоваться как кратность соответствующей дуги, а с учетом фиктивной дуги законы сохранения превращают сеть в эйлеров мультиграф. Соответствующий эйлеров контур можно найти, проходя из s в t по некоторому маршруту, разрушая пройденные мосты. [18]
Все фиктивные дуги построенного графа можно разделить на два класса - фиктивные дуги, соединяющие вход в вершину и выход из вершины исходного графа, и фиктивные дуги, описывающие ненепосредственные предшествования. Дуги второго типа по самому своему происхождению имеют обходные пути. Дуги первого типа ( после того как исключены все дуги, второго типа) исключаются по второму правилу, так как после этого из каждой вершины выходит не более одной фиктивной дуги. [19]
В случае, когда в сети появляется дефицит подачи ( резерв пропускной способности не достаточен для компенсации ограничений) для получения полной картины, распределения потоков необходимо добавить фиктивную дугу, соединяющую источник и сток с пропускной способностью, равной размеру дефицита. [20]
Следовательно, каждому моменту времени t е [ О, Г ] соответствует своя подмодель, изображенная на рис. 8.7. Все такие статические подмодели связаны друг с другом фиктивными дугами через уз-лы - запасы, которые описаны далее, а на рис. 8.10 дана общая конструкция модели, которую можно представить в виде многослойной сети с кратными дугами. [21]
Условия (8.2) следуют из предположения, что поток не исчезает в процессе транспортировки, поэтому условия (8.2) называются условиями сохранения потока. Добавление фиктивной дуги из стока в источник позволяет нам написать условия сохранения потока для всех вершин ( включая источник и сток) в единообразной форме. [22]
Путем решения этой вспомогательной зада-чи, для которой допустимое базисное множество имеется, получим некоторое базисное множество, которое является в ней одновременно допустимым и двойственно допустимым. Если это множество не содержит фиктивных дуг, то оно может быть принято в качестве исходного допустимого базисного множества для исходной задачи. В противном случае в исходной задаче допустимых базисных множеств не существует. [23]
Дуга типа POP - это фиктивная дуга, указывающая, при каких условиях состояние следует рассматривать как заключительное, и определяющая форму, которая должна быть выдана как результат вычислений, если выбрана альтернатива POP. Одно из преимуществ представления этой информации как фиктивной дуги состоит в возможности упорядочить подъем по отношению к другим дугам, выходящим из того же состояния. [24]
Фиктивные дуги служат для установления обязательных предшествований между вершинами графа. Если это предшествование является следствием других предшествований, фиктивная дуга не нужна. [25]
Вершина 1 называется источником, поскольку поток только вытекает из данной вершины. Вершина 5 называется стоком, поскольку поток только втекает в данную вершину. Мы также добавляем некоторую фиктивную дугу из стока в источник с неограниченной пропускной способностью. [26]
Все фиктивные дуги построенного графа можно разделить на два класса - фиктивные дуги, соединяющие вход в вершину и выход из вершины исходного графа, и фиктивные дуги, описывающие ненепосредственные предшествования. Дуги второго типа по самому своему происхождению имеют обходные пути. Дуги первого типа ( после того как исключены все дуги, второго типа) исключаются по второму правилу, так как после этого из каждой вершины выходит не более одной фиктивной дуги. [27]
Доказательство этой теоремы легко может быть получено из теории двойственности. Задача о максимальном потоке может быть сформулирована как задача об оптимальном потоке. В исходном графе вводится фиктивная дуга ( s, t), обладающая неограниченной пропускной способностью. [28]
На рис. 3.13, а показана сетка произвольной конфигурации. Затем условно выравниваем дуги этой сетки и получаем сетку, изображенную на рис. 3.14, а сплошными линиями. Дополняя недостающие дуги ( они показаны пунктиром), получаем сетку прямоугольной формы с диагоналями. Причем на всех дополнительных дугах и узлах ( узлы на рис. 3.14 обозначены кружочками) запрещается прокладка трубопровода. Поэтому никакой дополнительной работы по съемке данных с карт введения фиктивных дуг не требует. Сформированная таким образом сетка представляет совокупность вертикальных полос. На рис. 3.14, б изображена первая полоса сетки. Как видно из рисунка, в пределах данной полосы только дуги 4, 5, в - действительные; остальные фиктивные. Соответственно снятие информации с карт проводится только по этим дугам, а остальные обозначаются символом запрещение по классификационной таблице. [29]