Ориентированная дуга
Cтраница 2
 |
Схема средств автоматизации отладки программ в статике. [16] |
Программа изображается абстрактно в виде ориентированного графа, каждая вершина которого соответствует некоторому множеству операторов, а каждая ориентированная дуга обозначает возможную передачу управления от одной вершины к другой. Если каждая вершина обозначает один оператор или группу последовательно выполняемых операторов, то графовая модель программы называется графом программы. [17]
ГСА - геометрическая фигура, содержащая одну начальную, одну конечную и несколько условных и операторных вершин, связанных ориентированными дугами. [18]
На полученном в результате указанных выше преобразований графе Г по матрице смежности вершин Л выделяются элементарные контуры - две вершины, связанные парой противоположно ориентированных дуг. При этом дуга, выходящая из выходной вершины во входную, помечается дугой обратной связи, а пара вершин, образующих элементарный контур, заменяется одной вершиной. После этого на упрощенном графе Г применяется алгоритм Б, позволяющий выделить дуги обратной связи и упорядочить все вершины графа по уровням предшествования. [19]
Под ориентированным графом G ( X, U) понимают геометрическую фигуру на плоскости, состоящую из множества вершин ( точек) X и множества ориентированных дуг U, их соединяющих. Последовательность ориентированных дуг, позволяющая пройти из одной вершины в другую, называется путем и изображается последовательностью соответствующих вершин. Вершины, соединенные дугой, называются инцидентными. [20]
Рассмотрим цепь, ведущую от / ( и) к кон туру ( по этой цепи определяется потенциал вершины / ( S)) В этой цепи есть отрицательно ориентированные дуги, так как иначе и замыкала бы контур. [21]
Если же i ( и) М, то, построив цепь, соединяющую i ( и) с контуром, примем в качестве и последнюю положи тельно ориентированную дугу в этой цепи. [22]
Под ориентированным графом G ( X, U) понимают геометрическую фигуру на плоскости, состоящую из множества вершин ( точек) X и множества ориентированных дуг U, их соединяющих. Последовательность ориентированных дуг, позволяющая пройти из одной вершины в другую, называется путем и изображается последовательностью соответствующих вершин. Вершины, соединенные дугой, называются инцидентными. [23]
Множество дуг, которые будучи соответственно упорядоченными, образуют контур. В геометрическом графе это замкнутая кривая, образованная соответственно ориентированными дугами. [24]
Эта модель представляет собой сеть из узлов и связывающих их ориентированных дуг, причем узлы соответствуют состояниям конечного автомага, а дуги - переходам от состояния к состоянию. [25]
Ориентированный граф называется обыкновенным, если он не имеет строго параллельных дуг и петель. Заметим, что если обыкновенный ориентированный граф имеет параллельные, но противоположно ориентированные дуги, то соответствующий неориентированный граф уже не будет обыкновенным графом в неориентированном смысле, так: -; у он содержит параллельные ребра. [26]
Требуется определить, существует ли поток из источника N s в сток Nt, удовлетворяющий на дугах ограничениям сверху и снизу. Ответим на этот вопрос сначала в случае, когда в сети имеется только одна ориентированная дуга с ограниченным снизу дуговым потоком. [27]
Рассмотрим теперь тлеяь ориентированного узла, т.е. полную проекцию узла, без указания того, какая ветвь на перекрестке проходит сверху, а какая снизу. Тень можно считать ориентированным плоским графом, вершинами которого служат перекрестки, а ребрами служат ориентированные дуги, соединяющие их. Можно рассматривать также грани - области, ограниченные дугами. [28]
При изучении автоматов удобно пользоваться терминологией, имеющейся в теории графов. Граф переходов представляет собой структуру, состоящую из вершин, изображаемых в виде кружков и ориентированных дуг, изображаемых в виде линий между парами вершин и снабженных стрелками, указывающими направление от одной вершины к другой. Граф переходов, описывающий автомат с г состояниями, содержит г вершин, причем каждая из них соответствует только одному состоянию автомата. Состояние, изображаемое вершиной, снабжается соответствующим ему обозначением. Дуги проводятся и обозначаются по следующему правилу. Из вершины Q, проводится дуга со стрелкой, направленной от этой вершины к вершине Q, если автомат, находящийся в состоянии Q, под действием входного символа может быть переведен в состояние Q &. Ya-выходные символы, соответствующие этим переходам. Дуга, соединяющая Q, с Q -, называется петлей при вершине Qi. В этом случае входной символ не изменяет внутреннее состояние автомата, но на его выходе возникает соответствующий символ. [29]
При анализе случайных процессов с дискретными состояниями удобно пользоваться геометрической схемой - так называемым графом состояний. Обычно состояния системы изображаются прямоугольниками ( кружками), а возможные переходы из состояния в состояние - стрелками ( ориентированными дугами), соединяющими состояния. [30]
Страницы: 1 2 3