05. Маршруты в графе

Определение. Маршрутом В графе называется чередующаяся последовательность вершин и рёбер , в которой любые два соседних элемента являются инцидентными.

Длиной маршрута называется число ребер в нём с учётом повторений.

Замкнутым называется маршрут, начало и конец которого находятся в одной вершине. Иначе, маршрут называется Открытым.

Цепью называется открытый маршрут с различными ребрами. Циклом называется замкнутый маршрут с различными ребрами. Простыми называются цепь и цикл с различными вершинами.

Например, в графе, диаграмма которого приведена на рис. 1, последовательность является открытым маршрутом длиной 3; последовательность является простой цепью длиной 3; последовательность является простым циклом длиной 3.

Задачи и упражнения

17. Составьте различные маршруты, содержащие четвертую вершину графа задачи 1.

18. Составьте различные маршруты длиной четыре графа задачи 1.

19. Составьте, если возможно, для графа задачи 1 следующие маршруты: открытый маршрут, но не цепь; цепь, но не простую цепь; простую цепь; замкнутый маршрут, но не цикл; цикл, но не простой цикл; простой цикл.

< Предыдущая		Следующая >