TOÁN TỬ BAO ĐÓNG THEO TIẾP CẬN SIÊU ĐỒ THỊ

Nguyễn Hoàng Sơn Tập 131, Số 2A, 2022 156 (3) Ánh xạ tịnh tiến → : ( ) ( ) M t U U xác định bởi ( ) M t X X M =  vớiM là tập con cho trước củaU và . X U  Ta có   ( ) : M C t U M X X U = − −  ,     ( ) : =  − M Min t a a U M và   ( ( )) = − M Tr Min t U M . Như vậy,   ( ) = − M Key t U M và   ( ) : = −  − Antikey i U a a U M . Ví dụ 4.2. Xét ánh xạ → : ( ) ( ) a f U U với  a U và   =   , ( ) , .a U neu a X f X X nguoc lai Dễ kiểm chứng được  ( ) a f Cl U . Khi đó   ( ) ( ) : = −  a C f U f X X U và do đó     ( ) = Min f a ,     ( ( )) = Tr Min f a . Như vậy,     = ( ) Key f a và   ( ) = − Antikey f U a . 5 Kết luận Sử dụng mô hình siêu đồ thị, chúng tôi đưa ra được biểu diễn tất cả khóa tối thiểu của toán tử bao đóng qua siêu đồ thị transversal của một họ. Sau đó thiết lập mối quan hệ giữa phản khóa và khóa tối thiểu của toán tử bao đóng bằng siêu đồ thị. Điều này mở ra hướng tiếp cận bằng siêu đồ thị cho các vấn đề tổ hợp trên toán tử bao đóng. Đặc biệt, có thể sử dụng Thuật toán 2.1 để tính các cấu trúc tổ hợp của toán tử bao đóng một cách hữu hiệu, cũng như ứng dụng vào trong một số bài toán của hệ thống thông tin, chẳng hạn như rút gọn thuộc tính [9]. Tài liệu tham khảo 1. Berge C. (1989), Hypergraphs: combinatorics of finite sets, North – Holland, Amsterdam. 2. Bertet K., Demko C., Viaud J., Guéri C. (2018), Lattices, closures systems and implication bases: a survey of structural aspects and algorithms, Theoretical computer science, 743, 93−109.