7. Graphenalgorithmen (8 Punkte)

7.1 · 크루스칼(Kruskal) 표를 한 줄도 빠짐없이 완성하기

선행지식이 전혀 없어도 이 페이지 하나에서 용어를 배우고, 작은 예제를 거쳐 실제 시험 풀이와 검산까지 따라가도록 구성했습니다.

  1. 용어: 기호와 전제
  2. 직관: 비유와 작은 예
  3. 풀이: 실제 상태 변화
  4. 확인: 검산과 자가점검

자료의 성격과 정확성 경계

시험 문언과 7.1 표는 `AuD Gedächtnisprotokoll SoSe 2025.md` lines 297-319에서 왔다. 이 파일은 비공식 복기다. MST 정의·cut property·Kruskal·Prim은 `Vorlesung\06GraphAlgorithms.pdf` pp.82-117로 검산했고, 표 작성과 네 유형의 비교는 `Übung\AuD26_Sheet10-Sol.pdf` pp.1-5, 13-14를 보조 근거로 사용했다.

문제를 읽기 전에 알아둘 기호와 용어

기호를 모른 채 풀이를 외우지 않도록, 이 문제에서 실제로 쓰는 뜻과 작은 예를 먼저 확인합니다.

기호·용어뜻작은 예
\(G=(V,E)\)G=(V,E)V는 vertex(정점) 집합, E는 두 정점을 잇는 edge(간선) 집합이다.7.1에서는 \(V=\{a,b,c,d,e,f\}\)V={a,b,c,d,e,f}이고 \(\{a,b\}\in E\){a,b}∈E다.
항목 (w({u,v}))간선 {u,v}를 선택할 때 더해지는 비용 또는 가중치다.\(w(\{a,b\})=1\)w({a,b})=1이고 선택 간선의 weight를 모두 더해 MST 비용 27을 얻는다.
항목 (A)알고리즘이 지금까지 선택한 간선 집합이며, 실행 중에는 forest이고 끝에는 spanning tree가 된다.첫 행 뒤 \(A=\{\{a,b\}\}\)A={{a,b}}이고 일곱 번째 행 뒤 선택 간선이 5개다.
항목 (set(v))현재 선택 간선만 따라 v에서 도달할 수 있는 모든 정점, 즉 v의 connected component다.a-b와 b-c를 골랐다면 \(\text{set}(a)=\text{set}(b)=\text{set}(c)=\{a,b,c\}\)set(a)=set(b)=set(c)={a,b,c}다.
\(\text{Dazu}? / \text{ja} / \text{nein} / =\)Dazu? / ja / nein / =Dazu?는 추가 여부, ja는 선택, nein은 거절, =는 바로 윗행의 셀 값을 그대로 복사한다는 시험 표기다.{a,c}는 같은 component를 이으므로 nein이고 모든 set 셀은 =다.
항목 ((S,V−S))정점 집합을 두 편으로 나눈 cut이며, 한 끝점이 S에 있고 다른 끝점이 V−S에 있으면 그 edge가 cut을 건넌다.Prim에서 현재 tree 정점 S와 아직 밖의 정점 V−S 사이 최소 edge를 고른다.
랭크(rank, Union-Find)Union-Find 내부 tree의 높이에 대한 상한 표식이다. 두 component를 합칠 때 rank가 작은 root를 큰 root 아래에 붙여 tree가 길게 늘어지는 것을 막는다.서로 다른 두 singleton의 rank가 같다면 하나를 다른 하나 밑에 붙이고 새 root의 rank를 1 올린다.
항목 (α(|V|), amortized)α는 inverse Ackermann 함수로 현실적인 입력에서 5보다도 작게 자라는 매우 느린 함수다. amortized는 한 번의 최악이 아니라 긴 연산열 전체 비용을 연산 수로 나눈 보장이라는 뜻이다.path compression과 union by rank를 함께 쓰면 E번의 Find/Union 총비용이 \(O(|E|α(|V|))\)O(|E|α(|V|))라 거의 선형이다.

