Дерево кратчайших путей – это ориентированное дерево с корнем в вершине S . Все пути в этом дереве – кратчайшие для данного графа.
Дерево кратчайших путей строится по таблице, в него включаются вершина за вершиной в том порядке, в котором они получали постоянные метки. Первым в дерево включается корень – вершина S .
Построим дерево кратчайших путей для нашего примера.
Сначала включаем в дерево корень – вершину 1. Затем в дерево включается дуга (1,6). Следующей была упорядочена вершина 9, длина кратчайшего пути до которой равна 3. Первый раз число 3 появилось в третьей строке, которая заполнялась при . Следовательно, вершина 6 – предпоследняя вершина кратчайшего пути до вершины 9. Включаем в дерево дугу (6,9) длины 1.
Затем была упорядочена вершина 2 с длиной кратчайшего пути, равной 4. Это число первый раз появилось в третьей строке, которая заполнялась при . Следовательно, кратчайший путь во вторую вершину проходит по дуге (6,2). Включаем в дерево дугу (6,2) длины 2.
Далее была упорядочена вершина 12, . Первый раз число 4 появляется в четвертой строке, которая заполнялась при . В дерево включается дуга (9,12) длины 1. Полное дерево кратчайших путей показано на рис. 5.
Алгоритм Дейкстры может ошибаться, если в графе есть дуги отрицательной длины. Так, отыскивая кратчайшие пути от вершины s =1 для графа на рис. 6, алгоритм сначала упорядочит вершину 3, затем вершину 2 и закончит работу. При этом этот кратчайший путь до вершины 3, с точки зрения алгоритма Дейкстры, - это дуга (1,3) длины 3.
На самом деле, кратчайший путь до вершины 3 состоит из дуг (1,2) и (2,3), длина этого пути равна 5+(-3)=2.
Из-за наличия дуги (2,3) отрицательной длины –3 оказались нарушенными следующие базовые принципы:
· ближайшая к s вершина лежит от нее на расстоянии двух дуг, а не одной;
· промежуточная вершина кратчайшего пути 1-2-3 (вершина 2) лежит дальше от вершины 1 (на расстоянии 5), чем конечная вершина пути 3.
Следовательно, присутствие дуг отрицательной длины усложняет решение задачи о кратчайшем пути и требует использования более сложных алгоритмов, нежели алгоритм Дейкстры.
Валы и оси служат для установки на них вращающихся деталей и обеспечения постоянного положения осей вращения этих деталей. Вал отличается от оси тем, что передает вращающий момент от одной детали к другой, а ось не передает. На рис.1 момент от полумуфты 3 к шестерне 1 передается валом 2.
Рис. 1
По назначению валы можно разделить на валы передач, несущие детали передач, и коренные валы несущие кроме деталей передач, рабочие органы машин (ротор турбины).
По форме геометрической оси валы делят на: прямые, коленчатые и гибкие. Коленчатые и гибкие валы относятся к специальным валам и в данном курсе не рассматриваются.
По конструкции различают валы и оси гладкие, фасонные, или ступенчатые, а также сплошные и полые. Чаще всего валы и оси выполняют ступенчатыми, хотя валы и оси постоянного сечения более технологичны. Образование ступеней связано с закреплением деталей и возможности их монтажа при посадках с натягом.
Опорная часть вала или оси называется цапфой. Концевая цапфа называется шипом, а промежуточная – шейкой. Концевая цапфа, предназначенная нести осевую нагрузку, называется пятой. Шипы и шейки вала опираются на подшипники, опорной частью для пяты является подпятник. По форме цапфы могут быть цилиндрическими, коническими, шаровыми и плоскими (пяты).
Кольцевое утолщение вала, составляющее с ним одно целое, называется буртиком. Переходная поверхность от одного сечения к другому, служащая для упора насаживаемых на вал деталей, называется заплечиком. Криволинейную поверхность плавного перехода от меньшего сечения к большему называют галтелью.