Цепь и цикл. Путь в графе и его связность

• Путь – последовательность рёбер, в которой конец одного ребра служит началом следующего.
• Вершины называют связными, если существует путь, соединяющий эти две вершины.
• Граф называют связным, если любые две его вершины связаны.
• Путь называется цепью, если каждое ребро содержится в нём не более одного раза.
• Если цепь начинается и заканчивается в одной и той же вершине, то она называется циклом.

 

Пример. На рисунке изображён несвязный граф. Вершины А и Б связывают два пути: АБ и АДБ. Путь через вершины АБДА является циклом.