Bao đóng trong đồ thì và bài tập áp dụng năm 2024

1 Bao đóng của các quan hệ 1.1 Bao đóng của quan hệ Định nghĩa: Giả sử R là một quan hệ trên tập A. R có thể có một tính chất P nào đó (phản xạ, đối xứng, bác cầu). Nếu S là một quan hệ có tính chất P và chứa R sao cho S là tập con của tất cả các quan hệ có tính chất P và chứa R thì S đựoc gọi là bao đóng của R đối với P.  Bao đóng phản xạ Định nghĩa 1 : Cho quan hệ R trên tập A. Bao đóng phản xạ của R, ký hiệu Rpx là quan hệ nhỏ nhất trên tập A có tính chất phản xạ và chứa R. Ví dụ 1 : Cho quan hệ R= {(1; 1), (1; 2), (2; 1), (3; 2), (3; 4)} trên tập A={1, 2, 3, 4}. Hãy tìm Rpx? Giải: Ta thấy R không có tính phản xạ. Ta xây dựng quan hệ S bằng cách ban đầu gán S=R, sau đó bổ sung thêm (2; 2), (3; 3), (4; 4) vào S. Tức là ta được tập S={(1; 1), (1; 2), (2; 1), (3; 2), (3; 4), (2; 2), (3; 3), (4; 4)}. Rõ ràng S có tính chất phản xạ. Và mọi tập có tính chất phản xạ chứa R thì đương nhiên phải chưa S. Do vậy S chính là bao đóng phản xạ của R. Vậy bao đóng phản xạ được tạo ra bằng cách: Rpx = R  {(a; a) | a A, (a; a)  R}.

Ví dụ 2 : Xác định bao đóng của R= {(a; b) | a > b} trên tập số nguyên Giải: Bao đóng phản xạ của Rpx = R {(a; a) | a Z} = {(a; b) | a b}

Lưu ý: nếu R đã có tính chất phản xạ, thì Rpx  R.

Ví dụ 3: Cho quan hệ R= {(1; 3), (2; 2), (2; 1), (3; 2)} trên tập A={1, 2, 3}. Hãy tìm Rpx? Giải:

• R chưa có tính chất phản xạ vì thiếu các cặp (1, 1), (3, 3).
• Vậy cần bổ xung thêm ∆px= {(1, 1), (3, 3)} vào R ban đầu để được Rpx.
• Khi đó Rpx= {(1; 3 ), ( 2 ; 2), (2; 1), (3; 2), (1, 1), (3, 3)} sẽ có tính chất phản xạ. Ví dụ 4: Cho quan hệ R= {(1; 1), (2; 2), (2; 1), (3; 2), (3, 3)} trên tập A={1, 2, 3}. Hãy tìm Rpx? Giải:
• R có chứa đủ các cặp dạng (a, a) với Ɐa ЄA. Vậy nên Rpx  R. Hay bao đóng phản xạ của R là chính nó.
• Rpx= {(1; 1 ), ( 2 ; 2), (2; 1), (3; 2), (3, 3)}  Bao đóng đối xứng Định nghĩa:

Rđx = R   1 R = {(1; 4 ), ( 2 ; 1 ), (2; 2), ( 1 ; 3), (3; 1), ( 4 ; 2), (2, 4), (4, 1), (1, 2)}. Ví dụ 3: Quan hệ R= {(3; 4), (3; 3), (1; 3), (3; 1), (4; 2), (2, 4), (4, 3)} trên tập A={1, 2, 3, 4}. Hãy tìm Rđx? Giải:

• Quan hệ R đã có tính chất đối xứng.
• Bao đóng đối xứng của Rđx  R là chính nó.  Bao đóng bắc cầu Định nghĩa: Cho quan hệ R trên tập A. Bao đóng bắc cầu của R, ký hiệu Rbc là quan hệ nhỏ nhất trên tập A có tính chất bắc cầu và chứa R. Ví dụ 3: Cho quan hệ R = {(1; 3), (1; 4), (2; 1), (3; 2) } trên tập A = {1, 2, 3, 4}. Tìm bao đóng bắc cầu Rbc của quan hệ R?
• Ta xây dựng tập S như sau: S = R;
• Vì (1; 3)  R và (3; 2)  R, nhưng (1; 2)  R, nên ta bổ sung (1; 2) vào S.
• Vì (3; 2)  R và (2; 1)  R nhưng (3; 1)  R,, nên ta bổ sung (3; 1) vào S.
• Vì (2; 1)  R và (1; 4)  R nhưng (2; 4)  R,, nên ta bổ sung (2; 4) vào S. Việc thêm các cặp này vào S, vẫn chưa tạo quan hệ S có tính chất bắc cầu vì khi đó quan hệ S có chứa cặp (3; 1), (1; 4) nhưng lại không chứa cặp (3; 4).

