Từ hành trình sang đa đồ thị cân bằng

Trong bài này, ta được cho một đồ thị đơn có hướng \(G\) và phải tìm một chu trình đủ ngắn đi qua mỗi cạnh ít nhất một lần, đồng thời đi qua mọi đỉnh cùng một số lần.

Gọi đồ thị đầu vào là \(G=(V,E)\), với \(V=\{1,2,\ldots,B\}\) và \(E=\{(X_1,Y_1),(X_2,Y_2),\ldots,(X_S,Y_S)\}\). Nếu chu trình tồn tại, gọi \(k\) là số lần chu trình đi qua mỗi đỉnh. Gom các cạnh xuất hiện trong chu trình, kể cả số lần lặp, ta được đa đồ thị \(G'=(V,E')\), trong đó \(E'\) là một đa tập và có các tính chất:

• Tập nền của \(E'\) chính là \(E\): mỗi cạnh của \(E\) xuất hiện ít nhất một lần trong \(E'\), và mọi cạnh của \(E'\) đều thuộc \(E\).
• Với mỗi đỉnh \(v\), \(\operatorname{indegree}(v)=\operatorname{outdegree}(v)=k\).

Ngược lại, nếu tìm được một đa đồ thị \(G'\) thỏa các tính chất trên với một \(k\) nào đó, ta có thể dùng thuật toán dựng chu trình Euler để tìm đáp án từ \(G'\). Chu trình Euler là chu trình đi qua mỗi cạnh của đồ thị đúng một lần. Vì vậy, các cách giải dưới đây tập trung vào việc tìm \(G'\).

Gọi \(L=10^6\) là giới hạn đầu ra. Khi phân tích độ phức tạp, cần coi \(L\) là một tham số quan trọng.

Cách \(O(LBS)\)

Cách này dùng luồng cực đại để tìm số lần lặp hợp lệ \(d_i\) cho mỗi cạnh \((X_i,Y_i)\in E\); tức là \((X_i,Y_i)\) xuất hiện \(d_i\) lần trong \(E'\).

Tổng số cạnh của chu trình là \(kB\), nên \(k\le L/B\). Không thể liệt kê mọi bộ \(d_i\), nhưng ta có thể thử từng giá trị \(k\) và kiểm tra xem với \(k\) cố định có sinh được một bộ \(d_i\) hợp lệ hay không. Khi tìm thấy bộ đó, \(G'\) cũng được xác định.

Ta quy bài toán này về luồng cực đại. Dựng một mạng luồng có nguồn \(s\), đích \(t\) và các đỉnh:

• nguồn \(s\);
• đích \(t\);
• một đỉnh \(in_v\) cho mỗi \(v\in V\);
• một đỉnh \(out_v\) cho mỗi \(v\in V\).

Mạng có tổng cộng \(2B+2\) đỉnh. Các cạnh của mạng là:

• \((s,out_v)\) với mỗi \(v\in V\), sức chứa \(k\);
• \((out_u,in_v)\) với mỗi \((u,v)\in E\), không giới hạn sức chứa trên nhưng có cận dưới luồng bằng \(1\);
• \((in_v,t)\) với mỗi \(v\in V\), sức chứa \(k\).

Mạng có tổng cộng \(S+2B\) cạnh. Lượng luồng đi qua \(in_v\) (tương ứng là \(out_v\)) biểu diễn bậc vào (tương ứng là bậc ra) của \(v\) trong \(G'\). Lượng luồng trên \((out_u,in_v)\) biểu diễn số lần lặp của cạnh \((u,v)\).

Ta tìm luồng cực đại của mạng. Nếu tổng luồng bằng \(kB\), là giá trị lớn nhất có thể, thì lượng luồng qua mỗi \(in_v\) và \(out_v\) đều bằng \(k\), và ta đã tìm được bộ \(d_i\) hợp lệ. Khi đó, dựng \(G'\) với các số lần lặp ấy, tìm chu trình Euler trong \(G'\) rồi in chu trình. Nếu không có bất kỳ \(k\) nào cho luồng như vậy, in IMPOSSIBLE.

Thuật toán chạy luồng cực đại cho từng \(k\). Có \(L/B\) khả năng cho \(k\), còn mạng có \(O(B)\) đỉnh và \(O(S)\) cạnh. Nếu dùng thuật toán Dinic, với cận \(O(B^2S)\) cho mỗi lần, tổng độ phức tạp là \(O(LBS)\). Có thể tăng tốc bằng cách, ở mỗi \(k\), bắt đầu từ luồng đã tìm được cho giá trị \(k\) trước đó.

Cách \(O(S^2)\)

Thuật toán trước có thể hơi chậm, nên ta muốn dựng \(G'\) trực tiếp hơn. Trước hết, xét thuật toán lặp đơn giản sau:

• Chọn một cạnh \((u,v)\) chưa có trong \(G'\).
• Thêm vào \(G'\) các cạnh trên một đường đi từ tòa nhà \(1\) đến \(u\).
• Thêm cạnh \((u,v)\) vào \(G'\).
• Thêm vào \(G'\) các cạnh trên một đường đi từ \(v\) về tòa nhà \(1\).
• Lặp cho đến khi mỗi cạnh xuất hiện ít nhất một lần trong \(G'\).

\(G'\) do thuật toán này sinh ra tạo được một chu trình, vì chỉ cần đi theo các cạnh đúng thứ tự chúng được thêm. Tuy nhiên, số lần ghé các tòa nhà chưa chắc bằng nhau. Vì vậy, ta thay bằng quy trình:

• Chọn một cạnh \((u,v)\) chưa có trong \(G'\).
• Tìm một tập cạnh \(A\) chứa \((u,v)\) sao cho bậc vào và bậc ra của mỗi đỉnh trong \(A\) bằng nhau.
• Thêm \(A\) vào \(G'\).
• Lặp cho đến khi mỗi cạnh xuất hiện ít nhất một lần trong \(G'\).

Nếu quy trình thành công, \(G'\) có mọi tính chất cần thiết đã nêu. Hơn nữa, nếu mỗi \(A\) nhỏ nhất có thể, nghĩa là bậc vào và bậc ra của từng đỉnh trong mỗi \(A\) đều bằng \(1\), thì \(G'\) có nhiều nhất \(SB\) cạnh. Giá trị này không vượt \(10^6\), đúng bằng giới hạn thuận tiện của bài.

Câu hỏi là: nếu bài có lời giải, ta có luôn tìm được \(A\) như vậy cho một cạnh bất kỳ \((u,v)\) không? Câu trả lời là có.

Việc tìm \(A\) được quy về ghép cặp hoàn hảo trên một đồ thị hai phía tương tự mạng luồng ở cách trước. Hai phía gồm các đỉnh \((s_1,s_2,\ldots,s_B)\) và \((t_1,t_2,\ldots,t_B)\). Có cạnh \((s_u,t_v)\) khi và chỉ khi \((u,v)\in G\). Nếu dùng một cạnh trong ghép cặp hoàn hảo, ta đưa cạnh tương ứng của \(G\) vào \(A\).

Ta cần chứng minh đồ thị này có ghép cặp hoàn hảo nếu bài toán có nghiệm. Dùng định lý hôn nhân Hall: với một tập con \(S_0\) bất kỳ của phía \((s_1,\ldots,s_B)\), gọi \(T_0\) là tập tất cả đỉnh kề với một đỉnh trong \(S_0\), ta cần chứng minh \(|S_0|\le|T_0|\). Điều tương tự ở phía các đỉnh \(t_i\) có cùng chứng minh.

Giả sử bài có lời giải và đa đồ thị tương ứng \(G'\) có bậc vào, bậc ra tại mỗi đỉnh đều bằng \(k\). Với mỗi \(i\), gọi \(g(s_i)\) là số cạnh của \(G'\) có đuôi tại đỉnh \(i\), và \(g(t_i)\) là số cạnh của \(G'\) có đầu tại đỉnh \(i\). Với mọi cặp \(S_0,T_0\) như trên,

vì các cạnh của \(G'\) có đầu thuộc \(T_0\) phải bao gồm mọi cạnh có đuôi thuộc \(S_0\), và có thể còn có thêm cạnh khác. Do mọi giá trị \(g\) đều bằng \(k\), suy ra \(|S_0|\le|T_0|\) như yêu cầu.

Tuy nhiên, bài toán ghép cặp thực sự còn bắt buộc một cạnh cố định \((s_u,t_v)\) phải thuộc ghép. Hãy xóa mọi cạnh khác kề với \(s_u\) hoặc \(t_v\) khỏi đồ thị hai phía, rồi định nghĩa lại \(g(s_i)\) và \(g(t_i)\) lần lượt là số cạnh của \(G'\) có đuôi hoặc đầu ở \(i\), không tính các cạnh vừa bị xóa.

Xét một tập \(S_0\) không chứa \(s_u\). Vì có ít hơn \(k\) cạnh liên quan bị xóa,

Mặt khác, \(\sum_{t\in T_0}g(t)\le k|T_0|\) vì \(k\) vẫn là giá trị lớn nhất của mọi \(g(t)\), và bất đẳng thức giữa hai tổng ở trên vẫn đúng. Do đó,

suy ra \(k|S_0|-k<k|T_0|\), rồi \(|S_0|-1<|T_0|\), và cuối cùng \(|S_0|\le|T_0|\) vì kích thước tập là số nguyên. Nếu \(S_0\) chứa \(s_u\), chỉ cần ghép \(s_u\) với \(t_v\) trước; phần còn lại là một tập không chứa \(s_u\) và áp dụng lập luận vừa rồi.

Nếu không tìm được ghép cặp hoàn hảo khi bắt buộc một cạnh \((s_u,t_v)\) nào đó, ta suy ra bài toán không có lời giải. Ứng dụng định lý Hall này còn được gọi là định lý Birkhoff về ma trận doubly stochastic.

Trong cách hiện tại, nếu tìm một ghép cặp hoàn hảo độc lập trên \(S\) đồ thị hai phía, mỗi đồ thị có \(O(B)\) đỉnh và \(O(S)\) cạnh, thì dùng thuật toán dựa trên luồng cho tổng độ phức tạp \(O(BS^2)\).

Ta còn có thể tận dụng kết quả trước để khỏi tính lại toàn bộ ghép cặp mỗi lần. Trước tiên tìm một ghép cặp hoàn hảo tùy ý làm ghép cơ sở. Với mỗi cạnh \((s_u,t_v)\) không thuộc ghép cơ sở, bỏ hai cạnh của ghép đang kề \(s_u\) và \(t_v\), rồi thêm \((s_u,t_v)\). Khi đó đúng hai đỉnh trở thành chưa ghép; tìm một đường tăng giữa chúng để hoàn tất ghép mới.

Tìm ghép cơ sở tốn \(O(BS)\). Với mỗi cạnh \((s_u,t_v)\), tìm đường tăng tốn \(O(S)\). Đồ thị hai phía có \(S\) cạnh, nên tổng độ phức tạp là \(O(S^2)\).

Phần trình bày dựa trên phân tích chính thức của Google Code Jam 2022, World Finals.