Cтраница 3
От корня до любого листа легко проследить элементарную последовательность дуг. Число дуг между корнем и листом называется уровнем листа. [31]
Исходной информацией для решения задачи поиска элементарных путей служат анализируемый орграф, структура которого задана тем или иным способом, и номера начального и конечного узлов путей. Найденные пути могут быть представлены в виде последовательности узлов или в виде последовательности дуг. [32]
Некоторые поверхности ( видимые множества) сцены оказываются видимо соседними в силу того, что они принадлежат одному телу, другие же - в силу того, что одно тело частично загораживает другое. Фрагмент сцены, соответствующий всем видимо соседним поверхностям тела, должен иметь ограничивающую последовательность дуг, помеченных предикатом hind. Очевидно, что такие последовательности дуг соответствуют последовательности линий, которая ограничивает множество соседей. [33]
Выделение кратчайшего пути осуществляется по пометкам стандартным образом. Для поиска отрицательного цикла по первому признаку нужно по новой пометке узла 0 восстановить последовательность дуг, участвовавших в образовании пометок, и отбросить дважды проходимые дуги. Во втором случае путь отыскивается тем же способом, если отправиться от любого узла с изменившейся на последнем шаге пометкой. [34]
Использование регистров значительно увеличивает объем занимаемой при расчете памяти. В связи с этим возрастает необходимость в рациональном формальном описании сети: число регистров памяти зависит от последовательности дуг сети в описании. [35]
Есть пять образующих, расположенных, как это показано на рис. 3.5, и соединенных между собой информационными каналами так, что из любой образующей можно передать в любую образующую. Время, необходимое для принятия решений из одной образующей в другую, приведено в табл. 3.1. Требуется найти такую последовательность дуг, начинающуюся в образуюшей 1, проходящей через все образующие и заканчивающуюся в образующей 1, чтобы продолжительность была наименьшей. [36]
Дерево - это связный граф, не содержащий циклов. Корневым деревом называется ориентированный граф, обладающий следующими тремя свойствами: 1) существует точно одна вершина, называемая корнем, в которую не входит ни одна дуга; 2) для каждой вершины дерева существует последовательность дуг из корня в эту вершину; 3) в любую вершину, за исключением корня, входит точно одна дуга. [37]
Путь на графе может быть открытым, если одна и та же вершина встречается не более одного раза, и замкнутым, если путь возвращается к начальной вершине. Путь может быть и незамкнутым, и неоткрытым. Последовательность дуг, входящих в замкнутый путь, называется контуром обратной связи. Дуги и вершины, не входящие в контур обратной связи, называются каскадными. [38]
При машинном расчете алгоритм выбора расчетных сочетаний нагрузок задается в виде графа. Геометрически такой граф представляет собой совокупность дуг, соединенных между собой в вершинах графа. Последовательность дуг ( цепь) от начальной точки до конечной определяет одну возможную комбинацию нагрузок. Если две или несколько нагрузок не могут действовать одновременно - они должны быть представлены параллельными дугами. [39]
Применяя теперь задачу 5.17, получим нужное утверждение. Примените задачу 5.13. 5.22. Примените задачу 5.13. 5.23. Пусть ( Q, з &, Р - вероятностное пространство, где Q - окружность единичной длины, 4 - - о-алгебра борелевских подмножеств Q, Р - мера Лебега. Рассмотрим последовательность дуг А, А. [40]
Так как из каждой вершины графа, соответствующей арифметическому оператору, исходит только одна дуга, то нетрудно убедиться, что каждой комбинации соответствует строго определенная последовательность дуг графа программы. Упорядоченную таким образом последовательность дуг, когда конец каждой дуги совпадает с началом следующей, будем называть путем графа программы. При этом всегда будем полагать, что всякий путь начинается в начальном элементе множества X, а оканчивается либо в том же элементе, либо в конечном элементе этого множества. [41]
Некоторые поверхности ( видимые множества) сцены оказываются видимо соседними в силу того, что они принадлежат одному телу, другие же - в силу того, что одно тело частично загораживает другое. Фрагмент сцены, соответствующий всем видимо соседним поверхностям тела, должен иметь ограничивающую последовательность дуг, помеченных предикатом hind. Очевидно, что такие последовательности дуг соответствуют последовательности линий, которая ограничивает множество соседей. [42]
Предположим, что D ( V, A) - примитивный граф с п - 1 и индекс примитивности равен пг. По предположению ( в силу примитивности), граф D сильно связен. Далее по лемме 4.6 существует замкнутая последовательность дуг длины 1 из v в V. Тогда по той же лемме существует замкнутая последовательность дуг R ( дважды Р) н S длины It и 2t - - соответственно. [43]
Граф g ( X, Т) называется конечным, если число его вершин конечно. Две точки, определяющие ребро или дугу, называются смежными. Смежными называются и две дуги, если они имеют общую вершину. Последовательность дуг, при которой конец одной дуги является началом другой, называется путем. [44]
Предположим, что D ( V, A) - примитивный граф с п - 1 и индекс примитивности равен пг. По предположению ( в силу примитивности), граф D сильно связен. Далее по лемме 4.6 существует замкнутая последовательность дуг длины 1 из v в V. Тогда по той же лемме существует замкнутая последовательность дуг R ( дважды Р) н S длины It и 2t - - соответственно. [45]