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

Question

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

Answer 1

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

Answer 2

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

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