В теории графов порождённым путём в неориентированном графе G называется путь, являющийся порождённым подграфом G. Таким образом, это последовательность вершин в G такая, что любые две смежные вершины в последовательности соединены ребром в G, и любые две несмежные вершины последовательности не соединены ребром G. Порождённый путь иногда называют змеёй и задача поиска самого длинного порождённого пути в графах гиперкубов известна как задача о змее в коробке.
Также порождённым циклом называется цикл, являющийся порождённым подграфом G. Порождённые циклы называются также циклами без хорд или (если длина цикла не меньше четырёх) дырами. Антидыра — это дыра в дополнении графа G, то есть антидыра — это дополнение дыры.
Длину наибольшего порождённого пути в графе иногда называют числом обхода графа[1]. Для разреженных графов существование ограниченного числа обхода эквивалентно существованию ограниченной глубины дерева[2]. Порождённым числом обхода графа G называется наименьшее число подмножеств вершин, на которые можно разложить вершины графа, чтобы каждое подмножество образовывало порождённый путь[3], и это понятие тесно связано с числом покрытия путями — минимальное число несвязных путей, являющихся порождёнными подграфами G, покрывающих все вершины G[4]. Обхват графа — это длина его кратчайшего цикла, но этот цикл должен быть порождённым циклом, так как любая хорда могла бы образовать более короткий цикл. По тем же причинам нечётным обхватом графа называется длина его кратчайшего нечётного порождённого цикла.
На рисунке показан куб, граф с восемью вершинами, двенадцатью рёбрами и порождённым путём длины четыре. Прямой анализ показывает, что не существует более длинного порождённого пути в кубе, хотя существует порождённый цикл длины шесть. Задача поиска наибольшего порождённого пути или цикла в гиперкубе, впервые поставленная Каутцем[5], известна как задача о змее в коробке и изучалась интенсивно ввиду её использования в теории кодирования и конструировании.
Многие важные семейства графов можно описать в терминах порождённых путей или циклов графов в семействе.
Задача определения, имеет ли граф G порождённый путь длины не меньшей k, является NP-полной. Гарей и Джонсон[6] высказали этот результат в неопубликованном сообщении Михалису Яннакакису. Однако эту задачу можно решить за полиномиальное время для определённых семейств графов, таких как графы без астероидальных троек[7] или графы без длинных дыр[8].