Минимальное остовное дерево: различия между версиями

Задачу MST часто сравнивают с задачей коммивояжера и поиском минимального дерева Штейнера [6]. Деревом Штейнера называется дерево, которое может охватывать любое надмножество заданных вершин; иначе говоря, к нему могут добавляться дополнительные вершины, снижающие вес минимального остовного дерева. В задаче коммивояжера необходимо найти путь (цикл) по вершинам с минимальной общей длиной. Обобщение задачи MST на ориентированные графы иногда называют задачей минимального ветвления [5]. Тем не менее, если задача MST для неориентированных и ориентированных графов разрешима за полиномиальное время, то задача коммивояжера и нахождение минимального дерева Штейнера являются NP-полными [6].