11. 고급 그래프 알고리즘 (Advanced Graph Algorithms)

핵심 인사이트 (3줄 요약)

본질: 고급 그래프 알고리즘은 최단 경로·최소 신장 트리를 넘어 최대 유량(Max Flow)·이분 매칭(Bipartite Matching)·강연결 요소(SCC)·위상 정렬 등 복잡한 실세계 문제를 그래프 모델로 해결하는 알고리즘 체계다.

가치: 네트워크 흐름(물류·통신 용량), 작업 스케줄링(의존성 그래프), 소셜 네트워크 분석(커뮤니티 탐지) 등 기업 IT 시스템의 핵심 최적화 문제가 그래프 알고리즘으로 귀결된다.

판단 포인트: 최대 유량 ≡ 최소 절단(Max-Flow Min-Cut 정리)은 용량 최적화 문제의 핵심이며, 위상 정렬(Topological Sort)은 의존성 있는 작업 순서 결정(빌드 시스템·패키지 관리자)의 표준 해법이다.

Ⅰ. 최대 유량 (Maximum Flow)

Ford-Fulkerson 알고리즘

소스(s) → 싱크(t)로 흐를 수 있는 최대 유량 찾기

잔여 그래프(Residual Graph) 개념:
  실제 용량 c(u,v)에서 현재 흐름 f(u,v)를 뺀 잔여 용량
  역방향 간선: f(v,u) = -f(u,v) (흐름 취소 가능)

증가 경로(Augmenting Path) 반복:
  BFS/DFS로 s → t 경로 탐색
  최소 잔여 용량만큼 흐름 추가
  종료: 더 이상 증가 경로 없음 → 최대 유량 달성

시간 복잡도:
  Ford-Fulkerson: O(E·f*)  [f*: 최대 유량값]
  Edmonds-Karp (BFS 사용): O(V·E²)
  Dinic: O(V²·E)  — 실무 권장

Max-Flow Min-Cut 정리

최대 유량(Max Flow) = 최소 절단(Min Cut)

절단(Cut): 그래프를 s 포함 집합 S, t 포함 집합 T로 분리하는 간선 집합
최소 절단: 용량 합이 최소인 절단 = 네트워크의 병목

응용:
  - 네트워크 최대 처리량 계산
  - 도로 교통 병목 구간 식별
  - 이미지 분할 (Graph Cuts)

📢 섹션 요약 비유: 최대 유량은 '파이프 네트워크에서 수도꼭지에서 배수구로 흐를 수 있는 최대 물의 양' 입니다. 가장 좁은 파이프(최소 절단)가 전체 흐름의 병목이 됩니다.

Ⅱ. 이분 매칭 (Bipartite Matching)

이분 그래프 (Bipartite Graph):
  두 집합 A, B로 분리되고 A-B 간선만 존재

최대 이분 매칭:
  A의 각 노드를 B의 노드에 1:1 최대 매칭

알고리즘:
  - 헝가리안 알고리즘: O(V³) — 최소 비용 완전 매칭
  - 홉크로프트-카프: O(E√V) — 최대 이분 매칭

응용:
  - 구직자 ↔ 채용 공고 매칭
  - 의대생 ↔ 병원 배정 (NRMP 알고리즘)
  - 작업 ↔ 작업자 할당

📢 섹션 요약 비유: 이분 매칭은 '결혼 중매' 와 같습니다. 남성 집합과 여성 집합이 있고, 서로 원하는 조합이 있을 때 최대 몇 쌍이 매칭될 수 있는지 찾는 알고리즘입니다.

Ⅲ. 강연결 요소 (Strongly Connected Components, SCC)

SCC: 방향 그래프에서 모든 정점 쌍 (u, v)에 대해
     u → v, v → u 경로가 모두 존재하는 최대 부분 그래프

알고리즘:
  Tarjan's: O(V+E) — DFS + 스택 기반
  Kosaraju's: O(V+E) — 두 번의 DFS

응용:
  - 웹 페이지 링크 구조 분석 (PageRank 전처리)
  - 소셜 네트워크 커뮤니티 탐지
  - 컴파일러 의존성 분석

Ⅳ. 위상 정렬 (Topological Sort)

DAG(Directed Acyclic Graph, 유향 비순환 그래프)에서
모든 간선 (u→v)에 대해 u가 v보다 먼저 오는 순서

알고리즘:
  ① Kahn's Algorithm (BFS 기반): 진입 차수 0인 노드부터
  ② DFS 기반: DFS 완료 역순

응용:
  - 빌드 시스템 (Makefile, Bazel): 컴파일 순서 결정
  - 패키지 관리자 (npm, pip): 의존성 설치 순서
  - 강의 선수 과목 이수 순서
  - 태스크 스케줄링 (DAG 파이프라인)

📢 섹션 요약 비유: 위상 정렬은 '선수 과목 이수 순서' 와 같습니다. "자료구조를 들어야 알고리즘을 들을 수 있다"는 의존 관계가 있을 때, 모든 과목을 순서대로 나열하는 것입니다.

Ⅴ. 기대효과 및 결론

고급 그래프 알고리즘은 실세계 복잡한 최적화 문제를 수학적으로 명확히 표현하고 효율적으로 해결하는 강력한 도구다. AWS의 마이크로서비스 의존성 관리, LinkedIn의 인맥 추천, 구글 지도의 교통 최적화 모두 그래프 알고리즘에 기반한다.

📌 관련 개념 맵

개념	연결 포인트
Max-Flow Min-Cut	네트워크 병목 탐지; 최대 유량 = 최소 절단
이분 매칭	헝가리안 알고리즘; 최소 비용 완전 매칭
SCC (타잔 알고리즘)	방향 그래프 커뮤니티 탐지; PageRank 전처리
위상 정렬	DAG 의존성 해결; 빌드·패키지 시스템 표준
유니온-파인드 (DSU)	크루스칼 MST 구현; 사이클 탐지

📈 관련 키워드 및 발전 흐름도

기본 그래프 탐색 (BFS / DFS)
    │
    ▼
최단 경로 (Dijkstra · Bellman-Ford · Floyd-Warshall)
    │
    ▼
최소 신장 트리 (Kruskal · Prim)
    │
    ▼
고급 그래프 알고리즘
    ├─► 최대 유량 (Ford-Fulkerson · Dinic)
    ├─► 이분 매칭 (Hungarian · Hopcroft-Karp)
    ├─► SCC (Tarjan · Kosaraju)
    └─► 위상 정렬 (Kahn's · DFS)
    │
    ▼
그래프 신경망 (GNN) — 그래프 구조 딥러닝

👶 어린이를 위한 3줄 비유 설명

최대 유량은 '수도관 네트워크에서 물이 최대 얼마나 흐를 수 있는지' 찾는 거예요. 가장 좁은 파이프가 전체 물의 양을 결정해요!
위상 정렬은 '선수 과목 순서대로 수업 듣기' 와 같아요. 수학을 배워야 물리를 배울 수 있으니, 순서를 지켜야 해요.
고급 그래프 알고리즘은 배달 경로 최적화, 병원 의사 배정, SNS 친구 추천 등 실생활의 복잡한 문제를 수학으로 해결하는 마법이에요!