Page 10 -

15장 그래프(3): 최소 신장 트리 문제 323

15.1 최소 신장 트리 문제란? 324
15.2 크러스컬 알고리즘 325
15.3 크러스컬 알고리즘 구현 327

15.4 신장 트리 구조 330
15.4.1 컷 330
15.4.2 기본 사이클 330
15.4.3 기본 컷 집합 332
15.5 크러스컬 알고리즘의 정확성(*) 332
15.6 정리 336

15.7 연습 문제 336

16장 그래프(4): 네트워크 흐름 337

16.1 네트워크 흐름을 배우는 의의 338
16.2 그래프 연결도 338
16.2.1 변 연결도 339
16.2.2 최소 컷 문제 340
16.2.3 변 연결도를 구하는 알고리즘과 강 쌍대성 증명 341
16.3 최대 흐름 문제와 최소 컷 문제 344
16.3.1 최대 흐름 문제란? 344
16.3.2 흐름의 성질 345
16.3.3 최소 컷 문제와 쌍대성 346
16.3.4 포드-풀커슨 알고리즘 348
16.4 포드-풀커슨 알고리즘 구현 351

16.5 응용 예(1): 이분 매칭 355
16.6 응용 예(2): 점 연결도 357
16.7 응용 예(3): 프로젝트 선택 문제 358

16.8 정리 361
16.9 연습 문제 362
026