Định lý Gale-Ryser

1. Định lý Gale-Ryser

Định lý Gale-Ryser là một trong những định lý cổ điển của toán Tổ Hợp. Định lý này trả lời câu hỏi sau đây:

Cho trước hai vectors \mathbf r = (r_1,\dots, r_m)\mathbf c = (c_1,\dots,c_n) gồm các số nguyên dương. Có tồn tại một ma trận nhị phân \mathbf A = (a_{ij}) \in \{0,1\}^{m \times n} gồm m hàng và n cột, sao cho tổng hàng thứ i của \mathbf Ar_i và tổng cột thứ j của \mathbf Ac_j. Câu hỏi này tương đương với câu hỏi liệu có tồn tại đồ thị hai phần (bipartite graph) cho trước bậc của các đỉnh.

Ta có thể thấy ngay vài quan sát đơn giản để tránh các trường hợp ngớ ngẩn:

  • Tất nhiên ta cần có r_1 + \cdots + r_m = c_1 + \cdots + c_n = B
  • Ta có thể giả sử r_1 \geq r_2 \geq \cdots \geq r_mc_1 \geq \cdots \geq c_n

Nói cách khác, ta chỉ cần trả lời câu hỏi trên khi mà \mathbf r\mathbf c là hai phân hoạch nguyên (integer partition) của cùng một số nguyên dương B. Một cách trực quan để hình dùng một phân hoạch nguyên là ta dùng sơ đồ Ferrers (Ferrers diagram). Ví dụ, sơ đồ Ferrers của phân hoạch 10 = 6 + 3 + 1 có thể minh hoạ bằng sơ đồ Ferrrers như sau:

sage: print Partition([6,3,1]).ferrers_diagram()
******
***
*

(Ở trên ta dùng sage, một phần mềm tính toán tuyệt vời, miễn phí, thay vì đám Matlab, Maple, Mathematica.) Khi ta lật cái sơ đồ Ferrers này theo trục chéo chính thì ta có một phân hoạch liên hợp (conjugate partition) của phân hoạch cho trước. Phân hoạc liên hợp của 6+3+1 là phân hoạch 3+2+2+1+1+1.

sage: print Partition([6,3,1]).conjugate().ferrers_diagram()
***
**
**
*
*
*

Cho một phân hoạch nguyên \mathbf p thì phân hoạch liên hợp của nó ký hiệu là \mathbf p^*. Cho hai phân hoạch \mathbf{p, q} của cùng một số nguyên thì \mathbf p áp đảo \mathbf q (dominate), ký hiệu \mathbf p \unrhd \mathbf q nếu và chỉ nếu \sum_{i=1}^k p_i \geq \sum_{i=1}^k q_i, với mọi k = 1, 2, \dots. (Ở đây, nếu không tồn tại giá trị p_i hay q_i thì ta định nghĩa p_i hay q_i bằng 0.)

Bài tập: Chứng minh rằng \mathbf p^* \unrhd \mathbf q nếu và chỉ nếu \mathbf q^* \unrhd \mathbf p.

Đến đây ta đã đủ khái niệm để phát biểu định lý Gale-Ryser.

Định Lý Gale-Ryser: cho trước hai phân hoạch \mathbf r = (r_1,\dots,r_m)\mathbf c = (c_1,\dots,c_n) của cùng một số nguyên dương B. Tồn tại một ma trận nhị phân \mathbf A=(a_{ij}) kích thước m \times n với \mathbf r là vector các tổng hàng và \mathbf c là vector các tổng cột nếu và chỉ nếu \mathbf r^* \unrhd \mathbf c

Chứng minh. Có nhiều cách chứng minh định lý này. Một cách đơn giản là dùng định lý luồng cực đại, cắt cực tiểu (max-flow, min-cut). Ta xây dựng một mạng luồng (flow network) với nguồn s (source), điểm thoát t (sink), m đỉnh trung gian u_1, \dots, u_mn đỉnh trung gian khác v_1,\dots, v_n. Các cạnh su_i có dung lượng (capacity) đúng bằng r_i. Các cạnh v_jt có dung lượng đúng bằng c_j. Và các cạnh u_iv_j có dung lượng bằng 1.

