Маршруты, пути, циклы

Маршрут в графе - это последовательность вершин , такая, что для каждого вершины и соединены ребром. Эти ребер называются ребрами маршрута. Говорят, что маршрут проходит через них, а число называют длиной маршрута. Говорят, что маршрут соединяет вершины и , они называются соответственно началом и концом маршрута, вершины называются промежуточными. Маршрут называется замкнутым, если . Путь - это маршрут, в котором все ребра различны. Путь называется простым, если и все вершины в нем различны. Цикл - это замкнутый путь. Цикл называется простым, если все вершины попарно различны.В графе на рисунке 2.1 последовательность вершин

· - не маршрут;

· - маршрут, но не путь;

· - путь, но не простой;

· - замкнутый маршрут, но не цикл;

· - цикл, но не простой;

· - простой цикл.

19.

Не нашли, что искали? Воспользуйтесь поиском: