Nửa vành thứ tự và ứng dụng

NỬA VÀNH THỨ TỰ VÀ ỨNG DỤNG HÀ CHÍ CÔNG Trường THPT Dân tộc nội trú Quảng Ngãi NGUYỄN XUÂN TUYẾN Trường Đại học Sư phạm Đồng Tháp Tóm tắt: Trong bài báo này, chúng tôi đề cập đến việc nhận dạng một số lớp nửa vành thứ tự và giả dàn có là một dàn phân phối hay không, chỉ ra một vài ứng dụng cụ thể của các lớp dàn phân phối cùng với biểu diễn Birkhoff vào việc tìm nghiệm cho một số bài toán tuyến tính thường gặp. 1 GIỚI THIỆU Nội dung bài báo gồm ba mục. Mục 1, nhắc lại một số kết quả cần thiết cho các mục sau. Trong mục 2, chúng tôi nêu lên một số lớp nửa vành thứ tự cụ thể với các loại biểu diễn tương ứng. Mục 3 dành cho việc nêu lên mối liên hệ chặt chẽ của hai thuật toán Monge và Dietrich-Hoffman trong việc chỉ ra nghiệm cho một số bài toán tuyến tính thường gặp. 2 NỬA VÀNH THỨ TỰ VÀ GIẢ DÀN Định nghĩa 2.1. Một biểu diễn của tập sắp thứ tự (hữu hạn) (P,≤) lên dàn (hữu hạn) (L,¹) là một ánh xạ χ : P −→ L thỏa mãn các điều kiện sau: ∀ a, b, c ∈ P ta có, (i) χ(a) ¹ χ(b)⇒ a ≤ b, (ii) a ≤ b ≤ c⇒ χ(a) ∧ χ(c) ¹ χ(b). Nhận xét 2.2. Từ tính chất (i) của Định nghĩa 2.1, ta có χ là một đơn ánh và χ−1 : χ(P ) −→ P là một đồng cấu thứ tự. Định nghĩa 2.3. Cho (L,¹) là một dàn (hữu hạn). Đặt J = J(L) là tập các phần tử bất khả qui của L. Với mỗi x ∈ L ta đặt J(x) = {u ∈ J | u ¹ x}, với mỗi u ∈ J(L) ta có hàm sau đây được gọi là hàm đặc trưng của u: µu : L −→ {0, 1} x 7→ µu(x) = { 1 , u ¹ x 0 , u  x hay µu(x) = { 1 , u ∈ J(x) 0 , u /∈ J(x) . Định nghĩa 2.4. Nếu χ : P −→ L là một hàm biểu diễn của tập sắp thứ tự P lên dàn L thì các hàm χu được xác định như sau được gọi là hàm đặt trưng của χ, với mỗi u ∈ J(L), χu : P −→ {0, 1} a 7→ χu(a) = µu(χ(a)), tức µuχ = χu. Tạp chí Khoa học và Giáo dục, Trường Đại học Sư phạm Huế ISSN 1859-1612, Số 03(11)/2009: tr. 5-14 6 HÀ CHÍ CÔNG - NGUYỄN XUÂN TUYẾN Định nghĩa 2.5. Cho (P,⊕) là một phỏng nhóm, P cùng với quan hệ thứ tự "≤" được gọi là một nửa nhóm thứ tự nếu phép toán ⊕ tương thích với quan hệ thứ tự "≤". Nghĩa là, a, b ≤ a ⊕ b, ∀a, b ∈ P . Ký hiệu (P,⊕,≤). Cho χ : P −→ L là một hàm biểu diễn của nửa nhóm thứ tự (P,⊕,≤) lên dàn L, ta nói χ là cộng tính dưới nếu χu(a ⊕ b) ≤ χu(a) + χu(b), ∀ u ∈ J(L), ∀ a, b ∈ P . Định lý 2.6. [4]. Nếu χ : P −→ L là một hàm biểu diễn của nửa nhóm thứ tự (P,⊕,≤) lên dàn (L,¹) thỏa mãn tính chất cộng tính dưới thì ta có a ⊕ b = a ∨ b, ∀ a, b ∈ P và (P,≤) là một dàn. Định nghĩa 2.7. Một tập sắp thứ tự (P,≤) được trang bị hai phép toán hai ngôi ¯ và ⊕ sao cho a ¯ b ≤ a, b ≤ a ⊕ b, ∀ a, b ∈ P được gọi là nửa vành thứ tự và được ký hiệu (P,¯,⊕,≤). Định nghĩa 2.8. Một tập sắp thứ tự (P,≤) được gọi là một giả dàn nếu ∀ a, b ∈ P , tồn tại hai phần tử thuộc P , ký hiệu là a∧∗ b, a∨∗ b, sao cho a∧∗ b ≤ a, b ≤ a∨∗ b. Hơn nữa, nếu a và b có quan hệ thứ tự với nhau thì a ∨∗ b = max{a, b} và a ∧∗ b = min{a, b}. Định nghĩa 2.9. Cho (P,¯,⊕,≤) là một nửa vành thứ tự (hữu hạn), hàm biểu diễn χ : P −→ L của P lên dàn (hữu hạn) L được gọi là hàm biến điệu trên (dưới) nếu χu(a⊕ b) + χu(a¯ b) ≥ χu(a) + χu(b), ∀ u ∈ J(L), ∀ a, b ∈ P, (χu(a⊕ b) + χu(a¯ b) ≤ χu(a) + χu(b), ∀ u ∈ J(L), ∀ a, b ∈ P ), và χ được gọi là biến điệu nếu χ vừa biến điệu trên vừa biến điệu dưới. Nghĩa là, χu(a⊕ b) + χu(a¯ b) = χu(a) + χu(b), ∀ u ∈ J(L), ∀ a, b ∈ P. Trường hợp (P,≤) là một giả dàn. Khi đó, hàm biểu diễn χ : P −→ L được gọi là biến điệu trên nếu χu(a ∨∗ b) + χu(a ∧∗ b) ≥ χu(a) + χu(b), ∀ u ∈ J(L), ∀ a, b ∈ P, và χ được gọi là biến điệu dưới nếu χu(a ∨∗ b) + χu(a ∧∗ b) ≤ χu(a) + χu(b), ∀ u ∈ J(L), ∀ a, b ∈ P, và χ được gọi là biến điệu nếu χu(a∨∗ b)+χu(a∧∗ b) = χu(a)+χu(b), ∀ u ∈ J(L),∀ a, b ∈ P, với chú ý rằng a ∨∗ b, a ∧∗ b tồn tại theo Định nghĩa 2.8. 3 MỘT SỐ LỚP CÁC NỬA VÀNH THỨ TỰ VỚI HÀM BIỂU DIỄN BIẾN ĐIỆU TRÊN, BIẾN ĐIỆU DƯỚI, BIẾN ĐIỆU 3.1 Lớp nửa vành thứ tự gồm các phản xích của tập sắp thứ tự bộ phận Định nghĩa 3.1. Một phản xích của tập sắp thứ tự (N,≤) là một tập con A của N mà các phần tử trong A không quan hệ với nhau từng đôi một. Ví dụ 3.2. ∅ là một phản xích của tập sắp thứ tự (N,≤). Cho N cùng với quan hệ chia hết là một tập sắp thứ tự. Khi đó, tập các số nguyên tố là một phản xích của N. NỬA VÀNH THỨ TỰ VÀ ỨNG DỤNG 7 Mệnh đề 3.3. Cho N là tập hữu hạn được sắp thứ tự bởi quan hệ "6", gọi A là tập các phản xích trên N . Với mỗi A ∈ A ta xét tập χ(A) = {s ∈ N | s 6 a, a ∈ A}, khi đó P = (A,≤) là một tập sắp thứ tự với quan hệ thứ tự "≤" được xác định như sau: A ≤ B ⇔ χ(A) ⊆ χ(B), ∀ A, B ∈ A. Hơn nữa, χ : P −→ B(N) = (2N ,⊆) A 7−→ χ(A) là một biểu diễn của P lên dàn B(N). Khi đó, (P,¯,⊕) là một nửa vành thứ tự và χ được xác định như trên là một hàm biểu diễn biến điệu dưới, (P,u,⊕) là một nửa vành thứ tự và χ được xác định như trên là một hàm biểu diễn biến điệu, trong đó A⊕B =MAX(A∪B) = {các phần tử cực đại trong A ∪ B}, A ¯ B = A ∩ B, A u B = MAX(χ(A) ∩ χ(B)) = {các phần tử cực đại trong χ(A) ∩ χ(B)}, ∀A, B ∈ P. Chứng minh. * χ : P −→ B(N) = (2N ,⊆) là một biểu diễn của P lên dàn B(N) là rõ. * Chứng minh (P,¯,⊕) là một nửa vành thứ tự. ∀ A, B ∈ A khi đó, A ¯ B = A ∩ B ⊆ A và A ¯ B ⊆ B ⇒ χ(A ∩ B) ⊆ χ(A) và χ(A ∩B) ⊆ χ(B)⇒ A¯B ≤ A và A¯B ≤ B. Mặt khác, A⊕B = {các phần tử cực đại của A∪B} nên một phần tử x thuộc A⊕B nếu x chỉ có thể là (x ∈ A ∩ B) hoặc (x ∈ A\B mà sao cho x không quan hệ với bất kỳ phần tử nào của A∪B hoặc nếu có y ∈ B để x và y quan hệ nhau thì chỉ có thể là y 6 x) hoặc (x ∈ B\A mà sao cho x không quan hệ với bất kỳ phần tử nào trong A ∪ B hoặc nếu có z ∈ A sao cho x và z quan hệ với nhau thì chỉ có thể là z 6 x). ∀ s ∈ χ(A)⇔ ∃a ∈ A sao cho s 6 a khi đó, Nếu a không quan hệ với bất kỳ phần tử nào khác trongA∪B thì a ∈ A⊕B ⇒ s ∈ χ(A⊕B). Nếu a có quan hệ với ít nhất một phần tử b ∈ B thì a ∈ A\B và + Nếu b 6 a thì a ∈ A⊕B (vì nếu không thì tồn tại b′ ∈ B sao cho a a > b ⇒ b′ > b, điều này mâu thuẫn với B là một phản xích) suy ra s ∈ χ(A⊕B). + Nếu a 6 b thì b ∈ A ⊕ B (vì nếu không thì tồn tại a′ ∈ A sao cho b b > a ⇒ a′ > a, điều này mâu thuẫn với A là một phản xích) suy ra s ∈ χ(A ⊕ B) (do s 6 a 6 b ∈ A⊕B). Vậy χ(A) ⊆ χ(A⊕B)⇒ A ≤ A⊕B. Trường hợp B ≤ A⊕B được chứng minh tương tự. * Chứng minh χ : (P,¯,⊕) −→ B(N) là một hàm biến điệu dưới. Ta có J(B(N)) = {{u} | u ∈ N}, để tiện cho việc trình bày ta viết χu(−) thay cho χ{u}(−). ∀ u ∈ N, ∀ A, B ∈ A ta có, χu(A⊕B)+χu(A¯B) = χu(A⊕B)+χu(A∩B) ≤ χu(A) + χu(B). Thật vậy, + Nếu χu(A⊕B) = 0 thì u /∈ χ(A⊕B)⇒ u /∈ χ(A∩B) (do A∩B ⊆ A⊕B ⇒ χ(A∩B) ⊆ χ(A⊕B)) suy ra χu(A ∩B) = 0 suy ra bất đẳng thức trên đúng. + Nếu χu(A ∩ B) = 1 thì u ∈ χ(A ∩ B) ⊆ χ(A ⊕ B) ⇒ u ∈ χ(A ⊕ B) ⇒ χu(A ⊕ B) = 1 suy ra χu(A¯B) + χu(A⊕B) = 2. Mặt khác, A ∩ B ⊆ A, B nên χ(A ∩ B) ⊆ χ(A), χ(A ∩ B) ⊆ χ(B) suy ra u ∈ χ(A) và u ∈ χ(B)⇒ χu(A) = χu(B) = 1⇒ χu(A) + χu(B) = 2 suy ra bất đẳng thức trên đúng. 8 HÀ CHÍ CÔNG - NGUYỄN XUÂN TUYẾN + Nếu χu(A ∩ B) = 0 và χu(A ⊕ B) = 1 thì { u /∈ χ(A ∩B) u ∈ χ(A⊕B) ⇒ ∃x ∈ (A ∪ B)\(A ∩ B) sao cho u 6 x (do A ⊕ B ⊆ A ∪ B). Do x ∈ (A ∪ B)\(A ∩ B) nên x ∈ A hoặc x ∈ B suy ra u ∈ χ(A) ∪ χ(B)⇒ χu(A) + χu(B) ≥ 1 = χu(A¯B) + χu(A⊕B). Vậy χ là hàm biến điệu dưới. * Chứng minh χ là hàm biểu diễn biến điệu. ∀ u ∈ N, ∀ A, B ∈ P ta cần chứng minh χu(A⊕B) + χu(A uB) = χu(A) + χu(B). + Nếu u ∈ χ(A uB) thì u ∈ χ(A), u ∈ χ(B), u ∈ χ(A⊕B) (do A uB ≤ A,B ≤ A⊕B ⇒ χ(AuB) ⊆ χ(A), χ(B) ⊆ χ(A⊕B)) suy ra χu(A⊕B)+χu(AuB) = 2 = χu(A)+χu(B). + Nếu u /∈ χ(A⊕B) thì χu(A⊕B) + χu(A uB) = 0 = χu(A) + χu(B) + Nếu u ∈ χ(A⊕B), u /∈ χ(A) thì u /∈ χ(A uB) suy ra χu(A⊕B) + χu(A uB) = 1. Do u ∈ χ(A ⊕ B) nên tồn tại m ∈ A ⊕ B sao cho u 6 m và do u /∈ χ(A) nên m ∈ B\A thì u ∈ χ(B)⇒ χu(B) = 1 suy ra χu(A) + χu(B) = 1. Vậy χu(A⊕B) + χu(A uB) = 1 = χu(A) + χu(B). Trường hợp u ∈ χ(A⊕B), u /∈ χ(B) chứng minh tương tự. + Nếu u ∈ χ(A) ∩ χ(B) thì u ∈ χ(A⊕B) và tồn tại a ∈ A, b ∈ B sao cho u 6 a và u 6 b suy ra tồn tại m ∈ AuB sao cho u 6 m⇒ u ∈ χ(AuB) suy ra χu(A⊕B)+χu(AuB) = 2 = χu(A) + χu(B). Nhận xét 3.4. Từ Mệnh đề 3.3 ta có một số nhận xét sau: Nếu (N,6) thỏa điều kiện ∀ A, B ∈ A mà A ∪B là một phản xích và A ⊕ B = A ∪ B thì χ là biến điệu. Điều này hoàn toàn có thể xảy ra, chẳng hạn như ta lấy N = {các số nguyên tố} là một phản xích của tập các số tự nhiên N với quan hệ chia hết. Khi đó, hợp của hai phản xích của N lại là một phản xích và do đó A ⊕ B = {các phần tử cực đại của A ∪B} = A ∪B. 3.2 Lớp nửa vành thứ tự gồm các hệ đóng, hệ đối đóng trên tập cho trước Định nghĩa 3.5. Họ F ⊆ 2N được gọi là một hệ đóng trên tập N nếu F thỏa mãn hai điều kiện sau: (i) N ∈ F , (ii) ⋂ S∈C⊆F S ∈ F , ∀ C ⊆ F . Bao đóng của một tập S ⊆ N đối với F là S = ∩{F ∈ F | S ⊆ F}. Mệnh đề 3.6. [4]. Cho F là một hệ đóng trên N , khi đó (F ,⊆) là một dàn và là một nửa vành thứ tự với các phép toán S ⊕ T = S ∪ T , S ¯ T = S ∩ T, ∀ S, T ∈ F . Mệnh đề 3.7. [4]. Cho N là tập hữu hạn, F là một hệ đóng trên N . Khi đó, ánh xạ i : (F ,¯,⊕) −→ B(N) = (2N ,⊆) S 7−→ S là một hàm biểu diễn biến điệu trên của F lên dàn B(N). NỬA VÀNH THỨ TỰ VÀ ỨNG DỤNG 9 Định nghĩa 3.8. Cho G là một họ các tập con của N và F là một hệ đóng trên N . Khi đó, G được gọi là thỏa mãn tính chất (∗) ứng với một hệ đóng F trên N nếu với mỗi S ∈ F tồn tại duy nhất tập GS ∈ G sao cho, ∀ S, T, V ∈ F ta có: (i) GS = S, (ii) S ⊆ T ⊆ V ⇒ GS ∩GV ⊆ GT , (iii) GS⊕T ⊆ GS ∪GT và GS∩T ⊆ GS ∩GT . Ví dụ 3.9. Cho N = {a, b, c, d}, N4 = {∅, {a}, {b, d}, N} là một hệ đóng trên N . Khi đó, G = {∅, {a}, {b}, {a, b}} là thỏa mãn tính chất (∗). Thật vậy, ∅ = ∅, {a} = {a}, {b} = {b, d}, {a, b} = N. ∅ ⊆ {a} ⊆ N ⇒ G∅ ∩GN = ∅ ⊆ G{a} = {a}. ∅ ⊆ {b, d} ⊆ N ⇒ G∅ ∩GN = ∅ ⊆ G{b,d} = {b}. G∅⊕{a} = G{a} = {a} = G∅ ∪G{a}. G∅⊕{b,d} = G{b,d} = {b} = G∅ ∪G{b,d}. G∅⊕N = GN = {a, b} = G∅ ∪GN . G{a}⊕{b,d} = G{a,b,d} = GN = {a, b} = {a} ∪ {b} = G{a} ∪G{b,d}. G{a}⊕N = GN = {a, b} = G{a} ∪GN . G{b,d}⊕N = GN = {a, b} = G{b,d} ∪GN . Mặt khác, G∅∩{a} = G∅∩{b,d} = G∅∩N = G{a}∩{b,d} = ∅. G{a}∩N = G{a} = {a} = G{a} ∩GN . G{b,d}∩N = G{b,d} = {b} = G{b,d} ∩GN . Mệnh đề 3.10. [4]. Cho N là tập hữu hạn phần tử, F là một hệ đóng trên N và G là một họ các tập con của N ứng với F thỏa mãn tính chất (∗). Khi đó, χ : F −→ B(N) = (2N ,⊆) là hàm biểu diễn biến điệu dưới. S 7−→ GS Định nghĩa 3.11. Cho F là một họ các tập con của tập hữu hạn N . Khi đó, F được gọi là hệ đối đóng trên N nếu thỏa mãn các điều kiện sau: (i) ∅ ∈ F , (ii) S ∪ T ∈ F , ∀ S, T ∈ F . Mệnh đề 3.12. [4]. Cho F là một hệ đối đóng trên tập N . Khi đó, F là một nửa vành thứ tự với các phép toán S⊕T = S ∪T và S¯T = ∪{A ∈ F | A ⊆ S ∩T}, ∀ S, T ∈ F , và ánh xạ sau là một hàm biểu diễn biến điệu dưới của F trong B(N) : i : (F ,⊆) −→ B(N) = (2N ,⊆) S 7−→ S 3.3 Lớp nửa vành thứ tự gồm các tập đóng của không gian tôpô hữu hạn Cho (U,Γ) là một không gian tôpô với U là tập hữu hạn, F là tập gồm tất cả các tập đóng của (U,Γ). Trên F ta trang bị quan hệ thứ tự bao hàm và hai phép toán S⊕T = S ∪T và 10 HÀ CHÍ CÔNG - NGUYỄN XUÂN TUYẾN S¯T = S∩T, ∀ S, T ∈ F , khi đó dễ dàng kiểm chứng được (F ,¯,⊕,⊆) là một nửa vành thứ tự. (F ,⊆) là một dàn với S∨T = S∪T = S⊕T, S∧T = S∩T = S¯T, ∀ S, T ∈ F . Xét một hàm biểu diễn của nửa vành thứ tự F lên dàn 2U sau: i : (F ,⊆) −→ (2U ,⊆) với i(S) = S, ∀ S ∈ F . Khi đó, ∀ u ∈ U và ∀ S, T ∈ F ta có, i{u}(S⊕T )+i{u}(S¯T ) = i{u}(S∪T )+i{u}(S∩T ) = i{u}(S) + i{u}(T ) suy ra i là hàm biến điệu. 4 MỘT VÀI ỨNG DỤNG CỦA NỬA VÀNH THỨ TỰ VÀ GIẢ DÀN Định lý 4.1. [4]. Cho (P,¯,⊕,≤) là một nửa vành thứ tự (hữu hạn). Khi đó, P là một dàn phân phối khi và chỉ khi tồn tại dàn L và một hàm biểu diễn χ : P −→ L của P lên L thỏa mãn điều kiện cộng tính dưới và biến điệu trên. Hệ quả 4.2. Cho (L,≤) là một giả dàn hữu hạn, χ : L −→ (L′,¹) là một hàm biểu diễn biến điệu của L lên dàn (L′,¹) (hữu hạn). Khi đó, L là một dàn phân phối. Chứng minh. Trước hết, ta chứng minh L là một dàn. ∀ a, b ∈ L⇒ ∃ a ∨∗ b, a ∧∗ b ∈ L sao cho a ∧∗ b ≤ a, b ≤ a ∨∗ b. Đặt d = a ∨∗ b, ta chứng minh d = a∨ b. Nghĩa là cần chứng minh, ∀ c ∈ L sao cho a, b ≤ c⇒ d ≤ c. Thật vậy, giả sử d  c thì ta có a ∧∗ b ≤ a, b ≤ c < c ∨∗ d (do L là giả dàn). Khi đó, χ(c ∨∗ d) không là phần tử bé nhất của dàn L′. Mặt khác, c < c ∨∗ d nên suy ra J(χ(c ∨∗ d)) * J(χ(c))⇒ ∃ u ∈ J(χ(c ∨∗ d))\J(χ(c)). Do χ là hàm biến điệu nên χu(c ∨∗ d) + χu(c ∧∗ d) = χu(c) + χu(d). (1) Ta có χu(c ∨∗ d) = 1, χu(c) = 0 nên từ (1) suy ra χu(d) = 1 và χu(c ∧∗ d) = 0 suy ra u ∈ J(χ(d)) suy ra χu(a∨∗ b)+χu(a∧∗ b) = χu(a)+χu(b)⇒ χu(a)+χu(b) ≥ χu(a∨∗ b) = χu(d) = 1 suy ra ít nhất một trong hai giá trị χu(a) hoặc χu(b) nhận giá trị là 1. Nếu χu(a) = 1 thì u ∈ J(χ(a)). Ta có a ≤ c < c ∨∗ d⇒ χ(a) ∧ χ(c ∨∗ d) ¹ χ(c). (2) Ta lại có, J(χ(a) ∧ χ(c ∨∗ d)) ⊆ J(χ(c)) (3) và J(χ(a) ∧ χ(c ∨∗ d)) = J(χ(a)) ∩ J(χ(c ∨∗ d)) (4). Từ (2), (3) và (4) suy ra J(χ(a))∩J(χ(c∨∗d)) ⊆ J(χ(c)) suy ra u ∈ J(χ(a))∩J(χ(c∨∗d)) ⊆ J(χ(c)) ⇒ u ∈ J(χ(c)), điều này mâu thuẫn với u ∈ J(χ(c ∨∗ d))\J(χ(c)). Trường hợp χu(b) = 1 được chứng minh tương tự. Vậy d ≤ c hay L là một dàn với a ∧∗ b = a ∧ b = ∨{e ∈ L | e ≤ a, e ≤ b}, ∀ a, b ∈ L, và do χ thỏa mãn tính chất cộng tính dưới và biến điệu trên nên áp dụng Định lý 4.1 ta có L là một dàn phân phối. Nhận xét 4.3. Từ Định lý 4.1 ta có các lớp nửa vành thứ tự ở mục 2 cùng với các hàm biểu diễn biến điệu trở thành một dàn phân phối. Nói riêng, cho N = {các số nguyên tố} cùng với quan hệ chia hết tạo thành một phản xích đã được đề cập ở Nhận xét 3.4. Khi đó, nửa vành thứ tự (P,¯,⊕) nêu trong Mệnh đề 3.3 trở thành P = 2N là một dàn phân phối và ∀ A ∈ P thì χ(A) có dạng ∅ hoặc A∪ {1}. Do đó, ∀ A,B ∈ P sao cho A ≤ B ⇔ χ(A) ⊆ χ(B)⇔ A ⊆ B. NỬA VÀNH THỨ TỰ VÀ ỨNG DỤNG 11 4.1 Bài toán 1 Cho L là một dàn (hữu hạn), χ : L −→ (2U ,⊆) là một hàm biểu diễn biến điệu, U là một tập nền cho trước. Giả sử rằng ⋃ a∈L χ(a) = U và cho trước hàm trọng số c : U −→ R với c(u) = cu, ∀u ∈ U. Tìm một hàm y : L −→ R sao cho y(a) = ya ≥ 0, ∀ a ∈ L (I)∑ u∈χ(a) ya ≥ cu, ∀ u ∈ U (II) . Ta xét thuật toán Monge cho bài toán (I)− (II) như sau: Bước 1. Chọn m là phần tử cực đại của dàn L và chọn ra một cặp Monge (m∗, u∗). Nghĩa là, chọn m∗ ∈ l(m) = {m′ ∈ L | m phủ m′} và u∗ ∈ χ(m)\χ(m∗) sao cho c∗ = min m′∈l(m) max{cu | u ∈ χ(m)\χ(m′)} = cu∗ . Bước 2. Đặt ym = max{0, c∗} và thay đổi các trọng số của các phần tử u ∈ χ(m) lại là cu − ym. Bước 3. Thay L bởi L∗ = {a ∈ L | a ≤ m∗}. Bước 4. Nếu L = ∅ thì dừng thuật toán, nếu L 6= ∅ thì ta quay lại Bước 1. Mệnh đề 4.4. [3]. Nếu M = {m1 < m2 < · · · < mk} ⊆ L là xích Monge có được khi thuật toán Monge kết thúc thì hàm sau đây là nghiệm của bài toán (I)− (II) : y : L −→ R a 7−→ y(a) = { ya nếu a ∈M 0 nếu a /∈M 4.2 Bài toán 2 Cho L là một dàn (hữu hạn), χ : L −→ (2U ,⊆) là một hàm biểu diễn biến điệu, U là tập nền cho trước, giả sử ⋃ a∈L χ(a) = U và hàm trọng số cho trước c : U −→ R với c(u) = cu, ∀u ∈ U. Tìm hàm y : L −→ R sao cho y(a) = ya ≥ 0, ∀ a ∈ L (III)∑ u∈χ(a) ya = cu, ∀ u ∈ U (IV ) . Xét thuật toán Dietrich-Hoffman cho bài toán (III)− (IV ) như sau: Bước 1. Đặt m ∈ L là phần tử cực đại của dàn L, chọn u ∈ χ(m) sao cho c = cu = min{cu | u ∈ χ(m)}. Bước 2. Đặt ym = c và thay đổi trọng số của các phần tử trong tập χ(m) lại như sau cu − ym, ∀ u ∈ χ(m). 12 HÀ CHÍ CÔNG - NGUYỄN XUÂN TUYẾN Bước 3. Thay L bởi L = L\u = {a ∈ L | u /∈ χ(a)}. Bước 4. Nếu L = ∅ thì dừng thuật toán, nếu không thì quay lại Bước 1. Mệnh đề 4.5. Tập L được xác định như trong Bước 3 của thuật toán Dietrich-Hoffman là một dàn phân phối. Chứng minh. Để tiện cho việc trình bày, trong phần chứng minh dưới đây ta viết χu(−) thay cho χ{u}(−). Trước hết, ta chứng minh L là một giả dàn. Thật vậy, ∀ a, b ∈ L ta có, do L là một dàn nên tồn tại a ∨ b, a ∧ b ∈ L sao cho a ∧ b ≤ a, b ≤ a ∨ b. Do χ là hàm biểu diễn biến điệu nên χu(a ∨ b) + χu(a ∧ b) = χu(a) + χu(b). Mặt khác, a, b ∈ L nên u /∈ χ(a), u /∈ χ(b) ⇒ χu(a) = χu(b) = 0, mà χu(a ∨ b) ≥ 0, χ(a ∧ b) ≥ 0 suy ra χu(a ∨ b) = χu(a ∧ b) = 0⇒ u /∈ χ(a ∨ b) và u /∈ χ(a ∧ b) hay a ∨ b và a ∧ b thuộc L. Hơn nữa, nếu a ≤ b thì a ∨ b = b = max{a, b} và a ∧ b = a = min{a, b}. Vậy L là một giả dàn. Áp dụng Hệ quả 4.2 ta có ngay L là một dàn phân phối. Định lý 4.6. [3]. Nếu bài toán (III)− (IV ) có nghiệm là y thì thuật toán Monge của bài toán (I)− (II) cũng sẽ cho ta nghiệm y của bài toán (III)− (IV ). 4.3 Biểu diễn Birkhoff Trong phần này, chúng tôi quan tâm đến nghiệm của bài toán (III)− (IV ) được xét trong trường hợp cụ thể. L là một dàn phân phối (hữu hạn), χ được xét ở đây là hàm biểu diễn Birkhoff của dàn L. Mệnh đề 4.7. Cho L là dàn phân phối (hữu hạn), J = J(L) = {u ∈ L | u bất khả qui} và J(a) = {u ∈ J | u ≤ a}, ∀ a ∈ L. Khi đó, ta có các đẳng thức sau: (i) J(a ∨ b) = J(a) ∪ J(b), (ii) J(a ∧ b) = J(a) ∩ J(b). Chứng minh. (i). ∀ u ∈ J(a∨ b)⇒ u ≤ a∨ b. Do u là bất khả qui và L là dàn phân phối nên u ≤ a hoặc u ≤ b⇒ u ∈ J(a) hoặc u ∈ J(b)⇒ u ∈ J(a) ∪ J(b). Ngược lại, ∀ u ∈ J(a)∪J(b)⇒ u ∈ J(a) hoặc u ∈ J(b)⇒ u ≤ a hoặc u ≤ b⇒ u ≤ a∨ b⇒ u ∈ J(a ∨ b). Vậy J(a ∨ b) = J(a) ∪ J(b). (ii). ∀ u ∈ J(a ∧ b)⇒ u ≤ a ∧ b⇒ { u ≤ a u ≤ b ⇒ { u ∈ J(a) u ∈ J(b) ⇒ u ∈ J(a) ∩ J(b). Ngược lại, ∀ u ∈ J(a) ∩ J(b) ⇒ { u ∈ J(a) u ∈ J(b) ⇒ { u ≤ a u ≤ b ⇒ u ≤ a ∧ b ⇒ u ∈ J(a ∧ b). Vậy J(a ∧ b) = J(a) ∩ J(b). Mệnh đề 4.8. [3]. Cho L là một dàn phân phối (hữu hạn) và J là tập các phần tử bất khả qui của L. Khi đó, hàm sau là biểu diễn biến điệu, còn gọi là hàm biểu diễn Birkhoff: χ : L −→ (2J ,⊆) a 7−→ J(a) NỬA VÀNH THỨ TỰ VÀ ỨNG DỤNG 13 Ví dụ 4.9. Xét N = {2, 3, 5} là tập ba số nguyên tố đầu tiên, cùng với quan hệ chia hết tạo thành một phản xích. Khi đó, nửa vành thứ tự (P,¯,⊕) được xét trong Mệnh đề 3.3 là một dàn phân phối và có đồ thị như sau: {2, 3, 5} tt tt tt tt t JJ JJ JJ JJ J {2, 3} JJJ JJJ JJJ J {2, 5} ttt ttt ttt t JJJ JJJ JJJ J {3, 5} ttt ttt ttt t {2} JJ JJ JJ JJ JJ J {3} {5} tt tt tt tt tt t ∅ Xét bài toán (III)− (IV ) ứng với dàn phân phối L = (P,¯,⊕) với J(P ) = {{2}, {3}, {5}} và hàm biểu diễn Birkhoff tương ứng. Cho trước hàm trọng số c : J(P ) −→ R với c({2}) = c2 = 2; c({3}) = c3 = 3; c({5}) = c5 = 5. Bây giờ ta chạy thuật toán Dietrich-Hoffman như sau: Bước 1. Chọn m = {2, 3, 5} ⇒ χ(m) = {{2}, {3}, {5}}, ta có c = c2 = 2 và u = {2}. Bước 2. y{2,3,5} = 2 và thay lại trọng số của các phần tử trong χ(m) lại là c2 := 0, c3 := 1, c5 := 3. Bước 3. L = {∅, {3}, {5}, {3, 5}} 6= ∅, ta quay lại bước 1. Bước 1’. Chọn m′ = {3, 5} ⇒ χ(m′) = {{3}, {5}}, ta có c′ = c3 = 1 và u′ = {3}. Bước 2’. y{3,5} = 1 và thay lại trọng số của các phần tử trong χ(m′) lại là c3 := 0, c5 := 2. Bước 3’. L′ = {∅, {5}} 6= ∅, ta quay lại bước 1. Bước 1". Chọn m” = {5} ⇒ χ(m”) = {{5}}, ta có c” = c5 = 2 và u” = {5}. Bước 2". y{5} = 2 và thay lại trọng số của các phần tử trong χ(m”) lại là c5 = 0. Bước 3". L” = {∅} 6= ∅, ta quay lại bước 1. Bước 1"’. Chọn m”′ = ∅ ⇒ χ(m”′) = ∅ nên ta dừng thuật toán. Ta có y{2,3,5} = 2, y{3,5} = 1, y{5} = 2. Khi đó, tại {2} ∈ J(P ), y{2,3,5} = 2 = c2 (do {2} ∈ χ({2, 3, 5})), tại {3} ∈ J(P ), y{2,3,5} + y{3,5} = 2 + 1 = 3 = c3 (do {3} ∈ χ({2, 3, 5}) và {3} ∈ χ({3, 5})), tại {5} ∈ J(P ), y{2,3,5} + y{3,5} + y{5} = 2 + 1 + 2 = 5 = c5 (do {5} ∈ χ({5}) và {5} ∈ χ({2, 3, 5}) và {5} ∈ χ({3, 5})). Vậy bài toán (III) − (IV ) có nghiệm y : L −→ R là: y({2, 3, 5}) = 2; y({2, 3}) = 0; y({2, 5}) = 0; y({3, 5}) = 1; y({2}) = 0; y({3}) = 0; y({5}) = 2; y(∅) = 0. Áp dụng Định lý 4.6, khi thuật toán Monge cho bài toán (I)− (II) tương ứng kết thúc sẽ cho ta nghiệm của bài toán (III)− (IV ), chính là hàm y được xác định như trên, do xích Monge có được khi thuật toán Monge kết thúc là M = {{5} ⊆ {3, 5} ⊆ {2, 3, 5}}. 5 KẾT LUẬN Trong bài báo này, chúng tôi đã đưa ra được hai lớp nửa vành thứ tự là lớp các phản xích của một tập sắp thứ tự cho trước (Mệnh đề 3.3) và lớp các nửa vành thứ tự gồm các tập đóng của một không gian tôpô hữu hạn và kiểm chứng được chúng là một dàn phân phối nhờ vào Định lý 4.1. Đưa ra một dấu hiệu nhận diện một giả dàn có là một dàn phân phối 14 HÀ CHÍ CÔNG - NGUYỄN XUÂN TUYẾN không (Hệ quả 4.2), chứng minh được một số tính chất của dàn phân phối (Mệnh đề 4.5, Mệnh đề 4.7), cho một ví dụ về họ tập thỏa mãn tính chất (∗) (Ví dụ 3.9), một ví dụ chạy thuật toán Dietrich-Hoffman cho dàn các phản xích của tập gồm ba số nguyên tố đầu tiên ứng với biểu diễn Birkhoff để tìm nghiệm của bài toán tuyến tính (III)− (IV ) (Ví dụ 4.9). TÀI LIỆU THAM KHẢO [1] G.Birkhoff (1948), Vol.25, Lattice theory, American Mathematical Society. [2] B.L.Dietrich and A.J.Hoffman (2003), On greedy algorithms , partially ordered sets and submodular functions, IBM J.Res. and Dev. 47, pp.25-30. [3] U.Faigle and B.Pies (2006), Note on Pseudolattices, Lattices and Submodular Linear Programs, ZAIK. Vol 80, pp.1-16. [4] U.Faigle and B.Pies (2006), Note on representations of ordered semirings, ZAIK. Vol 80, pp.1-14. [5] U.Kru¨ger (2000), Structural aspects of ordered polymatroids, Discr. Appl. Math, pp.125-148. Title: ORDERED SEMIRINGS AND APPLICATIONS Abstract: In this paper we find some classis of such ordered semirings and pseudolattices that can be distributed lattices. Besides, we give some concrete applications of distributive lattices with Birkhoff’s representations to find feasible solutions for some linear programs. HÀ CHÍ CÔNG GV Toán, Trường THPT Dân tộc nội trú Quảng Ngãi. PGS. TSKH. NGUYỄN XUÂN TUYẾN GV Khoa Toán, Trường Đại học Sư phạm Đồng Tháp.