cokcjswo   5년 전

그 아이디어 대로 라면, x축에서 2개, y축에서 2개, z축에서 2개로


한 점에서 연결된 간선은 최대 6개인데, 


이 6개, 총 6 * V개의 간선으로 미니멈 스패닝 트리가 무조건 만들어진다고 증명할 수 있나요 ?


근데 그건 반대로 말하면 한 정점에 7개 이상의 점은 못 연결한다는 소리 아닌가요?


뭔가 증명할 수 있을 듯 하면서 아리송하네요. (뭔가 좌표의 정수 조건에서 비둘기집 원리 냄새가 나는 것도 같은데. ㅎ 아니면 ㅈㅅ)


ㅠㅠ...

jseo   5년 전

주어진 그래프의 MST를 T라고 합시다. 

인접하지 않은 정점 A, B가 T에서 간선으로 연결되어있다고 가정하죠.

일반성을 잃지 않고 A, B 사이에 연결된 간선 무게가 |A_x - B_x| 라고 하죠. x 축으로 A, B 사이에 있는 정점 C가 존재합니다 (A_x <= C_x <= B_x)

여기서 A, B를 연결하는 간선을 제거하고 A, C 와 C, B를 연결합니다 (이 그래프를 G라고 하죠) G는 N개의 간선으로 이루어져 있고, 연결되어있다는건 자명합니다.

그리고 총 무게 변화는 최대 -|A_x - B_x| + |A_x - C_x| + |C_x - B_x| = 0 입니다. 즉 G의 싸이클에서 간선 아무거나 지워도 T보다 총 무게가 더 작습니다.

T가 MST라는 가정이 모순되니 MST에서 연결된 정점은 인접합니다.

cokcjswo   5년 전

갑사합니다 !! 답글 주신 내용 이해 해보겠습니다 !!

gmldnjs526   9달 전

제가 정리한 내용을 공유하기 위해 남깁니다.

위의 jseo님의 논리와 핵심은 같습니다만 조금 더 풀어서 정리한 것입니다.


정답을 구성하는 터널 N-1개 중에서 어떤 한 터널을 택해서 해당 터널이 잇는 행성을 P, Q라고 하자.

정의에 의해 해당 터널의 길이는 |xP-xQ|, |yP-yQ|, |zP-zQ| 중 가장 작은 값이다.


|xP-xQ|가 해당 터널의 길이인 경우,

만약 어떤 한 행성 M의 x좌표 xM이 xP와 xQ 사이의 값이라면 다음과 같은 과정을 통해 정답보다 전체 비용 합이 더 작은 조합을 만들 수 있다.

(정답이 정답이 아님, 모순)


1. P, Q를 잇는 해당 터널을 제거한다.

전체 비용은 |xP-xQ| 감소하며, Spanning Tree에서 간선 하나를 제거한 것이므로 M은 P와 Q 중에 하나와는 연결되어 있고 다른 하나와는 연결되어 있지 않게 된다.

처음에 P, Q를 정하는 순서를 임의로 정할 수 있으므로 이때 M과 연결되어 있지 않은 행성을 P라고 하자.

2. P와 M 사이에 터널을 새로 건설한다.

정의에 의해 새로 건설한 터널의 길이는 min(|xP-xM|, |yP-yM|, |zP-zM|) 이므로 |xP-xM| 이하이다.

건설 후 Spanning Tree 조건을 만족하게 되어 다시 모든 행성이 서로 연결되며, |xP-xM| < |xP-xQ| 이므로 전체 비용 합은 처음의 정답보다 더 작아진다.


|yP-yQ|가 해당 터널의 길이인 경우,

|zP-zQ|가 해당 터널의 길이인 경우도 동일한 과정으로 모순이 도출된다.


따라서 정답을 구성하는 터널이 존재하는 축을 기준으로 봤을 때 터널로 이어지는 두 행성 사이에는 다른 행성이 존재해선 안된다.

댓글을 작성하려면 로그인해야 합니다.