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

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 .