Исходная вершина

Cтраница 3

Какая-либо вершина, например Z, выбирается исходной. Затем делается переход к графу, в котором исходная вершина Z преобразуется к стоку. [31]

Любая вершина блока обратной связи может быть разделена на две вершины, одна из которых инцидентна только исходящим дугам исходной вершины, а другая - входящим дугам. При этом все дуги обратных связей, инцидентные исходной вершине, становятся каскадными дугами новой сети. [32]

Ст, на с переводит вершину х графа на один шаг по ребру, исходящему из х, а умножение на с1 отвечает переходу на / таких шагов. Очевидно, переход на / шагов от вершины петли возвращает нас в исходную вершину тогда и только тогда, когда петля проходится конечное число раз. [33]

Если для всех вершин найти кратчайшее расстояние Li L0 от какой-либо одной вершины, а потом ко всем расстояниям прибавить ог-0, то полученные величины называются потенциалами. Кратчайшие расстояния - система потенциалов с u o 0, Vi0 - всегда равно потенциалу исходной вершины LJO VJ - vio. Можно доказать следующее: если по дуге ( i, /) проходит кратчайший путь до вершины, то Vj - t) - C j, если нет, то Vj - - Vi. [34]

Все вместе спектры гомологических рядов образуют типичные распределения полос обсуждавшегося выше типа. Брауном и Шеппардом [113] было показано, что в случае ярко выраженных полос н-ал-килбромидов все распределение в качестве исходной вершины имеет частоту веерных колебаний СН2 бромистого этила. Соответствующие полосы поглощения в спектрах спиртов и - парафинов гораздо слабее ( рис. 11), но тем не менее и в спектрах этих соединений обнаруживаются регулярные распределения [59], согласующиеся по интервалам частот с гораздо более интенсивными распределениями других гомологических рядов. [35]

Задача раскрашивания областей произвольной карты может быть сведена к задаче раскрашивания областей трехвалентной карты. Это достигается путем замены какой-то вершины степени, отличной от трех, на замкнутую многоугольную область с числом вершин, равным числу ребер, инцидентных с исходной вершиной. Каждая из новых вершин имеет степень 3, и к ней инцидентно одно из этих ребер. [36]

Инверсия на входных зажимах многополюсника. [37]

Требуется инверсировать разомкнутый путь от источника к стоку. Для того чтобы инверсировать выделенный разомкнутый путь, не перемещая остальных ветвей графа, достаточно ввести вспомогательные вершины ( как показано на рисунке), соединенные с исходными вершинами ветвями, коэффициент передачи которых равен единице. [38]

На рис. 3 - 3 в показаны схема и граф, построенный для нее указанным способом. Ветви графа, нанесенные пунктиром, не нужны либо потому, что коэффициент передачи ветви равен нулю ( в знаменателе бесконечная узловая проводимость), либо в силу того, что исходная вершина имеет нулевую величину. Граф, вычерченный сплошными линиями, есть У-гра. [39]

Одним из известных параллельно-последовательных методов компоновки является метод оптимального ( параллельного) свертывания схемы. В этом случае для осуществления компоновки образуется специальное прадерево свертки, которое строится следующим образом. Исходные вершины графа схемы считаются принадлежащими первому уровню прадерева свертки Рсг. На первом этапе из множества исходных вершин выбираются равноценные группы вершин для заданного критерия оптимизации, которые принимаются в качестве центров дальнейшего наращивания подграфов Gt. Каждую такую группу могут составлять две и более вершин исходного графа схемы. Образованные группы вершин считаются принадлежащими множеству Р второго уровня прадерева свертки. [40]

Обратите внимание: к каждой вершине ведет точно одно ребро. С другой стороны, из каждой исходной вершины выходят d ребер, а из специальных - ни одного. [41]

Посмотрим сначала, удалось ли нам этого достичь. При обходе по уровням мы начинали с исходной вершины и шли по всем доступным ребрам, если только вершина на втором конце ребра не оказывалась уже посещенной. Приводит ли это к каким-либо трудностям. Любой из узлов, в который можно попасть из данного, окажется посещенным - но вдоль самого прямого пути. [42]

Поочередно меняя каждую внебазисную переменную, найдем все Л - М ребер, выходящих из исходной вершины и проводящих в смежные вершины. Сравним все значения функции в смежных вершинах L, и выберем из них наименьшее. Если оно меньше, чем значение функции в исходной вершине L0, то переместимся в наинизшую из новых вершин и повторим процесс. Если же minL; L0, то минимум уже достигнут в исходной вершине. [43]

На следующем этапе выбирается та из свободных переменных, введение которой в число базисных способно улучшить значение целевой функции. Геометрически эти операции эквивалентны выбору того из ребер многогранника ограничений, соединяющих исходную вершину с соседними, проекция градиента целевой функции на которое максимальна. Затем вновь вводимая базисная переменная выражается через переменную, выводимую из числа базисных, и другие свободные переменные. Все остальные базисные переменные и значения целевой функции выражаются через новые свободные переменные. Если окажется, что введение любой из свободных переменных неспособно улучшить значение целевой функции, то найденная вершина является оптимальной. В противном случае все операции второго этапа повторяются. Доказано, что, если следовать этой схеме, оптимальное решение будет получено через конечное число шагов. [44]

Последовательное уменьшение порядка дискретного преобразования иллюстрируется при помощи рисунков. Вычисляемые значения а ( п) представим массивом конечных вершин некоторого графа. Значения b ( n) и с ( л) изобразим посредством вертикального массива исходных вершин. Связь между значениями, соответствующими вершинам того и другого массивов, выражаемая соотношениями ( 4 - 88), может быть показана при помощи стрелок, соединяющих соответствующие вершины. [45]

Страницы: 1 2 3 4