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

Nguyễn Hoàng Sơn Tập 131, Số 2A, 2022 150 quan tâm phát triển. Tuy nhiên, phần lớn các bài toán về tổ hợp này rất khó; độ phức tạp của các bài toán này thường cỡ NP đầy đủ trở lên. Trong bài báo này, chúng tôi nghiên cứu một số vấn đề về tổ hợp của toán tử bao đóng bằng mô hình siêu đồ thị. Đây là công cụ toán học chuyên giải quyết các vấn đề về tổ hợp rất hiệu quả và được các nhà nghiên cứu sử dụng nhiều trong thời gian gần đây [1, 6, 7, 12]. Cụ thể, bài báo quy dẫn được bài toán xác định tất cả khóa tối thiểu của toán tử bao đóng về bài toán tính siêu đồ thị transvesal 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 các toán tử bao đóng theo siêu đồ thị. Cách tiếp cận này mở ra hướng nghiên cứu về toán tử bao đóng bằng mô hình siêu đồ thị. Với mục đích như vậy, cấu trúc bài báo chia làm năm phần. Sau phần mở đầu, phần thứ 2 trình bày toán tử bao đóng, nửa dàn giao, siêu đồ thị và một số kết quả cơ sở. Phần thứ 3 giới thiệu bài toán về khóa tối thiểu của toán tử bao đóng. Trong phần này, chúng tôi biểu diễn các khóa tối tiểu của toán tử bao đóng bằng siêu đồ thị transversal. Chúng tôi chứng minh rằng tất cả khóa tối thiểu của toán tử bao đóng đều sinh ra từ siêu đồ thị transversal của một họ. Trong phần 4, chúng tôi đề cập đến phản khóa của toán tử bao đóng và 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 qua siêu đồ thị. Phần cuối cùng của bài báo là kết luận. 2 Các khái niệm cơ sở XétU là một tập hữu hạn khác rỗng bất kỳ. Ký hiệu ( ) U là tập lũy thừa củaU . Ánh xạ → : ( ) ( ) f U U thỏa các điều kiện sau:

(i)  ( ) X f X (ii)    ( ) ( ) X Y f X f Y (iii) = ( ( )) ( ) f f X f X với mọi  , X Y U , được gọi là một toán tử bao đóng (TTBĐ) trênU . Ký hiệu ( ) Cl U là tập tất cả các TTBĐ trênU . Tập  X U được gọi là đóng của  ( ) f Cl U nếu = ( ) f X X . Tập tất cả các tập đóng củaf ký hiệu là ( ) Closed f . Họ  ( ) U được gọi là nửa dàn giao trênU nếu các điều kiện sau là đúng: (i)  U

