Путь и методы их построения

21 Жол және оны құру әдістері

Для ориентированного графа введено понятие пути, т. е. последовательности дуг, причем конец каждой предыдущей совпадает с началом последующей.

Путь называется простым, если никакая дуга не встречается дважды, и составным – в противном случае; элементарным – если никакая вершина не встречается дважды. В технических приложениях используются только простые, элементарные пути, и эти определения обычно опускаются. Замкнутый путь называется контуром.

Последовательность ребер и разнонаправленных дуг называется цепью. Замкнутая цепь называется циклом.

Рангом пути будем называть число дуг, составляющих путь.

Если каждой дуге поставить в соответствие некоторую характеристику, называемую весом дуги (например, длину, стоимость, вес и т. д.), то сумму этих весов будем называть длиной пути

Путь, имеющий наименьшую характеристику среди множества путей M_ST, соединяющих вершины S и T, называется кратчайшим.

Длина кратчайшего пути между S и T называется расстоянием d_ST между S и T, т. е.

Для определения кратчайших путей разработано множество методов, рассмотрим один из них – метод пометок.

Пусть дан граф, на дугах которого записаны цифры – длины дуг. Определить расстояние между вершинами 1 и 5.

Рисунок 7.1

Помечаем вершины:

Определим (из вершины 4)

(из вершины 2)

μ={1,2,4,5}

l_μ- расстояние между вершинами 1 и 5.

Дата добавления: 2015-07-17