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

Bài viết Nửa vành thứ tự và ứng dụng trình bày: Đề 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,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Nửa vành thứ tự và ứng dụngNỬA VÀNH THỨ TỰ VÀ ỨNG DỤNGHÀ CHÍ CÔNGTrường THPT Dân tộc nội trú Quảng NgãiNGUYỄN XUÂN TUYẾNTrường Đại học Sư phạm Đồng ThápTóm tắt: Trong bài báo này, chúng tôi đề cập đến việc nhận dạng mộtsố 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ớibiểu diễn Birkhoff vào việc tìm nghiệm cho một số bài toán tuyến tínhthường gặp.1 GIỚI THIỆUNộ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ễntươ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 Mongevà 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ấtkhả 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àmsau đây được gọi là hàm đặc trưng của u:µu : L −→ {0, 1}x 7→ µu (x) =(1, u¹x0, ux(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 Lthì 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-146HÀ 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ự ≤ đượcgọ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ĩalà, a, b ≤ a ⊕ b, ∀a, b ∈ P . Ký hiệu (P, ⊕, ≤). Cho χ : P −→ L là một hàm biểu diễncủ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ồntạ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à χ đượcgọ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ỆUTRÊN, BIẾN ĐIỆU DƯỚI, BIẾN ĐIỆU3.1Lớ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.7NỬA VÀNH THỨ TỰ VÀ ỨNG DỤNGMệ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ácphả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),Hơn nữa,∀ A, B ∈ 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à χ đượcxá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 = M AX(A ∪ B) ={các phần tử cực đại trong A ∪ B}, A ¯ B = A ∩ B, A u B = M AX(χ(A) ∩ χ(B)) ={các phần tử cực đại trong χ(A) ∩ χ(B)}, ∀A, ...