3.2 Пути, цепи, контуры, циклы

 

Простой путь — это последовательность дуг, в которой каждая следующая дуга имеет началом конец предыдущей дуги и каждая дуга встречается не более одного раза (если отказаться от этого второго условия и допустить повторы вершин или дуг в пути, то граф называ­ется путем — без слова «простой»).

 

Рис. 3. Путь.

 

Цепь — это последовательность дуг, в которой каждая дуга имеет общую вершину с предыдущей дугой и со следующей дугой и эти общие вершины различны.

 

 

Рис. 4. Цепь.

 

Контур — это простой путь, в котором начало и конец совпадают. Цикл – это цепь, в которой начало и конец совпадают.

 

 Рис. 6. Цикл.