이분 매칭 계산기

두 무리로 나뉘어 있고 같은 쪽끼리는 이어지지 않는 그래프에서 겹치지 않게 짝을 최대한 많이 짓는 문제입니다. 사람과 일, 지원자와 자리, 기계와 작업처럼 「한 사람은 한 곳, 한 자리에는 한 명」인 배정이 모두 여기에 해당합니다.

더 늘릴 「증가 경로」가 하나도 없으면 최대입니다. 왼쪽을 하나씩 보며 빈 상대가 있으면 잡고, 다 차 있으면 그 상대의 지금 짝에게 다른 자리를 찾아 달라고 부탁합니다. 부탁이 연쇄적으로 성공하면 자리를 밀어내며 짝이 정확히 하나 늘어나고, 그런 길이 더는 없을 때가 최대입니다.

이분 그래프에서 최대 매칭의 크기와 최소 정점 덮개의 크기가 정확히 같다는 정리입니다. 정점 덮개란 모든 간선을 적어도 한쪽 끝으로 덮는 정점 집합입니다. 일반 그래프에서는 성립하지 않고 이분 그래프에서만 성립합니다.

최소 정점 덮개의 여집합입니다. 모든 간선이 덮개를 지나가므로 덮개를 뺀 나머지끼리는 이어질 수 없기 때문입니다. 일반 그래프에서는 독립 집합 문제가 NP-난해인데 이분 그래프에서는 매칭 한 번으로 풀립니다.

안정 매칭은 양쪽에 선호 순위가 있고 서로 지금 짝보다 상대를 더 좋아하는 쌍이 없게 짝짓습니다. 이분 매칭은 순위 없이 「이을 수 있다·없다」만 있고 오직 개수를 최대로 합니다. 목적이 다른 문제입니다.

있습니다. 왼쪽 전체에 원천을, 오른쪽 전체에 싱크를 붙이고 모든 간선의 용량을 1로 두면 최대 유량이 곧 최대 매칭의 크기가 됩니다. 다만 이 도구는 증가 경로를 직접 밟아 어느 자리를 밀어냈는지 보이는 쪽을 택했습니다.

계산하지 않고 막습니다. 같은 이름이 왼쪽에도 오른쪽에도 있으면 이분 그래프가 아니게 되어 최대 매칭 계산도 쾨니그 정리도 성립하지 않기 때문입니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.