Маршруты. Цепи. Циклы.
Маршрутом в графе 
называют чередующуюся последовательность вершин и ребер, в которой любые два соседних элемента инцидентны.
Если 
, то маршрут называют замкнутым. Если все ребра различны, то маршрут называют цепью. Если все вершины, а значит и все ребра, различны – то маршрут называют простой цепью. Обозначают маршрут 
. Восклицательный знак – обозначение простой цепи. 
– длина маршрута 
. В маршруте 
и 
называют концами. Замкнутая цепь называется циклом. Замкнутая простая цепь называется простым циклом. Число циклов в графе обозначают 
. Граф без циклов, 
, называют ациклическим.
Пример:
v1-v3-v4-v3 – маршрут, но не цепь;
v1-v3-v5-v2-v3-v4 – цепь, но не простая цепь;
v1-v4-v3-v5 – простая цепь;
v1-v3-v5-v2-v3-v4-v1 – цикл, но не простой цикл;
v1-v3-v4-v1 – простой цикл.
Длиной маршрута называют количество ребер в нем (учитывая повторения). Расстоянием между вершинами 
и 
, обозначается 
, называется длина кратчайшей цепи 
, а сама кратчайшая цепь называется геодезической цепью. Множество вершин, находящихся на одинаковом расстоянии 
от вершины называют ярусом.
Дата добавления: 2015-12-16; просмотров: 832;