3. Петли, ориентированные циклы и циклы

Петлей называется дуга, начальная и конечная вершины которой совпадают. На рис. 1.3, например, дуги являются петлями.

Путь называется замкнутым, если в нем начальная вершина дуги совпадает с конечной вершиной дуги

Так, например, в графе, приведенном на рис. 1.3, последовательности дуг

являются замкнутыми путями.

Пути (1.7) и (1.9) являются замкнутыми простыми орцепями (контурами, или простыми орциклами), поскольку в них одна и та же вершина используется только один раз (за исключением начальной и конечной вершин, которые совпадают), а путь (1.8) не является контуром, так как вершина используется в нем дважды. Контур, проходящий через все вершины графа, имеет особое значение и называется гамильтоновым контуром. Конечно, не все графы обладают гамильтоновыми контурами. Так, например, контур (1.9) является гамильтоновым контуром графа, приведенного на рис. 1.3, а граф на рис. 1.2 не имеет гамильтоновых контуров, поскольку не существует такой дуги, для которой была бы конечной вершиной.

Замкнутый маршрут является неориентированным двойником замкнутого пути. Таким образом, замкнутый маршрут является маршрутом в котором совпадают начальная и конечная вершины, т. е. в котором яд.

На рис. 1.3 маршруты

и

являются замкнутыми маршрутами.