Последовательность - вершина
Cтраница 4
 |
Пример графа с дугами обратной связи, которые можно исключить при выделении псевдокомпонент и вершинных сечений ( Е с. [46] |
Согласно этой терминологии контур-это путь, начинающийся и заканчивающийся в одной и той же вершине ориентированного графа; путь-это маршрут, в котором все вершины различны ( встречается понятие элементарный путь, например в работах К. Под термином маршрут общепринято понимать некоторую последовательность вершин и дуг на любом графе ( ориентированном либо неориентированном), что и использеутся выше. [47]
Так как ( 1 / 3) 24 / а 3 / 4, то мы получаем в этом случае требуемый результат. Наконец, существует одно вхождение вершины vs л последовательность вершин для G. Так как a log ( & Q / co) a log b 1, доказательство закончено. [48]
Найденную вершину х изымем и если k 0, то поместим х в конец последовательности изъятых вершин. В случае k 1 поместим х в начало последовательности изъятых вершин. Проверка работы алгоритма показала, что время счета пропорционально второй степени числа элементов множества. [49]
Ясно, что все пути вне R, которые существовали до редукции, продолжают существовать и после нее. Исключением являются те, в которые не была включена последовательность вершин из R. [50]
Кривые По и По имеют по крайней мере две различные общие точки. Путем в графе будет любая бесконечная в обе стороны последовательность вершин типа а), а также последовательности, ограниченные слева, справа или с двух сторон. [51]
Последовательность порядка обработки операторов оптимизируемой программы во многом влияет на скорость работы алгоритма. Ряд алгоритмов обрабатывает операторы программы до тех пор, пока последовательность обработанных вершин не будет содержать в качестве подпоследовательностей все простые пути по уграфу программы или все его простые несокращаемые пути. В основе большинства эффективных алгоритмов анализа уграфов транслируемых программ содержатся специального вида нумерации вершин уграфа, получившие название базисных. [52]
Введем теперь специальный класс сводимых графов, так называемые спиральные графы, для которых легко строятся требуемые последовательности вершин. Так как любой сводимый граф достаточно просто преобразуется в спиральный, то последовательность вершин для спирального графа также просто преобразуется в последовательность вершин для исходного. Класс спиральных графов определяется рекурсивно. [53]
Практически в доказательстве теоремы 14 содержится алгоритм раскраски, исключая момент выбора соцветных вершин. Так как вся сложность решения задачи о раскраске указанным методом заключается в построении последовательности соцветных вершин, то необходима подходящая эвристика для этого шага. [54]
Обратим внимание на то, что Лбсе па плане скоростей звена 2 подобен / ВСЕ па плане механизма по взаимной перпендикулярности сторон. В треугольнике па плане механизма при обходе против хода часовой стрелки получается та же последовательность вершин. Если треугольник bee показать в другом положении, симметричном относительно отрезка be, то сходственности расположения треугольников Ьсс и ВСЕ уже не будет. [55]
Страницы: 1 2 3 4