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