Теория графов в логистике: задачи о кратчайшем остовом дереве и алгоритмы Прима и Краскала

Математическая модель транспортной или коммуникационной сети представляется в виде связного неориентированного графа, где вершины — это соединяемые объекты, а ребра — это возможные пути прокладки кабеля или дороги. Каждому ребру присваивается вес, отражающий стоимость, длину или время прокладки участка. Деревом в теории графов называется связный граф, не имеющий ни одного цикла (замкнутого контура). Остовным деревом (каркасом) называется такое дерево, которое включает в себя абсолютно все вершины исходного графа. Если в графе n вершин, любое остовное дерево будет содержать ровно (n - 1) ребер. Очевидно, что добавление любого лишнего ребра создаст цикл, что экономически бессмысленно (зачем прокладывать дублирующий кабель к городу, который уже подключен к сети?). Минимальное остовное дерево — это каркас, сумма весов ребер которого является абсолютным минимумом.Удивительной особенностью задачи о минимальном остове является то, что в отличие от задачи коммивояжера, она не является NP-трудной. Для ее решения существуют невероятно быстрые и полиномиально эффективные алгоритмы, которые гарантированно находят глобальный оптимум. Одним из классических методов является алгоритм Краскала (Kruskal algorithm), предложенный в 1956 году. Это типичный жадный алгоритм. В начале работы все вершины графа изолированы друг от друга. Алгоритм выстраивает все возможные ребра графа в список по возрастанию их веса. На каждом шаге алгоритм берет самое дешевое (короткое) ребро из списка и проверяет: если добавление этого ребра не создает замкнутого цикла между уже соединенными вершинами, ребро утверждается и добавляется в каркас. Если цикл возникает, ребро навсегда отбрасывается. Процесс повторяется, пока в сети не окажется ровно (n - 1) ребер, объединяющих все вершины в единый лес, а затем в единое дерево.Вторым знаменитым методом является алгоритм Прима (Prim algorithm), разработанный Робертом Примом в 1957 году (и ранее Войтехом Ярником). В отличие от Краскала, который строит дерево из разрозненных фрагментов (леса), алгоритм Прима выращивает единое дерево из одного начального корня, подобно кристаллу. Алгоритм стартует из абсолютно любой произвольной вершины. На каждом шаге он рассматривает все ребра, которые соединяют уже подключенные к дереву вершины с еще не подключенными (разрез графа). Из этого множества граничных ребер жадно выбирается самое дешевое, и новая вершина присоединяется к растущему каркасу. Алгоритм Прима математически гарантирует отсутствие циклов, так как на каждом шаге мы присоединяем строго одну новую, ранее не посещенную вершину. Оба алгоритма в итоге строят один и тот же минимальный остов (или один из них, если оптимумов несколько), но используют разные стратегии обхода матриц смежности.Аналитическая красота алгоритмов Прима и Краскала заключается в том, что они служат строительными блоками для решения гораздо более сложных задач исследования операций. Например, минимальное остовное дерево используется как нижняя граница и стартовая эвристика для приближенного решения задачи коммивояжера (алгоритм Кристофидеса опирается на MST). В кластерном анализе данных удаление нескольких самых длинных ребер из минимального остовного дерева позволяет разбить гигантские массивы точек на логические группы (Single-linkage clustering). Таким образом, теория графов доказывает, что жадный подход — стремление к сиюминутной максимальной выгоде на каждом шаге — в некоторых математических структурах (матроидах) парадоксальным образом приводит к абсолютно идеальному глобальному результату.