이분 매칭·Flow·Cut·최소 정점 덮개

가능한 배정과 최적성 증명은 다릅니다

세 작업을 서로 다른 기계에 배정하되 작업마다 사용할 수 있는 기계가 다르다고 합시다. 매칭은 같은 작업이나 기계를 두 번 쓰지 않는 허용된 짝의 집합입니다. 두 쌍을 찾으면 두 배정이 가능하다는 하한을 얻지만 세 쌍이 불가능하다는 증명은 아닙니다. 컷이나 정점 덮개가 제공하는 상한과 같은 값을 얻으면 최적성을 인증할 수 있습니다.

이 관점은 배정·추적·자원 할당에 유용합니다. 여기서는 쌍의 수를 최대화하며 별도의 품질 점수 합을 최적화하지 않습니다. 최대 개수 매칭이 가중 품질까지 최대화하는 것은 아닙니다. 작은 모형에서 잔여 경로의 실제 갱신과 인증을 함께 확인합니다.

이분 그래프를 표현하기

왼쪽 정점은 L0,L1,L2, 오른쪽은 R0,R1,R2입니다. 이웃 mask는 비트의 합으로 1은 R0, 2는 R1, 4는 R2를 연결합니다. (3,1,6)이면 L0는 R0·R1, L1은 R0, L2는 R1·R2에 연결됩니다. 모든 간선은 두 집합 사이를 가로지릅니다.

이진 선택 변수는

$$x_{ij}\in\{0,1\},\qquad \sum_jx_{ij}\le1,\quad\sum_ix_{ij}\le1, \qquad \max\sum_{(i,j)\in E}x_{ij}$$

을 만족합니다. 없는 간선은 선택할 수 없습니다. 아홉 간선의 유무를 조합한 가능한 그래프는 512개입니다. 이 작은 크기는 독립 전수 검산에 쓰며, 화면의 흐름을 계산하는 알고리즘 자체는 잔여 BFS입니다.

Flow 문제로 환원하기

source s와 sink t를 추가합니다. s→Li와 Rj→t의 용량은 1, 원래 Li→Rj 간선의 용량은 4입니다. 내부 정점에서는 들어오는 흐름과 나가는 흐름이 같습니다. 정수인 바깥 흐름이 1 이하이므로 각 왼쪽·오른쪽 정점에는 최대 하나의 내부 선택만 대응합니다. 정수 흐름과 같은 크기의 매칭을 서로 구성할 수 있습니다.

왜 내부 용량을 4로 정할까요? s만 포함하는 컷의 용량이 3이므로 최소 컷은 3 이하입니다. 내부 간선 하나를 자르면 이미 비용 4라 최소 컷일 수 없습니다. 알려진 상한에서 충분한 유한 값을 정한 것이며 임의로 거대한 수를 넣은 것이 아닙니다.

역방향 잔여 간선은 이전 선택을 고칩니다

알고리즘은 흐름 0에서 시작하고 결정적인 순서의 BFS를 수행합니다. 정방향 잔여 간선은 남은 용량, 역방향 잔여 간선은 이미 보낸 흐름을 취소할 권한입니다. 바깥 간선의 용량이 1이므로 이 모형의 모든 증대 경로에서 병목은 1입니다. 경로 전체에 1을 보내면서 정방향 원래 흐름은 늘리고 역방향에 대응하는 원래 흐름은 줄입니다.

(3,1,6)의 첫 증대는 L0-R0를 선택합니다. 다음 최단 경로는 s-L2-R1-t라 두 쌍을 만듭니다. 그 뒤의 실제 경로는

$$s\to L1\to R0\to L0\to R1\to L2\to R2\to t.$$

L1-R0를 추가하고 L0-R0를 취소합니다. L0-R1을 추가한 뒤 L2-R1을 취소하고 L2-R2를 추가합니다. 세 번 추가하고 두 번 취소하여 전체 크기는 1 늘어납니다. 최종 매칭은 L0-R1, L1-R0, L2-R2입니다. 역방향이 음수의 실제 배정이나 음수 용량을 뜻하지는 않습니다. 표는 원래 간선의 음수가 아닌 흐름과 역방향 잔여 용량을 구분합니다.

전체 이력을 계산한 다음 요청한 prefix를 표시합니다. 별도로 표시한 종료 최적값이 현재의 중간 prefix까지 인증하는 것은 아닙니다. 증대가 세 번보다 적으면 더 큰 요청에도 종료 상태와 실제 완료 수를 표시합니다.

컷은 가능한 매칭의 상한입니다

s-t 컷의 source 쪽 집합 S는 s를 포함하고 t를 제외해야 합니다. S 안의 흐름 보존식을 합하면 전체 흐름 값은 바깥으로 나가는 흐름에서 안으로 들어오는 흐름을 뺀 값입니다. 따라서 어떤 가능한 흐름도 나가는 간선 용량 합을 넘지 못합니다.

현재 잔여 그래프에서 s가 도달할 수 있는 전체 집합을 S라 합시다. 증대가 가능하면 t도 이 집합에 들어가므로 아직 s-t 컷이 아닙니다. 화면은 이때 도달 집합의 컷·덮개 인증을 제공하지 않습니다. 종료하여 t가 도달되지 않으면 S가 유효한 컷입니다. 경계를 나가는 원래 간선은 포화되고 들어오는 원래 간선의 흐름은 0이므로 흐름과 컷 값이 같아집니다. 가능한 흐름과 상한이 일치하므로 둘 다 최적입니다.

