Рекуррентное соотношение (или разностное уравнение) — это математическое уравнение, которое рекурсивно определяет числовую последовательность. В таких уравнениях каждый следующий член последовательности выражается через один или несколько предыдущих членов. В дискретной математике рекуррентные соотношения служат фундаментальным инструментом для оценки сложности алгоритмов, моделирования динамических систем и решения сложных комбинаторных задач.

Теория графов предлагает мощный математический аппарат для решения классических задач маршрутизации. Две самые известные и исторически значимые концепции в этой области — эйлеровы и гамильтоновы пути и циклы. Несмотря на кажущееся визуальное сходство определений, они имеют принципиально разную математическую природу, разные методы доказательства и, что самое главное для информатики, кардинально различающуюся вычислительную сложность алгоритмов их поиска.