Начальная вершина - дуга
Cтраница 1
 |
Ормаршруты, пути, той путь также называют прямым J J. [1] |
Начальная вершина дуги определяет ее входную переменную. Вершина графа, имеющая только выходящие из нее дуги, определяет внешнюю переменную ( внешнее воздействие) и называется входной вершиной графа. [2]
 |
Ормаршруты, пути, той путь также называют прямым J J. [3] |
Ормаршрут называется замкнутым, если конечная вершина дуги Wn совпадает с начальной вершиной дуги Wi, и незамкнутым в противном случае. [4]
Дугой называется ориентированная пара ( Et, EJ) вершин графа Ei и Е, где Ei - начальная вершина дуги, a EJ - конечная. [5]
Если вершина Vj уже помечена, то метки г ( и) известны для всех вершин Vj е У, являющихся начальными вершинами дуг, у которых конечной вершиной является и, так как в соответствии со способом нумерации это означает, что VjVj и, следовательно, вершины Vj уже помечены в процессе применения алгоритма. [6]
Конечная последовательность ( не обязательно различных) дуг таких, что конечная вершина каждой дуги ( исключая последнюю) является также начальной вершиной последующей дуги. Говорят, что маршрут является замкнутым, если начальная вершина первой дуги совпадает с конечной вершиной - последней дуги, и незамкнутым в противном случае. [7]
Работая с классами эквивалентности, мы будем переходить от одной новой вершины к другой по дугам старого графа. Часто нужно будет искать нынешнего представителя начальной вершины дуги, выбранной для данной вершины. [8]
В методе ветвей и границ искомый вариант, как отмечалось, строится поэтапно, сужая на каждом из этапов множество возможных выборов. Например, в задаче о кратчайшем пути это есть подмножества тех путей, которые могут быть получены продолжением одной из исходящих из начальной вершины дуг. После этого выбирается то из подмножеств, оценка v j которого наименьшая, и оно разбивается на некоторое число подмножеств, для каждого из которых отыскивается своя оценка. [9]
Пусть дан граф G с п вершинами и т дугами. Матрица инци-денций графа G обозначается через В [ btj ] и является матрицей размерности п X т, определяемой следующим образом: Ьц - 1, если xt является начальной вершиной дуги a j, Ьц - 1, если xt является конечной вершиной дуги ау, Ьц 0, если Xi не является концевой вершиной дуги at или если и) является петлей. [10]
Для задания графа G ( X, А) используют матрицу смежности и матрицу инцидентности. В матрицу смежности М [ а ] входят элементы а 1, если в графе G ( X, А) существует ребро ( xt, Xj), и atj О, если такого ребра нет. Элементы матрицы Ьц 1, если xt является начальной вершиной дуги a /, bi - 1, если Xi является конечной вершиной дуги а, и Ьц 0, если Xi не инцидентна дуге at или если она является петлей. [11]
Математическая система, состоящая из двух множеств V и А и отображения Д множества А на VXV. Элементы V и А называются соответственно вершинами и дугами ориентированного графа, а Д называется отображением ориентированной инцидентности. Если Д ( а) ( р, ю), тон называется начальной вершиной дуги а, в w - конечной вершиной. [12]
Задача состоит в определении общего среднего потока в любой момент времени в этой сети. В общем случае, величина потока, поступающего из источника, также описывается стохастическим процессом. Таким образом, в каждый момент времени поток, текущий из источника к начальной вершине дуги, может существовать, а может и не существовать. Если величина поступающего потока превышает пропускную способность дуги, через которую он должен пройти, он задерживается в начальной вершине этой дуги. [13]
Страницы: 1