Пусть G = G(V,E) – неориентированный граф с вершинами v0, v1, v2, v3, …, vk множества V и ребрами e1, e2, e3, …, ek множества Е. Определение. Путем (маршрутом) длины k из v0 в vk (или между v0 и vk) называется последовательность v0e1v1e2v2e3v3…v(k-1)ekvk такая, что eі = {ѵі-1, vі}. Таким образом, путь длины k имеет k ребер. Определение. Если нет рёбер, предшествующих e1, то вершина v0 называется начальной, если нет рёбер, следующих после ek, то вершина vk называется конечной, вершины пути, не являющиеся начальной или конечной, называются внутренними...

Определение. Ориентированным путем (ориентированным маршрутом) длины k из v0 в vk (или между v0 и vk) называется последовательность v0,e1,v1,e2,v2,e3,v3,…v(k-1),ek,vk такая, что eі = (v(і-1), vі). Таким образом, ориентированный путь длины k имеет k ориентированных рёбер, при этом, конечно, обязательно учитывать направление ориентированных ребер, составляющих путь, т. е. начальная вершина последующего ориентированного ребра должна быть конечной вершиной предыдущего ориентированного ребра. Определение...