Я пишу алгоритм, чтобы найти доминирующий набор турнирного графика. Является ли минимальное остовное дерево ориентированного графа эквивалентным доминирующему множеству графа? Другими словами, если я найду наименьший MST для графика турнира (итерацией по всем вершинам), могу ли я сказать, что это эквивалентно доминирующему набору графика?Доминирующий набор турнирного графика
В этом Wikipedia article указано, что проблемы нахождения доминирующего множества и нахождения связующего дерева эквивалентны. Учитывая остовное дерево, нелистовые узлы образуют доминирующее множество и задают связное доминирующее множество, вы можете легко получить исходный граф, соединяющий одно связующее дерево с вершинами, которые ему не принадлежат. Тем не менее, поиск минимальный остовное дерево и поиск минимальный доминирующий набор различные проблемы. Думаю, они снова эквивалентны, но я не уверен.
Нет, потому что MST будет включать в себя все вершины графа, а доминирующий набор не может.
См. Например, график: http://en.wikipedia.org/wiki/Tournament_(graph_theory) Вершины 2 и 4 создают доминирующий набор, а не остовное дерево.
Я еще не понял, как получить URL-адреса Википедии с круглыми скобками, чтобы правильно выйти в SO. Какие-либо предложения? – sep332 2008-11-17 18:44:00
«маленький» избыточен в «самом маленьком MST». MST по определению является наименьшим. – jfs 2008-11-17 18:40:28
Доминирующий набор турниров [LogSNP-complete] (https://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#logsnp) и, кроме того, [W \ [2 \] -полный] (https://complexityzoo.uwaterloo.ca/ Complexity_Zoo: W # w1). Маловероятно, что существует алгоритм полиномиального времени для турнирного доминирования. Однако MST разрешима в полиномиальное время. Кроме того, универсальная вершина является доминирующим множеством, тогда как MST всегда имеет все вершины. – 2015-04-29 01:14:15