# MST

• 2026년 5월 27일 알고리즘
  Prim·Kruskal은 모든 MST를 찾을 수 있는가

  같은 그래프에 여러 MST가 나올 수 있다. 동률 간선이 같은 자리를 두고 맞설 때 갈림이 생기는 조건을 짚고, 목표 MST를 정해 그것을 출력하게 하는 선택 규칙을 Prim과 Kruskal 각각에 대해 구성해 두 알고리즘이 모든 MST에 도달함을 보인다. 가중치가 모두 다르면 MST가 유일함도 증명한다.

• 2026년 5월 26일 알고리즘
  Kruskal 알고리즘 — 그리디로 MST를 만든다

  Kruskal 알고리즘으로 최소 신장 트리(MST)를 구성한다. 가장 작은 간선부터 그리디하게 고르는 전략이 왜 최적인지 컷 기반 교환 논법으로 증명하고, Union-Find로 사이클 검사를 거의 상수 시간에 처리해 O(m log m)으로 마무리한다.

• 2026년 5월 23일 알고리즘
  프림 알고리즘 (Prim) — MST를 찾는 그리디 전략

  프림 알고리즘은 하나의 정점에서 시작해 현재 트리 안과 밖을 가르는 간선 중 가장 가벼운 것을 반복적으로 추가하여 MST를 만든다. 알고리즘의 동작을 단계별로 살펴보고, 매 단계 선택이 항상 어떤 MST의 부분집합에 포함된다는 사실을 귀납법과 사이클 논증으로 증명한다.

• 2026년 5월 23일 알고리즘
  최소 신장 트리 (MST) — 정의와 성질

  최소 신장 트리(MST)는 가중 연결 그래프에서 모든 정점을 잇는 간선 가중치 합이 최소인 부분 그래프다. MST가 왜 트리여야 하는지, 정확히 n−1개 간선을 갖는 이유를 증명하고, MST가 유일하지 않을 수 있는 경우를 정리한다.