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