토너먼트 그래프의 지배 세트

Question

나는 지배적 인 토너먼트 그래프 세트를 찾기 위해 알고리즘을 작성하고 있습니다. 지시 된 그래프의 최소 스패닝 트리는 지배적 인 그래프 세트와 동일합니까? 다시 말해서, 토너먼트 그래프에서 가장 작은 MST를 찾으면 (모든 정점을 반복하여), 이것이 지배적 인 그래프 세트와 동일하다고 말할 수 있습니까?

Answer 1

이것 위키 백과 기사 지배적 인 세트를 찾고 스패닝 트리를 찾는 문제는 동일하다고 말합니다. 스패닝 트리가 주어지면, 비 잎 노드는 지배적 인 세트를 형성하고 연결된 지배 세트를 주면 원래 그래프를 쉽게 얻을 수 있습니다. 그러나 찾기 최저한의 스패닝 트리 및 찾기 a 최소 지배 세트는 다른 문제입니다. 나는 그들이 다시 동등하다고 생각하지만 확실하지 않습니다.

Answer 2

아니요, MST는 그래프의 모든 정점을 포함하고 지배적 인 세트는 그렇지 않을 수 있기 때문입니다.

예를 들어 여기의 그래프를 참조하십시오. http://en.wikipedia.org/wiki/tournament_(그래프_이론)정점 2와 4는 스패닝 트리가 아닌 지배적 인 세트를 만듭니다.