доминирующий набор граф турниров

Question

Я пишу алгоритм, чтобы найти доминирующий набор графа турнира. Является ли минимальное остовное дерево ориентированного графа эквивалентным доминирующему множеству графа? Другими словами, если я найду наименьшее MST для графа турнира (итерируя по всем вершинам), могу ли я сказать, что это эквивалентно доминирующему набору графа?

Answer 1

В этой статье в Википедии говорится о проблемах поиска доминирующего множества и поиска связующего дерева. эквивалентны. При наличии остовного дерева неконечные узлы образуют доминирующий набор, а при наличии связанного доминирующего набора вы можете легко получить исходный граф, соединяющий одно его остовное дерево с вершинами, которые ему не принадлежат. Однако поиск связующего дерева минимальный и поиск доминирующего набора минимальный - разные проблемы. Я думаю, что они снова эквивалентны, но я не уверен.

Answer 2

Нет, потому что MST будет включать все вершины графа, а доминирующий набор может и не быть.

См., например, график здесь: http://en.wikipedia.org/ вики / Турнирная <код> _ (граф <код> _ теория) Вершины 2 и 4 создают доминирующий набор, а не остовное дерево.