Vậy tìm bao đóng bắc cầu là phức tạp. Bao đóng bắc cầu có thể tìm được bằng cách thêm các cặp được sắp mới cần phải có mặt sau đó lặp lại quá trình này cho tới khi không cần phải thêm nữa. Việc biểu diễn quan hệ bằng đồ thị có hướng giúp ta xây dựng bao đóng bắc cầu. 1.1 Đường đi trong đồ thị có hướng và thuật toán Warshall Định nghĩa: Đường đi từ a đến b trong đồ thị có hướng G là dãy cạnh ( x 0 ; x 1 ), (x 1 ; x 2 )...(xn- 1 ; xn) với x 0 = a đỉnh xuất phát, xn = b đỉnh kết thúc. Ký hiệu {x 0 , x 1 , x 2 ..} là một đường đi từ x 0 đến xn, có chiều dài n. Nếu đỉnh kết thúc trùng với đỉnh xuất phát thì đường đi gọi là chu trình. Định lý 1: Cho R là một quan hệ trên tập A, có một đường đi chiều dài n từ a đến b nếu và chỉ nếu (a; b)  Rn.

• Bao đóng bắc cầu : Việc tìm bao đóng bắc cầu của một quan hệ tương đương với việc xác định cặp đỉnh nào đó trong đồ thị có hướng biểu diễn quan hệ đó được nối bằng một đường đi Định nghĩa: Cho R là một quan hệ trên tập A. Quan hệ liên thông R* gồm các cặp (a, b) sao cho có một đường đi giữa a và b trong R Vì Rn gồm các cặp (a; b) sao cho có một đường đi có chiều dài n từ a đến b suy ra R* là hợp của tất cả các tập Rn

R*=

 n 1 Rn Ví dụ:

 Tìm bao đóng bắc cầu dựa vào việc xây dựng đường đi trong đồ thi có hướng.  Biểu diễn quan hệ bằng đồ thị có hướng.  Lấy Rbc =R  Tìm tất cả các đường đi từ mỗi đỉnh đến tất cả các đỉnh của đồ thị, nếu có thì bổ sung vào Rbc  Kiểm tra xem quan hệ R đã có tính chất bắc cầu chưa?  Nếu thỏa mãn thì kết luận bao đóng bắc cầu R*bc= R là chính R.  Ngược lại ta bổ xung thêm các cặp dạng (a,c) với (a,b), (b,c) thuộc R. Ví dụ 2: Ví dụ: Cho tập A= {1, 2, 3, 4} Và quan hệ R={(1, 2), (2, 3), (1, 4), (3, 4), (4, 2)} Hướng dẫn: Biểu diễn quan hệ R dưới dạng đồ thị có hướng. Hình 1: Đồ thị biểu diễn quan hệ R R chưa có tính chất bắc cầu, nên cần bổ xung thêm các cặp dạng (a,c) với (a,b), (b,c) thuộc R.

Hình 2: Đồ thi biểu diễn bao đóng bắc cầu của quan hệ R. R*bc= R{(2, 2), (3, 3), (4, 4), (2, 4), (4, 3), (3, 2), (1, 3)}. Vậy bao đóng bắc cầu được biểu diễn như đồ thị trên (hình 2)  Thuật toán Warshall tìm R * bc của quan hệ R (Tìm bao đóng bắc cầu của R bằng tích Bool) Hướng dẫn:

• Biểu diễn quan hệ bằng ma trận Bool MR.
• Xác định n. (n = số phần tử của tâp hợp).
• Tính tích bool: MR 1 , MR 2 , ....... M R * MR 1 MR 2 .. Rn Ví dụ: tìm bao đóng bắc cầu bằng tích Bool. Cho quan hệ R={ (1, 3), (1, 4), (2, 1), (3, 2) } trên tập A= {1, 2, 3, 4} Giải: Vì n= 4. Nên ta tính đến MR 4

For i:=2 to n begin A:=A  MR; B:= B A; end; end; { B là ma trận Rêzo- một biểu diễn R* } Thuật toán Warshall Cho Wk = [  k wij ] là ma trận Rêzo- một có phần tử ở vị trí (i, j) nhận giá trị 1 nếu và chỉ nếu có một đường đi từ vi đến vj với các đỉnh trong thuộc tập hợp { v 1 , v 2 ... vk } thì  k wij =  k 1  wij (  k 1  wik   k 1  wkj ) với mọi i, j, k là các số nguyên dương không vượt quá n. Đỉnh trong là đỉnh nằm ở đâu đó trên đường đi khác đỉnh xuất phát và đỉnh kết thúc. Procedure Warshall ( MR : ma trận Rêzo- một n x n ) begin W= MR For k:=1 to n begin For i:=1 to n Begin For j:=1 to n wi j =wij (wik wk j ) end; end; end;{ W= [wi j ] là MR* }