맞습니까? 모든 모서리 가중치가 양수이면 모든 정점을 연결하고 최소 총 가중치를 갖는 모든 것이 최소 스패닝 트리 여야합니까?

Question

이 문제는에 소개의 운동 23.1-7에서 진화되었습니다.

원래 문제이다

23.1-7

그래프의 모든 에지 가중치가 긍정적 인 경우, 다음 에지들의 부분 집합은 모든 꼭지점을 연결하여 트리 있어야 최소 총 중량을 갖는 것을 주장한다. 우리가 어떤 가중치를 비항 성적으로 허용한다면 동일한 결론이 따르지 않는다는 것을 보여주는 예를 든다.

그래프의 모든 에지 가중치가 양수이면 모든 꼭지점을 연결하고 최소 총 가중치를 갖는 모든 하위 집합은 최소 스패닝 트리이어야합니다.

내 결과가 맞습니까? 그렇지 않다면, 반례를 들어주세요.

Answer 1

귀하의 결과는 귀하가 증명하도록 요구하는 진술과 동일하다고 생각합니다. 스패닝 트리는 모서리의 서브 세트이므로 모든 정점이 사이클없이 연결됩니다 (따라서 트리입니다). 최소 스패닝 트리 인 경우 에지의 총중량이 최소화됩니다.

그렇습니다. 결과는 정확하지만 진술을 입증하지 않았습니다. 힌트 : 트리에는 사이클이 포함되어 있지 않으므로주기가있는 최소 총 무게로 모든 꼭지점을 연결하는 하위 세트가 있다고 가정하여 모순적 증거를 작성하십시오.