Mô hình đồ thị và quy hoạch động

Bước đầu tiên là chuyển bài toán công nhân/nhà máy sang ngôn ngữ đồ thị. Ta có đồ thị hai phía, mỗi phía \(N\) đỉnh, và cần thêm ít cạnh nhất sao cho mọi ghép cặp cực đại (không thể thêm cạnh nào nữa) đều là ghép cặp hoàn hảo (phủ tất cả đỉnh).

Muốn làm vậy, ta cần hiểu những đồ thị hai phía nào có tính chất mọi ghép cặp cực đại đều hoàn hảo. Có thể bắt đầu bằng cách vẽ vài đồ thị và thử thêm từng cạnh để tạo ghép cặp cực đại.

Sau một vài thí nghiệm, ta đưa ra giả thuyết: mọi ghép cặp cực đại là hoàn hảo khi và chỉ khi mỗi thành phần liên thông là một đồ thị hai phía đầy đủ có cùng số đỉnh ở hai phía. Chiều “nếu” khá rõ, nhưng chiều “chỉ nếu” ban đầu khá bất ngờ và cần chứng minh hình thức ở cuối bài phân tích. Đây là ví dụ về một đồ thị như vậy:

Quay lại bài toán, trước hết tìm số đỉnh ở mỗi phía của từng thành phần liên thông. Ghi chúng thành danh sách cặp

Theo giả thuyết, cần chia danh sách thành các nhóm sao cho trong mỗi nhóm, tổng các \(p\) bằng tổng các \(q\), cùng bằng \(r\). Mỗi nhóm sẽ trở thành một thành phần liên thông sau khi thêm cạnh. Số cạnh thêm bằng tổng số cạnh của đồ thị cuối trừ số cạnh ban đầu; số cạnh cuối bằng tổng \(r^2\) của các nhóm. Vì vậy cần tối thiểu hóa \(\sum r^2\).

Vì \(N\) khá nhỏ, tối đa 25, có nhiều cách làm được; gần như tất cả đều xoay quanh quy hoạch động hoặc ghi nhớ.

Một khả năng là: với mỗi tập con \(Y\) của đa tập \(X\) gồm các cặp trên, và mỗi \(t\) từ 0 đến \(N\), kiểm tra xem có thể gom mọi thành phần trong \(Y\) thành một số nhóm cân bằng có tổng kích thước \(t\), và có thể thêm một nhóm chưa cân bằng chứa tất cả thành phần còn lại hay không. Nếu có, đặt \(dp_{Y,t}\) là tổng bình phương kích thước nhỏ nhất của các nhóm cân bằng. Giá trị \(dp_{X,N}\) cho đáp án của bài toán.

Thoạt nhìn dường như phải xét \(2^{50}\) tập con vì đồ thị ban đầu có thể có tới 50 thành phần khi không có cạnh. Nhưng các thành phần bằng nhau có thể hoán đổi. Với đồ thị không cạnh, chỉ có 25 thành phần một loại và 25 thành phần loại kia, nên chỉ có \(26\cdot26=676\) tập con thành phần khác nhau. Với \(N=25\), số tập con phân biệt lớn nhất là 43008, đạt được ở cấu hình thành phần ban đầu:

6×(0,1), 5×(1,0), 3×(1,1), 1×(1,2), 1×(1,3), 1×(1,4),
1×(2,1), 1×(2,2), 1×(3,1), 1×(3,2), 1×(4,1).

Cách trực tiếp nhất tính \(dp_{Y,t}\) là quy hoạch động tiến: sau khi biết \(dp_{Y,t}\), thử mọi cách thêm một phần tử mới vào nhóm chưa cân bằng trong \(Y\), và cập nhật \(t\) nếu nhóm đó trở thành cân bằng.

Chứng minh giả thuyết

Ta chứng minh phản chứng. Giả sử tồn tại đồ thị hai phía mà mọi ghép cặp cực đại đều hoàn hảo, nhưng một thành phần liên thông không phải đồ thị hai phía đầy đủ với số đỉnh hai phía bằng nhau.

