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