Bài toán về hệ thống đại diện chung

Cho tập m phần tử X={ z₁, z₂, . . . ,z_m}. Giả sử <A₁, A₂, . . ., A_n> và <B₁, B₂, . . ., B_n> là hai dãy các tập con của X. Dãy gồm n phần tử khác nhau của X: <a₁, a₂, . . . ,a_n> được gọi là hệ thống các đại diện chung của hai dãy đã cho nếu như tìm được một hoán vị s của tập {1, 2,. . .,n} sao cho < a₁, a₂, . . . ,a_n> là hệ thống các đại diện phân biệt của hai dãy <A₁, A₂, . . ., A_n> và <Bs₍₁₎, Bs₍₂₎, . . ., Bs_(n)>, tức là điều kiện sau được thoả mãn: a_i ∈ A_i  Bs _(i), i = 1, 2, . . ,n. Xây dựng mạng G = (V, E) với tập đỉnh

V = { s, t}  { x₁, x₂, . . . ,x_n} {u₁, u₂, . . . ,u_n} { v₁, v₂, . . . ,v_n} { y₁, y₂, . . . ,y_n}.

trong đó đỉnh x_i tương ứng với tập A_i, đỉnh y_i tương ứng với tập B_i, các phần tử u_j, y_j tương ứng với phần tử z_j. Tập các cung của mạng G được xác định như sau

     E  = { (s, x_i): 1≤i≤n}  { (x_i,u_j): với z_j ∈ A_i, 1≤i≤n, 1≤j≤m} 

{ (u_j,v_j):1≤j≤m}  {(v_j, y_i): với z_j ∈ B_i, 1≤i≤n, 1≤j≤m}  { (y_i, t): 1≤i≤n}

Khả năng thông qua của tất cả các cung được đặt bằng 1. Dễ dàng thấy rằng hệ thống đại diện chung của hai dãy và tồn tại khi và chỉ khi trong mạng G=(V,E) tìm được luồng với giá trị n. Để xét sự tồn tại của luồng như vậy có thể sử dụng thuật toán tìm luồng cực đại từ s đến t trong mạng G=(V, E).