먼저 문제의 정체를 줄글로 이해하기

아래 선수 개념부터 차례대로 읽으면 실제 문제의 요구를 이해할 수 있습니다.

필요한 개념을 깊게 배우기

초보자용 연결 강의

이 소문제를 왜 배우나

Kruskal 표는 단순 암기 문제가 아니라 ‘현재 연결 상태’를 한 행씩 갱신하는 훈련이다. 이 원리를 이해하면 어떤 가중 그래프에서도 cycle을 만들지 않으면서 최소 비용 연결망을 구성하고, 시험 표의 ja·nein·=를 근거와 함께 채울 수 있다.

풀이 전에 꼭 알아야 할 말

path(경로)와 cycle(순환)

path는 이웃한 edge를 차례로 따라가는 정점 열이다. cycle은 시작 정점으로 다시 돌아오되 중간 정점을 반복하지 않는 닫힌 path다. 선택 edge에 cycle이 생기면 그중 하나를 빼도 연결이 유지되므로 spanning tree가 될 수 없다.

아주 작은 예: a-b와 b-c가 있으면 a-b-c는 path다. 여기에 c-a를 더하면 a-b-c-a cycle이 된다.

핵심 학습 항목 (tree, forest, spanning tree)

tree는 connected이면서 cycle이 없는 graph다. forest는 서로 떨어진 tree가 여러 개일 수 있는 acyclic graph다. spanning tree는 원래 graph의 모든 vertex를 포함하는 tree이며 |V|개 정점에 정확히 |V|-1개 edge가 있다.

아주 작은 예: {a,b}와 {c,d} 두 edge는 forest다. 여기에 {b,c}를 더하면 네 정점을 잇는 spanning tree가 된다.

component와 DSU(Union-Find)

component는 현재 선택 edge로 서로 오갈 수 있는 정점 묶음이다. DSU는 MakeSet으로 singleton을 만들고, Find로 두 정점의 대표가 같은지 검사하며, Union으로 서로 다른 두 component를 합치는 자료구조다.

아주 작은 예: Find(a)≠Find(b)이면 {a,b}를 고른 뒤 Union(a,b)를 수행해 \(\text{set}(a)=\text{set}(b)=\{a,b\}\)set(a)=set(b)={a,b}로 만든다.

핵심 학습 항목 (MST(minimaler Spannbaum))

connected undirected weighted graph의 모든 정점을 잇는 spanning tree 중 선택 edge의 총 weight가 최소인 것이다. edge 수가 |V|-1이라는 사실만으로는 최소성을 보장하지 않으며 Kruskal의 safe-edge 규칙이 필요하다.

아주 작은 예: 정점 6개인 7.1의 MST는 edge 5개이고, 선택 \(\text{weight} 1+2+4+9+11=27\)weight 1+2+4+9+11=27이다.

단체 채팅방을 합치는 가장 싼 케이블 공사

처음에는 여섯 마을이 각각 혼자 있는 채팅방이다. 공사 후보를 가격이 싼 순서로 보고, 서로 다른 채팅방을 잇는 케이블이면 계약해 두 방을 합친다. 이미 같은 방 사람 둘을 또 잇는 케이블은 새 마을을 연결하지 않고 고리만 만들므로 거절한다.

마을 한 곳
↔
vertex 한 개
같은 채팅방의 마을들
↔
현재 connected component, 즉 set(v)
두 채팅방을 합치는 케이블
↔
다른 component를 잇는 accepted edge와 Union
이미 같은 방을 다시 잇는 불필요한 고리
↔
same-component edge가 만드는 cycle

비유의 한계: 실제 통신망에는 용량·고장 대비·방향 같은 조건이 있을 수 있지만 이 문제는 오직 undirected edge의 weight 합과 연결 여부만 비교한다.

한 행에서 머릿속으로 보는 네 칸

