이분 매칭의 DFS 시작 쪽을 더 작은 partition으로 바꾸면 정답과 비용에 어떤 영향이 있나요?

두 partition을 뒤집어도 maximum cardinality 자체는 변하지 않습니다. 같은 매칭 간선을 반대 방향으로 표현하는 것뿐이기 때문입니다. 다만 Kuhn의 반복 DFS는 시작 쪽 정점마다 증가 경로를 시도하므로, 시작 partition의 크기를 n1, 간선 수를 m이라 하면 표준적인 상한 O(n1·m)에서 n1을 작은 쪽으로 두는 편이 탐색 횟수를 줄입니다.

왼쪽 10,000개와 오른쪽 100개인 그래프를 오른쪽 시작으로 재표현한다고 하겠습니다. 기존 matchR[r] = l 구조를 그대로 복사하는 것이 아니라, 새 시작 쪽을 L'로 정하고 상대 배열이 matchR'[oldLeft] = newRight인지 의미를 다시 정의해야 합니다. adjacency의 각 간선도 새 시작 정점의 목록으로 옮겨야 합니다. 이 변환을 빠뜨리면 알고리즘은 실행되더라도 전혀 다른 정점을 해제하거나 존재하지 않는 인덱스를 참조합니다.

정답의 cardinality와 증가 경로 부재에 따른 최대성 조건은 바뀌지 않습니다. 바뀌는 것은 DFS를 몇 번 시작하는지와 배열의 방향입니다. 단, 이는 최대 카디널리티 매칭에 대한 판단입니다. 가중 매칭은 별도의 목적 함수이고, 일반 그래프 매칭은 partition 자체가 없어 같은 변환을 적용할 수 없습니다.

상한의 n1은 단순히 정점 수가 작은 쪽이라는 뜻이 아니라 실제로 augmentation을 시작하도록 선택한 쪽의 정점 수입니다. 예컨대 |L|=10000, |R|=100, m=500이면 L 시작 상한은 O(10000·500), R 시작 상한은 O(100·500)로 표현됩니다. 실제 실행에서는 인접 리스트를 새 시작 정점 기준으로 재구성하고 match의 값이 원래 어느 쪽 ID를 가리키는지 바꿔야 합니다. 작은 쪽에 간선이 집중되어 있어도 최악 상한은 줄지만, 인접 리스트의 캐시 지역성·재귀 호출 비용·이미 매칭된 정점 비율은 별도 측정 대상입니다.