Chọn phản ví dụ \(G\) có ít đỉnh nhất; việc chọn phản ví dụ nhỏ nhất về bản chất tương đương quy nạp. Trước hết, \(G\) liên thông, nếu không một thành phần của nó sẽ là phản ví dụ nhỏ hơn. Hai phía của \(G\) cũng phải có cùng số đỉnh; nếu không thì không tồn tại ghép cặp hoàn hảo, trong khi luôn tồn tại ít nhất một ghép cặp cực đại, gây mâu thuẫn. Vì \(G\) là phản ví dụ, nó thiếu ít nhất một cạnh; gọi cạnh thiếu nối \(a\) và \(b\).

Xét một cạnh có thật \((a,c)\) đi ra từ \(a\); cạnh này tồn tại vì \(G\) liên thông. Tạo \(G'\) bằng cách xóa \(a,c\) và mọi cạnh kề chúng. Mọi ghép cặp cực đại trong đồ thị nhỏ hơn này đều hoàn hảo, vì có thể mở rộng nó thành ghép cặp cực đại trong \(G\) bằng cách thêm \((a,c)\). Do \(G'\) ít đỉnh hơn \(G\), nó không phải phản ví dụ; vậy mỗi thành phần liên thông của \(G'\) là đồ thị hai phía đầy đủ cân bằng.

Xét thành phần \(H\) của \(G'\) chứa \(b\). Có ba trường hợp, trường hợp nào cũng dẫn đến mâu thuẫn:

1. Có ít nhất một cạnh \((d,c)\) trong \(G\) từ \(H\) tới \(c\). Vì mọi thành phần của \(G'\) đều đầy đủ, dễ dựng một ghép cặp \(M'\) trong \(G'\) phủ mọi đỉnh trừ \(d,b\). Thêm \((d,c)\) được ghép cặp \(M\) trong \(G\). \(M\) là cực đại: hai đỉnh duy nhất chưa phủ là \(a,b\), và giữa chúng không có cạnh. Nhưng \(M\) không hoàn hảo, trái với định nghĩa của \(G\).
2. Không có cạnh từ \(H\) tới \(c\), nhưng có cạnh \((a,e)\) từ \(a\) tới \(H\). Chọn đỉnh \(f\) trong \(H\) ở phía đối diện \(e\). Vì \(H\) và mọi thành phần khác của \(G'\) đều đầy đủ, dựng được \(M'\) phủ mọi đỉnh trừ \(e,f\). Thêm \((a,e)\) được \(M\) trong \(G\). Hai đỉnh duy nhất chưa phủ là \(f,c\), giữa chúng không có cạnh vì cả \(H\) không nối tới \(c\); vậy \(M\) cực đại nhưng không hoàn hảo, lại mâu thuẫn.
3. Nếu \(H\) không nối với cả \(a\) lẫn \(c\), thì \(G\) không liên thông, cũng mâu thuẫn.

Hai trường hợp mâu thuẫn đầu tiên được minh họa dưới đây:

Còn một lập luận đẹp hơn, không cần chọn \(G\) là phản ví dụ nhỏ nhất nhưng khó nghĩ ra hơn. Vì \(G\) liên thông, có một đường đơn \(P\) giữa \(a\) và \(b\). Do đồ thị hai phía, \(P\) có độ dài lẻ và chứa cùng số đỉnh ở mỗi phía. Dựng một ghép cặp cực đại — do đó hoàn hảo — bằng cách lấy mọi cạnh ở vị trí lẻ dọc theo \(P\), rồi bổ sung các cạnh tùy ý. Sau đó đổi lựa chọn: lấy các cạnh ở vị trí chẵn của \(P\) thay cho các cạnh lẻ. Ghép cặp mới ít hơn một cạnh; \(a,b\) là hai đỉnh duy nhất chưa được phủ. Vì \(a,b\) không có cạnh nối, ta thu được một ghép cặp cực đại nhưng không hoàn hảo, mâu thuẫn.

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2016, Vòng 2.