1. edge와 weight아직 처리하지 않은 가장 가벼운 edge {u,v}를 본다.
2. Find 비교set(u)와 set(v)가 같은지 확인한다.
3. ja 또는 nein다르면 ja+Union, 같으면 cycle이므로 nein이다.
4. 새 상태모든 set, forest A, running weight를 기록한다.

매 행은 ‘edge를 본다 → 두 component를 비교한다 → 선택 또는 거절한다 → 상태와 누적 비용을 갱신한다’의 같은 순서다. weight는 처리 순서를 정하고, ja/nein은 component 비교가 정한다.

먼저 작은 예제로 연습 · 세 정점 a,b,c와 edge 1,2,3

vertices={a,b,c}, edges={a,b}:1, {b,c}:2, {a,c}:3이라고 하자. 처음에는 A=∅이고 세 정점이 각각 singleton component다.

{a,b}:1을 선택

\(\text{set}(a)=\{a\}, \text{set}(b)=\{b\}\)set(a)={a}, set(b)={b}로 서로 다르므로 cycle 없이 두 component를 합칠 수 있다.

\(A=\{\{a,b\}\}, \text{components}=\{a,b\}|\{c\}, \text{running} \text{weight}=1\)A={{a,b}}, components={a,b}|{c}, running weight=1
{b,c}:2를 선택

b는 {a,b}, c는 {c}에 있어 서로 다른 component다. Union 후 모든 정점이 연결된다.

\(A=\{\{a,b\},\{b,c\}\}, \text{components}=\{a,b,c\}, \text{running} \text{weight}=3\)A={{a,b},{b,c}}, components={a,b,c}, running weight=3
{a,c}:3을 거절

a와 c는 이미 a-b-c path로 연결되어 있다. 추가하면 a-b-c-a cycle이 생긴다.

A 변화 없음, \(\text{components}=\{a,b,c\}, \text{running} \text{weight}=3\)components={a,b,c}, running weight=3

작은 예제의 결론: 정점 3개에 선택 edge 2개가 있고 connected·acyclic이므로 spanning tree다. 정렬 순서에서 safe edge만 골랐으므로 Kruskal이 만든 MST이며 비용은 3이다.

이제 실제 시험 문제에 연결

실제 표를 시작하기 전에 무엇을 적어야 하나?

행 0에 A=∅, running weight=0, set(a)={a}, set(b)={b}, …, \(\text{set}(f)=\{f\}\)set(f)={f}를 적는다. 이 초기 상태가 없으면 첫 Union과 이후 = 표기의 기준을 잃는다.

{a,c}:5가 작아 보이는데 왜 nein인가?

그 행이 오기 전에 {a,b}와 {b,c}가 선택되어 a-b-c path가 이미 있다. 따라서 \(\text{set}(a)=\text{set}(c)=\{a,b,c,d\}\)set(a)=set(c)={a,b,c,d}이고 {a,c}를 더하면 a-b-c-a cycle이 생긴다. 절대 weight가 아니라 현재 component가 결정한다.

{d,e}:11은 더 비싼데 왜 ja인가?

d는 {a,b,c,d}, e는 {e,f}에 있어 서로 다른 두 component를 잇는다. 지금까지 처리한 더 가벼운 edge로는 이 두 묶음을 연결할 수 없었으므로 이 edge가 필요한 safe edge다.

edge 5개를 고른 뒤에도 왜 두 행을 더 쓰나?

알고리즘의 MST는 완성됐지만 원문이 표의 모든 행을 채우라고 요구한다. {d,f}:12와 {c,e}:16은 같은 component를 이으므로 nein이고, 변하지 않는 set 칸에는 =를 쓴다.

이 spanning tree가 왜 minimum인가?

Kruskal은 각 component를 나누는 cut에서 아직 가능한 가장 가벼운 crossing edge를 선택한다. cut property에 따라 그런 light edge는 어떤 MST로 확장 가능한 safe edge이므로, 모든 선택을 반복한 최종 tree는 MST다.