jos.hueuni.edu.vn Tập 131, Số 2A, 2022 151 (ii)        ( ), U . Rõ ràng ( ) Closed f là một nửa dàn giao. Có thể thấy [5] nếu là một nửa dàn giao thì ánh xạf xác định theo   =   ( ) : f X Y X Y là một TTBĐ. Ngược lại, nếu  ( ) f Cl U thì tồn tại duy nhất một nửa dàn giao trênU sao cho = f f , với   =  = : ( ) X U f X X . Một họ   =  = : ( ), 1,2, , i i E E U i m được gọi là siêu đồ thị trênU nếu   i E với mọi i. Khi đó, mỗi phần tử  a U được gọi là một đỉnh và mỗi tập i E được gọi là một siêu cạnh hay cạnh của . Lưu ý rằng một số tác giả, chẳng hạn [1], yêu cầu tập các siêu cạnh cũng như mỗi siêu cạnh phải khác rỗng và hợp tất cả các siêu cạnh phải bằng tập đỉnh. Trong bài báo này, chúng tôi không yêu cầu như vậy. Ký hiệu ( ) HG U là tập tất cả siêu đồ thị trênU . Một siêu đồ thị được gọi là đơn nếu với mọi    = , , i j i j i j E E E E E E . Tập tất cả siêu đồ thị đơn trênU được ký hiệu là ( ) SG U . Một tập  T U được gọi là một transversal của  ( ) HG U nếu với mọi  E ta có    T E . Ký hiệu ( ) Trs là tập tất cả các transversal của . Một transversal  ( ) T Trs được gọi là tối thiểu nếu không tồn tại một tập con thật sự ' T củaT sao cho  ) ' ( Trs T . Tập tất cả các transversal tối tiểu của còn được gọi siêu đồ thị transversal của , và ký hiệu là ( ) Tr . Như vậy, có thể thấy  ( ) ( ) Tr SH U . Siêu đồ thị transversal có các tính chất cơ bản sau đây. Mệnh đề 2.1. [1] Cho  1 2 , ( ) SH U . Ta có (1) =  = 1 2 2 1 ( ) ( ) Tr Tr . (2) =  = 1 2 1 2 ( ) ( ) Tr Tr . (3) = 1 1 ( ( )) Tr Tr .

Nguyễn Hoàng Sơn Tập 131, Số 2A, 2022 152 Siêu đồ thị transversal có rất nhiều ứng dụng trong nhiều lĩnh vực của khoa học máy tính. Thuật toán tổ hợp tìm siêu đồ thị transversal rất hiệu quả đã được đề xuất như sau. Thuật toán 2.1. [6] (Tìm siêu đồ thị transversal) Đầu vào:   =  1 2 , , , ( ) m E E E HG U với   1 , , n U a a = . Đầu ra: ( ) Tr . Phương pháp: Bước 1. Đặt     =  1 1 : a a E . Bước k + 1 (  k m ). Giả sử   =  1 , , k k k t B B với +  =  1 i k B E , = 1, , k i t và   + =     1 : k k k A A E . Với mỗi i = ( 1, , ) k i t sinh ra tập  1 : i k B a a E +   và ký hiệu là 1 , , i i i r A A . Đặt   + =         1 : ,1 ,1 i i k k l k l k i A A A A i t l r Bước m + 1. Đặt = ( ) m Tr . Thuật toán 2.1 có độ phức tạp thời gian là hàm mũ theo n. Tuy nhiên, trong nhiều trường hợp, độ phức tạp thời gian chỉ là 2 2 ( | ( )| ) n m Tr . Do đó, khi m nhỏ thì thuật toán rất hiệu quả. Trong các vấn đề tổ hợp của nhiều lĩnh vực trong khoa học máy tính có thể tiếp cận được bằng siêu đồ thị thì thuật toán này thường được sử dụng với tính hiệu quả cao. 3 Khóa tối thiểu của toán tử bao đóng Xét TTBĐ  ( ) f Cl U . Một tập con  K U được gọi là khóa củaf nếu = ( ) f K U . Trường hợp nếu với mọi  a K ta có −  ( ) f K a U 1 thìK được gọi là khóa tối thiểu củaf . Ký hiệu ( ) Key f là tập tất cả khóa tối thiểu củaf . 1 Ký hiệu , , − −  X a X Y X a tương ứng lần lượt thay cho     \ , \ ,  X a X Y X a với mọi   , ; X Y U a U .

jos.hueuni.edu.vn Tập 131, Số 2A, 2022 153 Khóa tối thiểu là khái niệm quan trọng và có nhiều ứng dụng của TTBĐ. Bài toán xác định tập ( ) Key f được biết có độ phức tạp thời gian là hàm mũ theo số phần tử củaU [14, 15]. Suy ra, đây là bài toán cực khó trong TTBĐ. Có thể thấy  ( ) ( ) Key f SH U . Do đó, trong mục này, có thể sử dụng siêu đồ thị để mô tả tập ( ) Key f . Đặc biệt, có thể vận dụng Thuật toán 2.1 để sinh ra tất cả khóa tối thiểu của TTBĐ một cách hiệu quả. Xét TTBĐ  ( ) f Cl U và  X U . Đặt = − ( ) ( ) C X U f X và   =  ( ) ( ) : C f C X X U . Mệnh đề sau là rõ ràng Mệnh đề 3.1. (1)   ( ) C f . (2) X là một khóa củaf nếu và chỉ nếu =  ( ) C X . Bây giờ, đặt:   ( ) ( ) : ,( ( ) ) =        Min f Y C f Y Z C f Y Z . Có thể thấy ngay ( ) ( )  Min f SH U và số phần tử của ( ) Min f là khá nhỏ. Cần chứng minh tập ( ) Key f có thể biểu diễn qua siêu đồ thị transversal của họ ( ) Min f . Có thể bắt đầu với các bổ đề sau. Bổ đề 3.1. Với mọi   ( ) Y C f thì − U Y không phải là một khóa củaf . Chứng minh. Xét tập  =  ( ) ( ) Y C X C f . Giả sử − = ( ) f U Y U . Theo định nghĩa của ( ) C X và tính chất của TTBĐ thì = = ( ) ( ( )) f X f f X U hay − = − = = ( ) ( ) U Y U C X f X U . Suy ra =  Y . Mâu thuẫn với giả thiết.  Bổ đề 3.2.   −  ( ) ( ( )) f X U U X Trs Key f . Chứng minh. Giả sử −  ( ( )) U X Trs Key f . Suy ra, tồn tại một khóa tối thiểu  ( ) K Key f sao cho −  =  ( ) U X K . Do đó,  K X hayX là một khóa củaf . Điều này mâu thuẫn với giả thiết.

Nguyễn Hoàng Sơn Tập 131, Số 2A, 2022 154 Ngược lại, giả sửX là một khóa củaf . Suy ra, tồn tại một  ( ) K Key f sao cho  K X . Điều này có nghĩa  − =  ( ) K U X hay −  ( ( )) U X Trs Key f . Mâu thuẫn với giả thiết − U X là một transversal của ( ) Key f .  Lúc này, thu được kết quả sau. Định lý 3.2. Với mọi  ( ) f Cl U , ta có ( ( )) ( ) = Tr Key f Min f . Chứng minh. Giả sửT là một transversal tối thiểu của ( ) Key f . Theo Bổ đề 3.2, −  ( ) f U T U . Lưu ý rằng   T . Rõ ràng, nếu −  − ( ) U T f U T thì với mọi  ( ) K Key f , ta có − −    ( ( )) U f U T K . Điều này mâu thuẫn với giả thiết. Do đó −  ( ) U T Closed f . Khi đó, − = − − = ( ) ( ) C U T U f U T T . Suy ra,  ( ) T C f . Bây giờ, giả sử tồn tại một tập   ( ) S C f sao cho  S T . Theo Bổ đề 3.1, −  ( ) f U S U . Và do đó, theo Bổ đề 3.2,  ( ( )) S Trs Key f . Điều này mâu thuẫn với giả thiết  ( ( )) T Trs Key f . Như vậy, ( )  T Min f . Ngược lại, giả sử ( )  Y Min f . Rõ ràng,   Y . Theo Bổ đề 3.1, −  ( ) f U Y U . Điều này có nghĩa rằng với mọi  ( ) K Key f ,    Y K . Như vậy,  ( ( )) Y Trs Key f . Bây giờ, giả sử tồn tại một  ( ( )) Z Tr Key f sao cho  Z Y . Lập luận tương tự như trên, ta cũng thu được ( )  Z Min f . Điều này mâu thuẫn với tính chất siêu đồ thị đơn của ( ) Min f . Do đó,  ( ( )) Y Tr Key f .  Hệ quả sau thu được ngay từ Định lý 3.2 và Mệnh đề 2.1. Hệ quả 3.1. Với mọi  ( ) f Cl U , ta có ( ) ( ( )) = Key f Tr Min f . Như vậy, tập tất cả khóa tối thiểu của TTBĐf có thể biểu diễn qua siêu đồ thị transversal

của họ ( ). Max f Điều này có nghĩa là có thể dùng mô hình siêu đồ thị để tiếp cận các vấn đề tổ hợp của TTBĐ, đặc biệt là khóa tối thiểu và các tập đóng.

jos.hueuni.edu.vn Tập 131, Số 2A, 2022 155 4 Phản khóa của toán tử bao đóng Xét TTBĐ ( )  f Cl U . Tập con 1−  K U được gọi là phản khóa củaf nếu 1− K thỏa mãn các điều kiện sau: (i) 1 ( ) −  f K U (ii) 1 1 , ( ) − −   −  = a U K f K a U . Ký hiệu ( ) Antikey f là tập tất cả phản khóa củaf . Rõ ràng, các phản khóa chính là các tập lớn nhất không phải khóa. Mối quan hệ giữa các khóa tối thiểu và phản khóa trên TTBĐ là [13] ( ) ( ) = − Key f U Antikey f . Biểu diễn trên cho thấy sự quan trọng của các phản khóa. Có thể xác định các khóa tối thiểu qua các phản khóa. Ngoài ra, các phản khóa có vai trò thiết yếu trong các bài toán tổ hợp extremal của TTBĐ [3, 6]. Tương tự như khóa tối tiểu, bài toán xác định tập ( ) Antikey f có độ phức tạp thời gian là hàm mũ theo số phần tử củaf [14, 15]. Do đó, đây cũng là bài toán cực khó trong TTBĐ. Rõ ràng, ( ) ( )  Antikey f SH U . Do đó, theo định nghĩa của phản khóa và họ ( ) Min f , ta có: ( ) ( ) = Antikey f Min f . Ở đây, ( ) Min f là ký hiệu họ bù của họ ( ) Min f . Từ đây, Mệnh đề 2.1 và Hệ quả 3.1 có thể dẫn tới mối quan hệ sau giữa khóa tối thiểu và phản khóa cuả TTBĐ theo siêu đồ thị. Mệnh đề 4.1. Với mọi  ( ) f Cl U , ta có ( ) ( ( )) = Antikey f Tr Key f . Ví dụ 4.1. Xét các TTBĐ cơ bản sau: (1) Ánh xạ tối đại → : ( ) ( ) m U U xác định bởi = ( ) m X U với mọi  X U . Ta có   =  ( ) C m , ( ) =  Min m và   ( ( )) =  Tr Min m . Vậy,   =  ( ) Key m và ( ) =  Antikey m . (2) Ánh xạ đồng nhất → : ( ) ( ) i U U cho bởi = ( ) i X X với mọi  X U . Ta có  

( ) : ( ) C i U X X U U = −  = ,     ( ) : =  Min i a a U ,   ( ( )) = Tr Min i U . Do đó,   = ( ) Key i U và   ( ) : = −  Antikey i U a a U .

jos.hueuni.edu.vn Tập 131, Số 2A, 2022 157 3. Burosch G., Demetrovics J., Katona G. O. H., Kleitman D. J., Sapozhenko A. A. (1993), On the number of closure operations, Combinatorics. Paul Erdos is Eighty, 91−105. 4. Caspard N., Monjardet B. (2003), The lattices of closure systems, closure operators, and implicational systems on a finite set: a survey, Discrete Applied Mathematics, 127, 241−269. 5. Demetrovics J., Hencsey G., Libkin L., Muchnik I. (1992), On the interaction between closure operations and choice functions with applications to relational databases, Acta Cybernetica, 10, 129−139. 6. Demetrovics J., Katona G. O. H. (1988), Extremal combinatorial problems of database models, MFDBS 87 (Dresden, 1987), 99−127. Lecture Notes in Comput. Sci., 305, Springer, Berlin, 1988. 7. Demetrovics J., Thi V. D. (1999), Describing candidate keys by hypergraphs, Computers and Artificial Intelligence, 18, 191−207. 8. Eiter T., Gottlob G. (1995), Identifying the minimal transversals of a hypergraph and related problems, SIAM Journal on Computing, 24, 1278−1304. 9. Giang N. L., Demetrovics J., Thi V. D., Khoa P. D. (2021), Some properties related to reduct of consistent decision systems. Cybernetics and Information Technologies, 21, 3−9. 10. Mao H., Liu S. (2012), Posets and closure operators relative to matroids, Matematika, 77-85. 11. Nghia V. D. (2004), Relationships between closure operations and choice functions equivalent descriptions of a family of functional dependencies, Acta Cybernetica, 16, 485−506.

12. Rudolph S. (2017), Succinctness and tractability of closure operator representations, Theoretical Computer Science, 658, 327−345. 13. Son N. H., Thi V. D. (2019), Some the combinatorial characteristics of closure operations, Algebra and Discrete Mathematics, 28, 144−156. 14. Son N. H., Khoa T. V. (2021), Bài toán NP-đầy đủ của toán tử bao đóng, Tạp chí Khoa học và Công nghệ: Khoa học tự nhiên, 1−5. 15. Thi V. D. (1986), Minimal keys and antikeys, Acta Cybernetica, 7, 361−371.