Путь - длина
Cтраница 2
Аналогично eJ / e O тогда и только тогда, когда из i в / ведет путь длины т, откуда и следует наше утверждение. [16]
Действительно, в 5х элемент b - 1, если в G ( U) существует хотя бы один путь длины / Я, от вершины хг к вершине Ху. Следовательно, с учетом определения 3 лемма 2 справедлива. Единственность следует из конструктивного характера теоремы. [17]
Стоимость c ( v, w) равна 1 тогда и только тогда, когда из v в w идет путь длины 0 или больше. [18]
Согласно формулам (4.4) и (4.5) существует столько же путей длины 2v, возвращающихся в момент 2v в начало координат, сколько существует путей длины 2v, вообще не возвращающихся в нуль. Рассмотрим теперь путь длины 2п, для которого r - г и последнее возвращение в начало происходит в некоторый момент In - 2v In. Другими словами, вероятность того, что до момента 2п произойдет ровно г возвращении, равна вероятности того, что в момент In произойдет возвращение и что ему будет предшествовать по меньшей мере г возвращений. [19]
Вершинная база орграфа 0 ( V, Е) - это минимальное подмножество B V, такое, что в каждую вершину V существует путь длины нуль или больше из некоторой вершины, принадлежащей В. [20]
Чтобы проделать путь длины п, шарик должен п раз встретиться с выбором влево - вправо. [21]
Согласно формулам (4.4) и (4.5) существует столько же путей длины 2v, возвращающихся в момент 2v в начало координат, сколько существует путей длины 2v, вообще не возвращающихся в нуль. Рассмотрим теперь путь длины 2п, для которого r - г и последнее возвращение в начало происходит в некоторый момент In - 2v In. Другими словами, вероятность того, что до момента 2п произойдет ровно г возвращении, равна вероятности того, что в момент In произойдет возвращение и что ему будет предшествовать по меньшей мере г возвращений. [22]
Необходимо выяснить, не совпадает ли этот путь с одним из ранее полученных k путей. Сравнение двух путей длины s на полное совпадение соответствующих им вершин имеет максимальную трудоемкость О ( s2) операций сравнения, при этом сравнение ведется до первого несовпадения вершин. Если выяснится, что новый путь не совпадает ни с одним из k путей, то для вычисления оценки потребуется С п2 арифметических операций. [23]
 |
Взвешенный граф и его матрица примыканий. [24] |
Кратчайший путь из двух ребер между вершинами х и у проходит еще в точности через одну вершину. Например, всякий путь длины два между вершинами А и Е проходит либо через вершину В, либо через вершину D. Сравнив сумму весов ребер АВ и BE с суммой весов ребер AD и DE, мы видим, что путь через вершину D короче пути через вершину В. В общем случае, если посмотреть на сумму весов ребер А и Е, где пробегает все вершины от А до I ( за исключением самих вершин А и Е), то минимальное значение суммы весов будет давать длину кратчайшего пути из двух или менее ребер. [25]
Первый класс характеризуется тем, что частица до момента 2г остается на положительной стороне, а в течение промежутка времени от 2г до 2п проводит на положительной стороне ровно 2 / г - 2г0 единиц времени. Существует 22Г / 2 - путей длины 2 / -, впервые возвращающихся в начало отсчета в момент 2л, из них половина лежит в верхней полуплоскости. [26]
Часто такой путь представляют последовательностью vlt У2, , vn У3 лов, лежащих на нем. В вырожденном случае один узел обозначает путь длины 0, идущий из этого узла в него же. Путь называется простым, если все ребра и все узлы на нем, кроме, быть может, первого и последнего, различны. Цикл - это простой путь длины не менее 1, который начинается и кончается в одном и том же узле. [27]
Установим взаимно однозначное соответствие между путями, впервые достигающими точки т в момент 2п - т, и всеми неположительными путями, для которых точка ( 2п, 0) является точкой последнего m - го возвращения в нуль. Полученные т точек на оси абсцисс будут вершинами некоторого неположительного пути длины 2п и будут указывать моменты возвращения этого пути в начало координат. [28]
Косвенное - это измерение, при котором искомое значение исследуемой величины находят на основании известной зависимости между этой величиной и величинами, подвергаемыми прямым измерениям. Например, при определении средней скорости движения объекта достаточно измерить время, за которое он проходит участок пути известной длины. [29]
Контур называется простым, если ни одна - вершина в нем не повторяется дважды, эйлеровым, если он содержит все дуги графа в точности по одному разу, и гамилътоновым, если он содержит все вершины графа в точности по одному разу. Длиной пути или контура называется число дуг, входящих в него. Путь длины 0 есть тривиальный или вырожденный путь. Длина эйлерова пути или контура равна числу дуг в орграфе; длина гамильтонова контура равна числу вершин в орграфе, длина гамильтонова пути на единицу меньше числа вершин. [30]
Страницы: 1 2 3