Dễ thấy rằng tồn tại ma trận cần tìm nếu và chỉ nếu tồn tại một luồng từ s đến t với tổng dung lượng bằng B = r_1+\dots r_m. Mà điều này xảy ra nếu và chỉ nếu nhát cắt cực tiểu có dung lượng đúng bằng B. Do đó ta chỉ cần chứng minh rằng \mathbf r^* \unrhd \mathbf c nếu và chỉ nếu dung lượng cắt cực tiểu bằng B.

Gọi U = \{u_1,\dots,u_m\}, và V = \{v_1,\dots, v_n\}. Một nhát cắt bất kỳ sẽ chia ra phía nguồn là tập \{s \} \cup U_s \cup V_s và phía thoát \{t \} \cup U_t \cup V_t, trong đó U_s \cup U_t là một phân hoạch của tập UV_s \cup V_t là một phân hoạch của tập V. Nhát cắt này có dung lượng bằng

\sum_{u_i \in U_t} r_i + |U_s|\cdot |V_t| + \sum_{v_j \in V_s} c_j = \sum_{u_i \in U_t} r_i + |U_s|\cdot |V_t| + B - \sum_{v_j \in V_t} c_j

Giả sử dung lượng cắt cực tiểu bằng B. Khi đó, với một nhát cắt tuỳ ý (\{s \} \cup U_s \cup V_s, \{t \} \cup U_t \cup V_t) thì dung lượng của nó ít nhất là B. Nói cách khác, với mọi phân hoạch U = U_s \cup U_tV = V_s \cup V_t, ta có

\sum_{u_i \in U_t} r_i + |U_s|\cdot |V_t| \geq \sum_{v_j \in V_t} c_j

Xét một số nguyên dương k \in [n] tuỳ ý. Chọn V_t = \{v_1, \dots, v_k\}, và U_t là tập tất cả các u_i sao cho . Tất nhiên, ta có thể giải bài toán luồng cực đại nhưng như vậy có vẻ giết gà bằng dao mổ trâu. Vấn đề kế tiếp ta muốn giải quyết là, cho trước \mathbf r^* \unrhd \mathbf c, xây dựng ma trận \mathbf A = (a_{ij}) với vector tổng hàng là \mathbf r và vector tổng cột là \mathbf c.

Ta giải quyết bài toán này bằng một thuật toán tham lam như sau. (Thuật toán này chứng minh một chiều của định lý Gale-Ryser mà không dùng định lý luồng cực đại.) Ta cần xác định xem đặt các số 1 vào đâu trong cột thứ nhất của \mathbf A, rồi dùng đệ qui để giải quyết phần còn lại cho các cột từ c_2 đến c_n. Để đệ quy đơn giản, ta cho phép các số r_i, c_j là không âm thay vì dương. Do \mathbf r^* \unrhd \mathbf c, ta biết r^*_1 \geq c_1. Mà r^*_1 chính là tổng số các giá trị r_i sao cho r_i \geq 1.

Cách đơn giản là đặt tổng cộng c_1 số 1 ở các hàng ir_i \geq 1, tính từ r_i lớn nhất lên đến r_i nhỏ nhất. Sau khi đã có các số 1 này ở cột thứ nhất, thì ta giải quyết bài toán cho các cột còn lại. Tổng các cột bây giờ là (c_2, \dots, c_n), còn tổng các hàng là

(r_1, \dots, r_m) - (\underbrace{1, \dots, 1}_{c_1 \text{ of them}}, 0, \dots, 0)

Dễ thấy rằng điều kiện Gale-Ryser vẫn thoả mãn cho bài toán đệ qui. (Cần một ít trí tưởng tượng, nhưng thật sự là “dễ” thấy.) Thuật toán này thể hiện bằng Python như sau:

# **************************************************************************
# assume r^* dominates c, and r and c are partitions of the same positive
# integer B. Returns a matrix A whose row sums are r and column sums are c
# **************************************************************************
def gale_ryser(r, c):
    n = len(c); m = len(r)
    A = [ [0]*n + [r[i], i] for i in range(m) ]
    for j in range(n):
        if (c[j] == 0): break
        for i in range(c[j]):
            A[i][n] = A[i][n]-1
            A[i][j] = 1

        # sort A in terms of r, the row with the largest r_i comes first
        A.sort(key = lambda row: row[n], reverse = True)
    A.sort(key = lambda row: row[n+1]) # the original row order
    return [ row[0:n] for row in A ]

