Введение
Найти кратчайшие пути по всем рёбрам графа
В теории графов, области математики и информатики, задача о маршруте Гуана, китайская задача почтальона, тур почтальона или задача инспекции маршрута заключается в поиске кратчайшего замкнутого пути или цикла, который посещает каждое ребро (связного) неориентированного графа хотя бы один раз. Если граф имеет эйлеров цикл (замкнутый путь, проходящий по каждому ребру ровно один раз), этот цикл является оптимальным решением. В противном случае задача оптимизации состоит в том, чтобы найти минимальное количество рёбер графа для дублирования (или подмножество рёбер с минимально возможным суммарным весом), чтобы полученный мультиграф имел эйлеров цикл. Она может быть решена за полиномиальное время. Она отличается от задачи коммивояжёра тем, что коммивояжёр не может повторно посещать узлы. Эта проблема была первоначально изучена китайским математиком Кван Мэй Ко в 1960 году, чья китайская статья была переведена на английский язык в 1962 году. Изначальное название "китайская задача почтальона" было придумано в его честь; различные источники приписывают авторство этого названия либо Алану Дж. Голдману, либо Джеку Эдмондсу, оба из которых в то время работали в Национальном бюро стандартов США. Обобщением является выбор любого множества T, состоящего из чётного числа вершин, которые должны быть соединены множеством рёбер в графе, чьи вершины нечётной степени точно соответствуют вершинам T. Такое множество называется T-соединением. Эта проблема, задача T-соединения, также может быть решена за полиномиальное время тем же методом, что и задача почтальона.
Ненаправленный раствор и Т-соединения
Проблема инспекции ненаправленного маршрута может быть решена за полиномиальное время алгоритмом, основанным на концепции T-соединения. Пусть T – множество вершин в графе. Множество ребер J называется T-соединением, если множество вершин, имеющих нечетное число инцидентных ребер в J, точно совпадает с множеством T. T-соединение существует, если каждый связный компонент графа содержит четное число вершин из T. Задача T-соединения состоит в том, чтобы найти T-соединение с минимально возможным числом ребер или минимально возможным суммарным весом. Для любого T, наименьшее T-соединение (если оно существует) обязательно состоит из путей, соединяющих вершины T попарно. Эти пути должны быть такими, чтобы их общая длина или суммарный вес был минимальным. В оптимальном решении никакие два из этих путей не будут иметь общих ребер, но они могут иметь общие вершины. Минимальное T-соединение можно получить, построив полный граф на вершинах T, ребра которого представляют кратчайшие пути в заданном исходном графе, а затем найдя совершенное соответствие минимального веса в этом полном графе. Ребра этого соответствия представляют собой пути в исходном графе, объединение которых образует искомое T-соединение. Как построение полного графа, так и поиск соответствия в нем могут быть выполнены за O(n³) вычислительных шагов. Для задачи инспекции маршрута T следует выбирать как множество всех вершин нечетной степени. По условиям задачи, весь граф связен (иначе тура не существует), и по лемме о рукопожатиях он содержит четное число вершин нечетной степени, поэтому T-соединение всегда существует. Удвоение ребер T-соединения приводит к тому, что заданный граф становится эйлеровым мультиграфом (связным графом, в котором каждая вершина имеет четную степень), из чего следует, что у него есть эйлеров тур – тур, проходящий по каждому ребру мультиграфа ровно один раз. Этот тур будет оптимальным решением задачи инспекции маршрута.
Направленный раствор
На ориентированном графе применимы те же общие принципы, но необходимо использовать иные методы. Если ориентированный граф является эйлеровым, достаточно найти эйлеров цикл. Если нет, то нужно найти T-соединения, что в данном случае означает поиск путей от вершин с входящей степенью, превышающей исходящую, к вершинам с исходящей степенью, превышающей входящую, так, чтобы входящая степень каждой вершины стала равной ее исходящей степени. Это можно решить как частный случай задачи о потоке минимальной стоимости, в которой для каждой единицы избытка входящей степени имеется одна единица предложения, а для каждой единицы избытка исходящей степени – одна единица спроса. Таким образом, задача разрешима за время O(|V|²|E|). Решение существует тогда и только тогда, когда данный граф сильно связен.
Варианты
Было изучено несколько вариантов задачи о китайском почтальоне, и было показано, что они NP-полны. Задача о ветреном почтальоне — это вариант задачи об инспекции маршрута, в которой входными данными является неориентированный граф, но стоимость прохождения каждого ребра в одном направлении может отличаться от стоимости прохождения в другом направлении. В отличие от решений для ориентированных и неориентированных графов, она является NP-полной. Задача о смешанном китайском почтальоне: в этой задаче некоторые рёбра могут быть ориентированными и, следовательно, могут посещаться только в одном направлении. Когда задача требует минимального обхода диграфа (или мультиграфа), она известна как "проблема нью-йоркского уборщика улиц". Задача о k китайских почтальонах: найти k циклов, все начинающиеся в заданном месте, так чтобы каждое ребро было пройдено хотя бы одним циклом. Цель состоит в том, чтобы минимизировать стоимость самого дорогого цикла. "Задача о сельском почтальоне": решить задачу с некоторыми необязательными рёбрами.