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,. . | 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 . 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 . Từ tính chất (i) của Định nghĩa , ta có χ là một đơn ánh và χ−1 : χ(P ) −→ P là một đồng cấu thứ tự. Định nghĩa . 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 . 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 . 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
