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

• Задача китайского почтальона. 3 Обход должен иметь минимальную длину или минимальный вес для графа с заданными весами дуг. 3
• Задача обхода всех вершин графа с минимальным числом вхождений в них. 1 Дано n вершин и m рёбер в неориентированном графе. 1 Начиная из любой вершины, нужно обойти все вершины, при этом побывав в каждой вершине не более одного раза. 1
• Задача поиска кратчайшего пути между двумя узлами невзвешенного графа. 4
• Задача поиска в пространстве состояний. 4 Нужно найти решение задачи с наименьшим числом ходов, если каждое состояние системы можно представить вершиной графа, а переходы из одного состояния в другое — рёбрами графа. 4
• Задача нахождения кратчайшего цикла в ориентированном невзвешенном графе. 4
• Задача нахождения всех вершин и рёбер, лежащих на каком-либо кратчайшем пути между двумя вершинами. 4