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

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.