7. Graphenalgorithmen (8 Punkte)

7.2 · 굵은 간선 집합이 크루스칼(Kruskal)·프림(Prim) 중 어디서 나왔는지 판별하기

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

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

자료의 성격과 정확성 경계

시험 문언과 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\|))`라 거의 선형이다.

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

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

필요한 개념을 깊게 배우기

초보자용 연결 강의

이 소문제를 왜 배우나

이 문제는 최종 MST를 계산하는 문제가 아니라, 보이는 굵은 edge set이 어떤 greedy 실행의 ‘중간 사진’이 될 수 있는지 역으로 추론하는 문제다. Kruskal의 전역 정렬과 Prim의 현재 cut이라는 서로 다른 시야를 구분해야 네 패널을 정확히 분류할 수 있다.

cut, crossing edge, light edge, safe edge를 작은 그래프에서 정의하고 cut property의 교환 직관을 설명할 수 있다.
Kruskal의 중간 결과는 forest일 수 있지만 Prim의 중간 결과는 한 connected tree라는 차이를 사용할 수 있다.
가능하다고 주장할 때 실제 edge 처리 순서 또는 Prim 시작점·cut 순서를 certificate로 제시할 수 있다.
불가능하다고 주장할 때 cycle, 누락된 더 가벼운 edge, 더 싼 crossing edge 중 하나의 구체 반례를 제시할 수 있다.

풀이 전에 꼭 알아야 할 말

cut(Schnitt)과 crossing edge

cut (S,V−S)는 모든 vertex를 S와 그 밖의 V−S 두 편으로 나눈 것이다. 한 endpoint가 S, 다른 endpoint가 V−S에 있는 edge가 그 cut을 건너는 crossing edge다.

아주 작은 예: \(S=\{A,B\}\)S={A,B}라면 A-E는 crossing edge이고 A-B는 S 내부 edge라 crossing이 아니다.

light edge와 safe edge

light edge는 한 cut을 건너는 edge 중 weight가 최소인 edge다. 현재 선택 집합 A를 깨지 않는 cut의 light edge는 A를 어떤 MST로 계속 확장할 수 있게 하는 safe edge다.

아주 작은 예: crossing weights가 3,6,9라면 weight 3 edge가 light edge이고 greedy가 먼저 선택해도 안전하다.

cut property의 교환 직관

어떤 MST가 우리가 고른 light edge를 쓰지 않더라도, 그 MST가 같은 cut을 건너는 더 무겁거나 같은 edge 하나를 light edge로 바꾸면 연결과 edge 수를 유지하면서 비용이 커지지 않는다.

아주 작은 예: 기존 tree가 cut을 weight 6으로 건너면 weight 3 crossing edge로 교체해 더 비싸지 않은 spanning tree를 만든다.

Prim key와 predecessor

Prim에서 key[v]는 시작점부터 누적 거리값이 아니라 현재 tree S에서 바깥 vertex v를 붙일 수 있는 가장 싼 edge 하나의 weight다. pred[v]는 그 edge의 S 쪽 endpoint다.

아주 작은 예: 현재 S에서 G로 가는 edge가 weight 1과 6이면 \(\text{key}[G]=1\)key[G]=1이고 pred[G]는 weight 1 edge의 안쪽 정점이다.

도시 전체 구매 목록과 현재 공사 구역의 경계

Kruskal 담당자는 도시 전체 계약서를 가격순으로 펼쳐 놓고 가장 싼 안전 공사를 처리한다. Prim 담당자는 이미 전기가 들어온 한 덩어리의 공사 구역만 보고 그 경계를 넘는 가장 싼 공사를 선택한다. 같은 굵은 선 사진이라도 두 담당자의 규칙을 각각 재생해 봐야 출처를 알 수 있다.

도시 전체 가격순 계약서

↔

Kruskal의 global nondecreasing edge order

현재 전기가 들어온 한 덩어리

↔

Prim의 connected partial tree S

구역 경계를 넘는 가장 싼 공사

↔

Prim cut의 light crossing edge

가능한 공사 일지

↔

알고리즘 가능성을 증명하는 edge-order certificate

비유의 한계: 실제 공사는 여러 계약을 동시에 할 수 있지만 두 알고리즘은 한 단계에 edge 하나를 선택하며, 문제의 굵은 집합은 그 순차 실행을 일찍 멈춘 결과다.

패널마다 적용하는 판별 필터

1. cycle?굵은 edge만으로 cycle이면 즉시 Keine다.

2. connected?disconnected면 Prim은 불가능하지만 Kruskal forest는 가능하다.

3. Kruskal replay모든 더 가벼운 edge가 선택 또는 당시 cycle로 거절 가능한지 본다.

4. Prim replayroot와 순서를 잡아 매 단계 cut-minimum edge인지 본다.

cycle 검사는 두 알고리즘을 동시에 탈락시키고, disconnected 검사는 Prim만 탈락시킨다. 그 뒤 Kruskal에는 전역 weight prefix, Prim에는 시작점부터의 cut-minimum certificate를 요구한다.

먼저 작은 예제로 연습 · Kruskal만 가능한 두 조각

vertices={a,b,c,d}, edges ab:1, cd:2, bc:5라고 하고 굵은 edge가 ab와 cd라고 하자.

cycle부터 검사

ab와 cd는 서로 떨어진 두 edge라 cycle이 없다. 따라서 Beide/하나/Keine 판정을 계속해야 한다.

굵은 \(\text{forest}={\text{ab}},{\text{cd}}\)forest={ab},{cd}

Kruskal을 재생

전역 weight 1의 ab와 2의 cd는 서로 다른 component를 이어 차례로 선택된다. 두 번째 선택 직후 멈출 수 있다.

Kruskal possible: \(\text{ab} \to \text{cd}\)ab → cd

Prim을 재생

Prim은 한 root에서 시작해 매번 새 vertex를 현재 tree에 붙인다. 떨어진 ab와 cd 두 조각을 중간 결과로 만들 수 없다.

Prim impossible: highlighted set disconnected

작은 예제의 결론: Kruskal은 가능하고 Prim은 불가능하므로 가장 정확한 답은 Kruskal이다. 단순히 cycle이 없다는 이유만으로 Beide라고 하면 안 된다.

이제 실제 시험 문제에 연결

굵은 집합이 cycle이면 왜 두 알고리즘 모두 불가능한가?

Kruskal은 같은 component를 잇는 edge를 거절하고, Prim은 매 단계 바깥의 새 vertex를 한 개 붙이므로 둘 다 accepted edge로 cycle을 만들지 않는다. 따라서 cycle 하나가 완전한 Keine certificate다.

disconnected이면 왜 Kruskal은 여전히 가능한가?

Kruskal은 그래프 전체에서 싼 edge를 보므로 서로 멀리 떨어진 여러 component를 동시에 키울 수 있다. 반면 Prim은 root에서 시작한 하나의 connected tree만 확장하므로 disconnected 굵은 집합은 만들 수 없다.

Kruskal 가능성은 어떻게 증명하나?

edge를 weight 오름차순으로 실제 나열하고, 굵은 edge는 다른 component라 accept, 빠진 더 가벼운 edge는 그 시점에 이미 같은 component라 reject됨을 보여 준다. 단순히 굵은 edge weight만 보는 것은 부족하다.

Prim 가능성은 어떻게 증명하나?

가능한 root를 하나 정한 뒤 현재 S, crossing candidates와 weights, 선택 edge를 단계별로 적는다. 매 단계 선택 edge가 최소 crossing weight이고 새 vertex를 붙이면 valid Prim certificate다.

Beide는 언제 쓰나?

같은 굵은 집합에 대해 Kruskal certificate와 Prim certificate가 모두 존재할 때만 Beide다. 한 알고리즘이 가능하다는 사실이 다른 알고리즘 가능성을 자동으로 뜻하지 않는다.

답이 맞는지 스스로 검산

각 패널에서 굵은 edge의 cycle과 connected component 수를 먼저 손으로 확인한다.
Kruskal possible에는 nondecreasing 처리 순서를, impossible에는 반드시 포함돼야 할 누락 edge 또는 순서 위반을 적는다.
Prim possible에는 root·cut-minimum 순서를, impossible에는 disconnected 또는 더 싼 crossing edge를 적는다.
최종 label이 두 가능성의 조합과 일치하는지 확인한다: \(\text{TT}=\text{Beide}, \text{TF}=\text{Kruskal}, \text{FT}=\text{Prim}, \text{FF}=\text{Keine}.\)TT=Beide, TF=Kruskal, FT=Prim, FF=Keine.

30초 자가점검

connected이고 cycle이 없는 굵은 tree면 무조건 Prim 가능한가?

힌트: 모양뿐 아니라 매 단계 crossing edge의 weight를 본다.

정답: 아니다. 어떤 순서에서도 더 싼 crossing edge를 건너뛰어야 한다면 Prim은 불가능하다.

disconnected 굵은 forest가 Keine가 아닌 이유는?

힌트: 두 알고리즘 중 여러 조각을 동시에 키울 수 있는 쪽을 생각한다.

정답: Kruskal은 전역에서 edge를 처리하므로 여러 component인 중간 forest를 만들 수 있다.

연습: 굵은 edge가 triangle 세 변이면 답은 무엇인가?

힌트: 가장 먼저 cycle 필터를 적용한다.

정답: Keine다. Kruskal과 Prim 모두 accepted edge 중간 결과에 cycle을 만들 수 없다.

마지막에 쓰는 시험 답안 틀

각 그림마다 (1) cycle이면 Keine, (2) disconnected면 Prim 제외, (3) Kruskal은 빠진 더 가벼운 간선이 당시 cycle로 거절 가능했는지 확인, (4) Prim은 가능한 시작점과 순서를 잡아 매 단계 cut-minimum인지 확인한다. 두 가능성을 조합해 Kruskal/Prim/Beide/Keine 중 가장 정확한 하나를 쓴다.

자주 하는 실수

굵은 간선이 connected이면 곧바로 Prim이라고 한다. cut-minimum 조건도 필요하다.
굵은 간선이 disconnected이면 Keine라고 한다. Kruskal의 중간 forest일 수 있다.
최종 spanning tree가 아니므로 둘 다 아니라고 한다. 문제는 조기 종료를 명시적으로 허용한다.
Kruskal이 현재 component와 맞닿은 간선만 본다고 착각한다. 그것은 Prim 쪽 사고방식이다.
Prim이 그래프 전체의 최솟값을 반드시 고른다고 착각한다. 현재 cut을 가로지르는 간선 중 최솟값만 고른다.
둘 다 가능하지만 Kruskal 또는 Prim 하나만 적는다. 원문은 Beide를 요구한다.
네 패널이면 Kruskal·Prim·Beide·Keine가 반드시 한 번씩 나온다고 가정한다. 실제 복원 패널은 Beide, Kruskal, Keine, Keine이며 Prim-only 패널이 없다.

근거와 정확성 범위

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

복기 시험 문언AuD Gedächtnisprotokoll SoSe 2025.md · lines 297-319 · 신뢰도/범위: 비공식 복기이며 공식 문제지·공식 답안 아님
7.1 간선표와 정답 행, 7.2 문제 문언 및 조기 종료 허용
강의 직접 근거Vorlesung\06GraphAlgorithms.pdf · pp.82-90 (MST·cut), pp.92-106 (Kruskal), pp.107-117 (Prim) · 신뢰도/범위: 현재 강의 자료
MST 정의, 두 greedy 알고리즘과 정확성 근거
공식 연습 풀이Übung\AuD26_Sheet10-Sol.pdf · pp.1-5 and pp.13-14 · 신뢰도/범위: 공식 연습 풀이
현재 강의의 Prim/Kruskal 표 작성 방식과 상세 실행 설명
공식 연습 문제Übung\AuD26_Sheet10.pdf · G2-G3 · 신뢰도/범위: 공식 연습 문제
Prim과 Kruskal 손실행 연습 형식

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