Связность, путь, цепь и цикл

Последовательность переходов

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

Терминология разных учебников отличается: слово «путь» иногда допускает повторения. Поэтому в задачах важно уточнение. Длина невзвешенного маршрута — количество пройденных рёбер, а не число записанных вершин.

Связность и компоненты

Граф связен, если между любой парой его вершин есть путь. Если нет, вершины разбиваются на компоненты связности — максимальные связные части. Изолированная вершина тоже образует компоненту. Кратчайший маршрут между достижимыми вершинами можно выбрать простым: петлю с повторным возвращением можно убрать.

Три примера

1. При рёбрах $AB,BC,CD$ маршрут $A-B-C-D$ имеет длину 3. В записи четыре вершины, но переходов только три.
2. В треугольнике $AB,BC,CA$ маршрут $A-B-C-A$ — цикл длины 3. Маршрут $A-B-A$ повторяет ребро и не является цепью.
3. В графе с рёбрами $AB,BC,DE$ и отдельной вершиной $F$ три компоненты: $\{A,B,C\}$, $\{D,E\}$ и $\{F\}$.

Частые ошибки

Связность не требует ребра между каждой парой — достаточно последовательности переходов. Замкнутый маршрут не обязательно цикл: он может многократно посещать вершины и рёбра. Если рёбра имеют веса, кратчайший по числу рёбер путь может оказаться не самым коротким по расстоянию или времени. В ориентированном графе дополнительно учитывается направление каждого перехода.