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 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.