# simple test case
r = [3, 2, 2, 2, 1, 0, 0]
c = [3, 3, 3, 1, 0]
for row in gale_ryser(r, c): print row

Chạy thử

$ python gale-ryser.py 
[1, 1, 1, 0, 0]
[1, 1, 0, 0, 0]
[1, 0, 1, 0, 0]
[0, 1, 1, 0, 0]
[0, 0, 0, 1, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]

3. Một bài toán khó … chịu

Thế nếu ta muốn in tất cả các ma trận cho trước hai vectors tổng hàng và cột, thì làm sao cho hiệu quả? Đây là một bài toán khó.

Chủ đề : Combinatorics, Python, Thuật Toán and tagged , . Bookmark the permalink. Trackbacks are closed, but you can post a comment.

6 Comments

  1. Vinh
    Posted 30/06/2013 at 9:13 pm | Permalink

    bài này làm e nhớ đến 1 vấn đề đang giải quyết nhưng chưa có lời giải đẹp: phân hoạch ngẫu nhiên (clustering) 1 data set theo 2 cách sao cho số điểm trong các clusters ứng với các giá trị (cố định trước) {r_1,r_2,…, r_m} và {c_1,c_2,…,c_n}. Tính xác suất để {cluster i-th của phân hoạch 1 và cluster j-th của phân hoạch 2 có n1 điểm chung} VÀ {cluster i’-th của phân hoạch 1 và cluster j’-th của phân hoạch 2 có n2 điểm chung}.

    có vẻ không liên quan nhỉ, anw, không biết các anh chị với anh Hưng có cao kiến gì không 😀

    • Posted 02/07/2013 at 2:35 pm | Permalink

      Thấp kiến cũng không có. Tôi không hiểu đề bài :-).
      Đề bài có vẻ under-specified. Cái “phân hoạch ngẫu nhiên” đó được chọn như thế nào, và quan hệ giữa i, j, i', j' ra sao?

      • Vinh
        Posted 02/07/2013 at 9:34 pm | Permalink

        nói nôm na là có n quả bóng, em có thể chọn tung ngẫu nhiên vào 1 cái contingency table (chả biết dịch sao :D) sao cho tổng số bóng trong các hàng tương ứng phải là {r_1,…r_m} và tổng số bóng trong các cột phải là {c_1,…,c_n} (fixed marginal constraints). Tính xác suất để ô ij-th của bảng có n_ij bóng VÀ ô i’j’-th của bảng có n_i’j’ bóng (ko có quan hệ gì giữa ij và i’j’, có thể i=i’,j=j’ hoặc ii’, jj’ hoặc i=i’, jj’ và ngược lại).

        ko biết e diễn giải thế đã đầy đủ hơn chưa 😀

        • Posted 03/07/2013 at 12:11 am | Permalink

          Thật ra tôi nghĩ vẫn chưa đủ thông tin về phân phối của bảng này, nhất là khi diễn giải bằng “tung bóng”. Có lẽ Vinh có thể nói là chọn ngẫu nhiên một bipartite graph từ một tập các bipartite graphs có bậc các đỉnh cho trước. Tính xác suất mà đồ thị ngẫu nhiên này có n_{ij} cạnh giữa hai đỉnh i, j, và n_{i'j'} cạnh giữa hai đỉnh i', j'.

          Bài toán khó và xấu xí. Tôi không nghĩ là có closed form formula.

        • Vinh
          Posted 07/07/2013 at 9:19 pm | Permalink

          vâng chắc cách diễn giải của anh Hưng là đúng rồi.
          Trước giờ nghĩ về graph em cứ nghĩ là chỉ có 0/1(undirected)/2(directed) cạnh giữa 2 đỉnh thôi nhỉ, lại có loại đồ thị có nhiều cạnh giữa 2 đỉnh ạ :D? nhưng diễn giải vào bài toán của em thì đúng

        • Posted 08/07/2013 at 11:40 am | Permalink

          Ừ, cái đó gọi là multigraph.

Post a Comment

Your email is never published nor shared. Required fields are marked *

You may use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*
*