답이 맞는지 스스로 검산

  • 구조 검산: a,b,c,d,e,f가 하나의 component이고 선택 edge 수가 \(5=|V|-1\)5=|V|-1이며 선택 과정에 cycle이 없다.
  • 비용 검산: accepted weight만 더해 \(1+2+4+9+11=27\)1+2+4+9+11=27이고 rejected 5,6,12,16은 더하지 않았다.
  • 최소성 검산: 각 accepted edge가 처리 당시 서로 다른 component를 잇는 정렬 순서상의 light/safe edge였는지 확인한다.
  • 표 형식 검산: 초기 row와 남은 두 rejected row를 포함해 모든 행, \(\text{ja}/\text{nein}, =\)ja/nein, =또는 expanded set을 빠짐없이 기록한다.

30초 자가점검

{a,c}:5를 선택하면 생기는 cycle을 정점 순서로 쓰라.

힌트: 이미 선택된 a-b와 b-c를 따라가 본다.

정답: a-b-c-a cycle이다. a와 c가 같은 component이므로 {a,c}는 nein이다.

{e,f}:9 행 직후 component와 누적 weight는 무엇인가?

힌트: 앞의 accepted weight 1,2,4에 9를 더한다.

정답: components는 {a,b,c,d}와 {e,f}, running weight는 \(1+2+4+9=16\)1+2+4+9=16이다.

연습: vertices p,q,r,s와 pq1, rs2, qr4, ps5를 Kruskal로 처리하라.

힌트: 처음 두 edge는 서로 떨어진 두 component를 만든다.

정답: pq1 ja, rs2 ja, qr4 ja로 모든 정점을 연결하고 ps5는 같은 component라 nein이다. MST weight는 7이다.

실제 문제의 상태 변화를 한 단계씩 재현하기

각 단계에서 무엇을 했는지, 왜 그렇게 했는지, 결과가 무엇인지 차례대로 확인합니다.

  1. 단계 1

    a와 b는 서로 다른 singleton component다. 선택해도 cycle이 없으므로 합친다.

  2. 단계 2

    b는 {a,b}, c는 {c}에 있다. 다른 component를 연결하므로 선택한다.

  3. 단계 3

    b는 {a,b,c}, d는 {d}에 있다. 서로 다른 component이므로 선택한다.

  4. 단계 4

    a와 c는 이미 {a,b,c,d} 안에서 a-b-c 경로로 연결되어 있다. 추가하면 a-b-c-a cycle이 생긴다.

  5. 단계 5

    c와 d도 이미 같은 component다. 추가하면 c-b-d-c cycle이 생긴다.

  6. 단계 6

    e와 f는 각각 singleton이다. 다른 component를 잇기 때문에 선택한다.

  7. 단계 7

    d는 {a,b,c,d}, e는 {e,f}에 있다. 두 큰 component를 잇는 첫 간선이므로 선택한다. 이제 모든 정점이 하나로 합쳐진다.

  8. 단계 8

    이미 모든 정점이 같은 component다. d와 f를 더 이으면 cycle이 생긴다. 시험 표가 계속되므로 행은 끝까지 채운다.

  9. 단계 9

    c와 e도 같은 component다. 역시 cycle이므로 거절한다.

마지막에 쓰는 시험 답안 틀

간선을 가중치 오름차순으로 처리한다. Find(u)≠Find(v)이면 ja 후 Union, 같으면 cycle이므로 nein이다. 선택 간선은 {a,b},{b,c},{b,d},{e,f},{d,e}, 총가중치는 27이다. 이후 {d,f},{c,e}도 같은 component이므로 nein과 =로 끝까지 기록한다.

자주 하는 실수

근거와 정확성 범위

복기 문언, 강의 정의, 공식 연습 풀이, 추가 유도를 구분해 표시합니다.

마지막 생성: 2026-08-02 08:51