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

Tạp chí Khoa học Đại học Huế: Kỹ thuật và Công nghệ; pISSN 2588-1175 | eISSN 2615-9732 Tập 131, Số 2A, 2022, Tr. 149–157; DOI: 10.26459/hueunijtt.v131i2A.6839 * Liên hệ: nhson@hueuni.edu.vn Nhận bài: 24–06–2022; Ngày nhận đăng: 08–07–2022 TOÁN TỬ BAO ĐÓNG THEO TIẾP CẬN SIÊU ĐỒ THỊ Nguyễn Hoàng Sơn* Trường Đại học Khoa học, Đại học Huế, 77 Nguyễn Huệ, Huế, Việt Nam Tóm tắt. Trong bài báo này chúng tôi nghiên cứu cách tiếp cận một số vấn đề về tổ hợp của toán tử bao đóng bằng mô hình siêu đồ thị. Chúng tôi đưa ra 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. Sử dụng siêu đồ thị, chúng tôi 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. Từ khóa: toán tử bao đóng, nửa dàn giao, khóa tối thiểu, phản khóa, siêu đồ thị Closure operations by hypergraph approach Nguyen Hoang Son* University of Sciences, Hue University, 77 Nguyen Hue St., Hue, Vietnam Abstract. In this paper, we study how to approach some combinatorial problems of closure operations using a hypergraph. We prove that all minimal keys of the closure operations can be represented with the transversal hypergraph of a family. We establish the relationship between anti keys and minimal keys of the closure operations in the hypergraph. Keywords: closure operation, minimal key, anti key, hypergraph 1 Mở đầu Toán tử bao đóng xuất hiện khá lâu trong toán học. Tuy nhiên, khoảng hơn 30 năm trở lại đây, toán tử bao đóng bắt đầu được ứng dụng nhiều vào trong các ngành của khoa học máy tính,

đặc biệt là các lĩnh vực liên quan về dữ liệu như cơ sở dữ liệu, các hệ suy diễn và khai phá dữ liệu [4, 5, 10, 13]. Bên cạnh đó, toán tử bao đóng cũng được phát triển trong nhiều lý thuyết của toán học, khoa học máy tính thời sự như siêu đồ thị, matroid, tập thô, tập mờ, trí tuệ nhân tạo và lý thuyết quyết định [1–3, 8–15]. Trong những vấn đề nghiên cứu về toán tử bao đóng thì những bài toán liên quan đến cấu trúc tổ hợp như tập đóng, khóa và phản khóa, hệ sinh và nửa dàn giao được các nhà nghiên cứu