Некоторые математические задачи, связанные с обходом графов по рёбрам:

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