이분 매칭에서 이미 매칭된 간선을 잠시 취소하고 다른 상대를 찾아도 매칭 수가 늘어나는 이유는 무엇인가요?

증가 경로는 현재 매칭에 속하지 않는 간선과 속하는 간선을 번갈아 지나고, 양 끝이 아직 매칭되지 않은 경로입니다. 이 경로의 모든 간선 소속을 뒤집으면 비매칭 간선이 매칭 간선보다 정확히 하나 많기 때문에 매칭의 크기가 1 증가합니다. 기존 매칭을 잠시 취소하는 것은 손실이 아니라, 이미 점유한 상대를 다른 정점으로 재배치해 자유로운 끝점을 연결하기 위한 과정입니다.

예를 들어 현재 L1-R1만 매칭되어 있고 L2, R2가 자유라고 하겠습니다. 그래프에 L2-R1, L1-R2가 있으면 L2-R1-L1-R2를 따라갈 수 있습니다. 처음에는 L2-R1과 L1-R2가 비매칭이고 가운데 L1-R1만 매칭입니다. 세 간선을 뒤집으면 L2-R1, L1-R2가 매칭되고 L1-R1은 빠져서 1개가 2개가 됩니다. 각 내부 정점은 경로에서 한 번 들어오고 한 번 나가므로 끝점 중복도 생기지 않습니다.

Kuhn DFS가 R1의 기존 상대 L1을 다시 호출하는 이유도 이 구조 때문입니다. L1이 다른 오른쪽 정점 R2를 확보할 수 있으면 R1을 현재 시작 정점 L2에 넘깁니다. 반대로 양 끝이 모두 이미 매칭된 alternating cycle을 뒤집으면 추가된 간선과 제거된 간선 수가 같아 cardinality는 변하지 않습니다. 임의의 DFS 경로를 뒤집는 것이 아니라, 교대성과 양 끝의 자유 상태를 모두 확인해야 합니다.

작은 상태를 배열로 적으면 이유가 더 분명합니다. 처음 matchR=[L1,NONE]에서 L2가 R1을 보며 old=L1을 만납니다. 재귀 호출 try(L1)이 R2의 NONE을 확인해 성공하면, 복귀 시 matchR[R2]=L1, 그 다음 상위 프레임에서 matchR[R1]=L2를 씁니다. 한 번의 성공 복귀가 경로 전체의 뒤집기를 표현하므로, 중간에 매칭 배열을 임의로 지웠다가 실패 시 복구하는 방식보다 불변식을 유지하기 쉽습니다. 다만 그래프에 L1-R2가 없거나 R2도 다른 정점에 막혀 있으면 재귀가 false를 반환하고 원래 배열을 건드리지 않아야 합니다.