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

jos.hueuni.edu.vn Tập 131, Số 2A, 2022 151 (ii)        ( ), U . Rõ ràng ( ) Closed f là một nửa dàn giao. Có thể thấy [5] nếu là một nửa dàn giao thì ánh xạf xác định theo   =   ( ) : f X Y X Y là một TTBĐ. Ngược lại, nếu  ( ) f Cl U thì tồn tại duy nhất một nửa dàn giao trênU sao cho = f f , với   =  = : ( ) X U f X X . Một họ   =  = : ( ), 1,2, , i i E E U i m được gọi là siêu đồ thị trênU nếu   i E với mọi i. Khi đó, mỗi phần tử  a U được gọi là một đỉnh và mỗi tập i E được gọi là một siêu cạnh hay cạnh của . Lưu ý rằng một số tác giả, chẳng hạn [1], yêu cầu tập các siêu cạnh cũng như mỗi siêu cạnh phải khác rỗng và hợp tất cả các siêu cạnh phải bằng tập đỉnh. Trong bài báo này, chúng tôi không yêu cầu như vậy. Ký hiệu ( ) HG U là tập tất cả siêu đồ thị trênU . Một siêu đồ thị được gọi là đơn nếu với mọi    = , , i j i j i j E E E E E E . Tập tất cả siêu đồ thị đơn trênU được ký hiệu là ( ) SG U . Một tập  T U được gọi là một transversal của  ( ) HG U nếu với mọi  E ta có    T E . Ký hiệu ( ) Trs là tập tất cả các transversal của . Một transversal  ( ) T Trs được gọi là tối thiểu nếu không tồn tại một tập con thật sự ' T củaT sao cho  ) ' ( Trs T . Tập tất cả các transversal tối tiểu của còn được gọi siêu đồ thị transversal của , và ký hiệu là ( ) Tr . Như vậy, có thể thấy  ( ) ( ) Tr SH U . Siêu đồ thị transversal có các tính chất cơ bản sau đây. Mệnh đề 2.1. [1] Cho  1 2 , ( ) SH U . Ta có (1) =  = 1 2 2 1 ( ) ( ) Tr Tr . (2) =  = 1 2 1 2 ( ) ( ) Tr Tr . (3) = 1 1 ( ( )) Tr Tr .