Маршрутом в графе называется чередующаяся последовательность вершин и рёбер, в которой любые два соседних элемента инцидентны: Если то маршрут замкнут, в противном случае открыт.
Маршрут называется цепью, если все его рёбра различны, и простой цепью, если все его вершины различны.
Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом.
Граф без циклов называется ациклическим.
Важным понятием теории графов является связность. Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Например, на рис.3а изображён несвязный граф, нет маршрута из в ; из в ; из в ; из в . Связный граф показан на рис.3б, где ‑ простая цепь, а ‑ простой цикл.
а)
Рис. 3
б)
Для орграфа существует понятие сильной связности.
Путём в графе называется ориентированный маршрут.
Орграф называется сильно связным, если для любых двух вершин найдётся путь с началом в , и концом в .
На рис.4,а показан сильно связный граф, а на рис.4,б связный граф (нет пути из в ).
а)
Рис. 4
б)
Замкнутый путь в орграфе называется ориентированным циклом или контуром. Например, в графе на рис.4,а путь является ориентированным циклом, а в графе на рис.4,б контуров нет.
