Добавление - дуга
Cтраница 1
Добавление дуги и к ( М, N порождает однозначно определенный цикл, содержащий и. Пусть w [ Nl - соответствующий ему циклический вектор. [1]
Поскольку добавление дуги приводит к появлению цикла, то цикл содержит эту дугу. Остальная часть цикла представляет собой цепь, соединяющую граничные вершины дуги. [2]
Под операцией добавления дуги ( х, у) в Г понимается переход от гр. [3]
Транзитивное замыкание исходного графа получается добавлением дуг между всеми вершинами, включенными в составную. В худшем случае алгоритм требует 0 ( п3) операций. [4]
 |
Замыкание контура интегрирования для представления функции ( / при.| Области сходимости при двустороннем преобразовании Лапласа. [5] |
На основании этого свойства контур, образованный добавлением дуги ABC бесконечно большого радиуса ( рис. 2.31, а) к прямой а, - too, at too, можно произвольно деформировать при соблюдении условия, что все полюса, расположенные левее прямой о, - / оо, ol - f too остаются внутри контура. [6]
При решении задач оптимизации приоритето-порожда-ющих функционалов на множестве ( G) операции отождествления вершин графа G н добавления дуг в G позволяют последовательно сужать область поиска экстремума. Рассмотрим условия, при которых применение указанных операций обеспечивает выделение множества ( G), содержащего хотя бы одну оптимальную перестановку. [7]
Пусть G ( N U) - граф, полученный из G в результате многократного применения операций отождествления вершин и добавления дуг. [8]
Последний вопрос, связанный со спецификой метода последовательных улучшений плана в данной задаче, - изменение базиса. Добавление дуги и к графу ( УИ, N) либо соединяет две компоненты связности - в этом случае появится компонента связности с двумя циклами - либо прямо породит второй цикл в какой-нибудь компоненте связности. [9]
Задачу нахождения кратчайших цепей между всеми парами узлов можно решить, добавив базисные дуги ( если таких дуг в сети не было) между всеми парами узлов. При добавлении базисной дуги ей ставится в соответствие длина, равная длине кратчайшей цепи, состоящей из базисных дуг исходной сети. [10]
В этом случае необходимо разомкнуть старый контур, исключив из него одну дугу из числа дуг, не входящих в новый контур. Для случая, когда добавление дуги и контура не порождает, процесс сводится также к удалению из базиса дуги и, не принадлежащей контуру. [11]
Если w [ i j ] 0, то значит дуги из 1й вершины в j - ю нет. Если матрицу w скомпенсировать путем добавления дуг только там, где они есть ( w [ i j ] 0), то тогда для каждой вершины число выходящих из нее дуг будет равно числу входящих в нее дуг. Число выходящих из 1 - й вершины дуг - это сумма элементов матрицы w по i - й строке, а число входящих в i - ю вершину дуг - это сумма элементов матрицы w no i - y столбцу. В скомпенсированной матрице w эти суммы равны. [12]
Напомним важное свойство контурных интегралов: величина интеграла не зависит от формы замкнутого контура, по которому производится интегрирование, если только полюсы подынтегральной функции остаются внутри контура. На основании этого свойства контур, образованный добавлением дуги ABC бесконечно большого радиуса ( рис. 6.2, а) к прямой с - too, с - - i оо, можно произвольно деформировать при соблюдении условия, что все полюсы, расположенные левее прямой с - / оо, с / оо, остаются внутри контура. [13]
Напомним важное свойство контурных интегралов: величина интеграла не зависит от формы замкнутого контура, по которому производится интегрирование, если только особые точки подынтегральной функции остаются внутри контура. На основании этого свойства контур, образованный добавлением дуги ABC бесконечно большого радиуса R ( рис. 5.2. а) к прямой с - too, с too, можно произвольно деформировать при соблюдении условия, что все полюсы, расположенные левее прямой с - too, с ioo, остаются внутри контура. [14]
Эти свойства позволяют интерпретировать симплекс-алгоритм решения сетевых задач. Будем последовательно соединять сначала узлы производства со всеми соседними узлами с помощью дуг, исходящих из узлов производства, следя за тем, чтобы добавление новой дуги не привело к образованию контура. Введя новую дугу, пометим узел, соединенный с исходным. Когда все узлы производства будут просмотрены, проделаем то же с узлами потребления, причем будем использовать лишь дуги, входящие в узлы потребления. Если после этого останутся непомеченными некоторые промежуточные узлы, повторим ту же процедуру, начиная от помеченных промежуточных узлов, соединенных с уз-ламп производства. Дерево будет построено, когда все узлы окажутся помеченными. Если в графе остаются изолированные друг от друга множества точек, исходная задача распадается на ряд самостоятельных. [15]
Страницы: 1 2