목록2025/08/10 (1)
Elevation
그래프 (10) - 이분 매칭(최소 버텍스 커버, 최대 독립 집합)
이분 그래프(bipartite graph)란 정점을 두 그룹($A, B$)로 나눴을 때, $A$와 $B$ 간에만 간선이 존재하고 그룹 내부에는 간선이 존재하지 않도록 만들 수 있는 그래프를 의미한다. 어떤 그래프가 이분 그래프인지 판별하는 방법은 간단하다. 탐색을 수행하면서 정점을 빨강/파랑으로 색칠해 주는데, 빨강색 정점에 인접한 정점은 모두 파란색으로 색칠되어야 하며, 파랑색 정점에 인접한 정점은 모두 빨간색으로 색칠되어야 한다. 그렇지 않으면 이분 그래프라고 볼 수 없다. 이분 매칭(bipartite matching)은 이분 그래프에서 최대 매칭을 찾는 알고리즘이다. 매칭(matching)은 정점을 공유하지 않도록 간선을 선택하는 방법이다. 정점의 입장에서는 최대 하나의 다른 정점과 연결되도록 하는..
ps/graph
2025. 8. 10. 16:02