최소 정점 덮개를 유도하기

정점 덮개 K는 모든 원래 간선의 끝점 중 적어도 하나를 포함합니다. 매칭 간선들은 정점을 공유하지 않으므로 각각을 덮으려면 서로 다른 덮개 정점이 필요합니다. 일반 그래프에서도 매칭 크기는 덮개 크기 이하입니다. 종료 상태에서

$$K=(L\setminus S)\cup(R\cap S)$$

로 둡니다. 최소 컷은 내부 용량 4의 간선을 자르지 않으므로 S 안의 L에서 S 밖의 R로 가는 간선이 없습니다. 따라서 모든 간선이 K에 닿습니다. S 밖의 왼쪽 정점과 S 안의 오른쪽 정점이 각각 컷 비용 1에 대응하여 덮개 크기와 컷 값도 같습니다. 같은 크기의 매칭과 덮개를 얻었으므로 최대 매칭과 최소 덮개를 인증합니다.

이는 이분 그래프의 매칭·덮개 동등성입니다. 모형 밖의 삼각형은 최대 매칭이 1, 최소 덮개가 2라 일반 그래프에서는 같은 값을 보장하지 않습니다. 이분성의 가정을 생략하면 안 됩니다.

조회한 정점 집합을 검증하기

조회 mask의 비트 0..2는 왼쪽, 3..5는 오른쪽 정점입니다. 덮개가 아닐 수도 있는 임의의 K에서 유효한 컷 S_K={s}∪(K 밖의 L)∪(K 안의 R)을 구성할 수 있습니다. u(K)가 덮이지 않은 간선 수이면

$$\operatorname{cap}(S_K)=|K|+4u(K).$$

이 컷은 여전히 상한이지만 K의 크기 자체를 덮개 상한으로 쓰려면 u(K)=0을 확인해야 합니다. 여섯 정점을 모두 고르면 덮개는 맞지만 최소일 필요는 없습니다. 조회 집합의 덮개 여부, 유효 컷 용량과 현재 흐름에 대한 간극을 따로 표시합니다.

(1,1,2)에서는 두 쌍만 배정할 수 있습니다. 종료 도달 집합은 s,L0,L1,R0라 K={L2,R0}이며 mask는 4+8=12입니다. 매칭·최소 컷·최소 덮개는 모두 2입니다. 왼쪽 부분집합 {L0,L1}의 이웃이 R0 하나뿐이라는 사실로 세 쌍이 불가능한 이유도 직관적으로 설명할 수 있습니다.

두 도식과 곡선 읽기

첫 도식의 화살표는 원래 흐름 네트워크입니다. 파랑은 현재 흐름과 매칭, 주황 채움은 종료 prefix에서 인증한 최소 덮개입니다. 점선 주황 원은 조회 집합일 뿐 인증은 아닙니다. 두 번째 도식은 다음 잔여 경로의 간선·잔여 용량·추가/취소를 표시합니다. 종료 상태에는 다음 경로가 없다는 메시지를 제공합니다.

아래 가로축은 실제 완료한 증대 수입니다. 파랑은 가능한 매칭 이력이며 종료하면 끝납니다. 주황은 조회 집합에서 만든 유효 컷 상한입니다. 조회 집합이 느슨하면 선택한 파란 점과 주황 상한이 만나지 않을 수 있습니다. 최적화 학습 손실의 시간 변화가 아닙니다.

문제와 해설

문제: 완전한 3×3 그래프에서 prefix 0, 조회 mask 0이면 조회 컷 용량과 도달 컷 인증은 무엇일까요?

해설: 아홉 간선이 모두 덮이지 않아 조회 컷의 용량은 4×9=36입니다. sink가 잔여 도달 가능하므로 도달 집합 자체는 s-t 컷이 아니고 그 인증은 제공하지 않습니다. 유효한 상한도 매우 느슨할 수 있습니다.

문제: (3,1,0)의 prefix 1에서 다음 경로는 무엇인가요?

해설: s-L1-R0-L0-R1-t가 L0-R0를 취소해 두 쌍을 만듭니다. 고립된 L2는 배정되지 않습니다. 이 작은 경우는 한 번의 취소이고 기본 세 쌍 예제의 마지막 경로는 두 번의 취소입니다.

문제: 알고리즘이 항상 같은 매칭을 반환하면 유일해인가요?

해설: 완전 이분 그래프에는 여러 perfect matching과 여러 최소 덮개가 있습니다. 인증은 최적값의 증명이며 이웃 탐색 순서는 그중 대표를 고릅니다.

후속 학습 연결

MIT의 Network Flows and Matching 자료는 흐름·매칭·덮개의 연결을, Karger의 흐름 계산 자료는 잔여 최적성 조건을 다룹니다. 이 단원의 용량 4 모형·prefix 진단·실행 예제는 독립 유한 열거로 검산한 교재 구성입니다. 가중 매칭과 일반 비이분 그래프 알고리즘은 추가 이론이 필요합니다.