MST를 이루는 집합에서 최단 거리가 있다.. 뭐 이런 말씀인 거 같은데. 일단 이 명제 먼저 봅시다.

이거 반례 있어요.

양방향 그래프라고 가정합시다.

1에서 2를 연결하는 cost = 3

1에서 3을 연결하는 cost = 5

2에서 3을 연결하는 cost = 4

일단 MST는 1-2인 (3), 2-3인 (4)로 이루어져 있지만.. 사실 1에서 3까지 가는 최단 코스트는 MST 위에 있지 않죠.

최단 거리면 MST다. 이거 역시 같은 그래프로 들어봅시다.

1에서 2를 연결하는 cost = 3

1에서 3을 연결하는 cost = 5

2에서 3을 연결하는 cost = 4

그러면 1에서 2까지 최단 거리는 3, 1에서 3까지 거리는 5, 2에서 3까지 거리는 4네요?

그런데. 이것들을 모두 뽑으면.. 사이클이 나오는군요.

지금 MST하고 최단 거리.. 이게 헷갈리시는 거 같아요.. 다른 개념이에요~

아...그렇군요 완전히 다르게 봐야하는군요.. 감사합니다!!!

뭔가 알 거 같은데 증명이 잘 안 되시는 거 같은데..

최악의 경우를 인위적으로 만들어버리면 됩니다. 반례를 쉽게 찾으시려면..

굉장한 학생도 명제에 대한 질문이 들어왔는데..

시간이 나신다면 그 문제를 푸시지는 못하시더라도.. 문제가 의미하는 게 뭔지 보시는 것도 괜찮을 거 같아요.

어려워요.. 명제..

둘이 완전히 달라요..!!

살짝ㄱ..이런 느낌..??

검정색이 그래프..!

빨간색이 거리

파란색이 MST

보라색은 1에서 5까지의 최단거리..

보라색과 파란색을 보면 굳이 MST 위에 있지 않아도 최단거리가 될수 있어요..!

최소 스패닝 트리MST는 그냥ㅇ n개의 점을 잇는데 필요한 최소한의 거리 가중치 랄까///

쨋든 그냥 아예 다른... 거에요..!

멋진 그림 설명 감사합니다^^