Определения теории графов.

Маршрут (цепь) – последовательность вершин, соединенных ребрами (в ориентированном графе - однонаправленными).

Путь – маршрут без повторяющихся вершин.

Цикл – замкнутый путь.

Компонента связности – связный подграф.

Мост – ребро, при удалении которого граф распадается на несколько компонент связности.

Висячая вершина (лист) – вершина, из которой выходит одно ребро.

Гамильтонов путь – путь, проходящий через все вершины графа по одному разу.

Эйлеров маршрут – маршрут, проходящий по всем ребрам графа по одному разу.