• Định nghĩa
• Disjoint đặt liên minh
• Tách rời từng cặp
• Hai tập hợp rỗng có rời rạc không
• Chung và Rời
• Thí dụ
• Câu hỏi thường gặp

Các bộ rời rạc có các ứng dụng chính trong cấu trúc dữ liệu. Trong Toán học, chúng ta sử dụng để tìm mối quan hệ giữa hai tập hợp hoặc hàm. Nếu các phần tử trong hai tập hợp được kết nối với nhau, thì chúng không rời rạc.

Định nghĩa tập hợp rời rạc

Hai tập hợp được cho là rời rạc khi chúng không có phần tử chung . Nếu một tập hợp có hai hoặc nhiều tập hợp, thì điều kiện của sự rời rạc sẽ là giao điểm của toàn bộ tập hợp phải trống.

Tuy nhiên, một nhóm các tập hợp có thể có giao nhau rỗng mà không rời rạc. Hơn nữa, trong khi một nhóm có ít hơn hai tập hợp là rất rời rạc, vì không có cặp nào ở đó để so sánh, giao của một nhóm của một tập hợp bằng với tập hợp đó, có thể khác rỗng. Ví dụ: ba tập hợp {11, 12}, {12, 13} và {11, 13} có giao nhau rỗng nhưng chúng không rời rạc. Không có hai bộ rời rạc có sẵn trong nhóm này. Ngoài ra, họ tập hợp rỗng là rời rạc theo cặp.

Hãy xem xét một ví dụ, {1, 2, 3} và {4, 5, 6} là các tập rời rạc.

Hai tập A và B là các tập rời nhau nếu giao của hai tập hợp là tập hợp rỗng hoặc tập hợp rỗng. Nói cách khác, giao của một tập hợp là trống.

tức là A ∩ B = ϕ

Chú ý: Có một sự khác biệt giữa  giao của hai tập hợp và hiệu của hai tập hợp . Trong trường hợp rời rạc, chỉ có giao lộ sẽ được xem xét.

Thuộc tính của Giao lộ:

• Giao hoán: A ∩ B = B ∩ A
• Liên kết: A ∩ (B ∩ C) = (A ∩ B) ∩ C
• A ∩ ∅ = ∅
• A ∩ B ⊆ A
• A ∩ A = A
• A ⊆ B nếu và chỉ khi A ∩ B = A

Disjoint Set Union

Một liên hiệp tập hợp rời rạc là một phép toán nhị phân trên hai tập hợp. Các phần tử của bất kỳ liên hợp rời rạc nào có thể được mô tả theo các cặp có thứ tự là (x, j), trong đó j là chỉ số đại diện cho nguồn gốc của phần tử x. Với sự trợ giúp của phép toán này, chúng ta có thể nối tất cả các phần tử khác nhau (riêng biệt) của một cặp tập hợp.

Một kết hợp rời rạc có thể chỉ ra một trong hai điều kiện. Thông thường nhất, nó có thể có ý định kết hợp hai hoặc nhiều bộ rời rạc. Nếu không, nếu chúng rời rạc, thì liên hiệp rời rạc của chúng có thể được tạo ra bằng cách điều chỉnh các tập hợp để chúng rời rạc trước khi tạo thành liên hiệp của các tập hợp đã thay đổi. Ví dụ, hai tập hợp có thể được trình bày dưới dạng một tập hợp rời rạc bằng cách hoán đổi từng phần tử bằng một cặp phần tử có thứ tự và một giá trị nhị phân tượng trưng cho dù nó tham chiếu đến tập hợp thứ nhất hay thứ hai. Đối với các nhóm có nhiều hơn hai tập hợp, người ta cũng có thể thay thế từng phần tử bằng một cặp phần tử có thứ tự và danh sách tập hợp chứa phần tử đó.

Liên hợp rời rạc được ký hiệu là XU * Y = (X x {0}) U (Y x {1}) = X * UY *

Giả định rằng,

Sự kết hợp rời rạc của các tập X = (a, b, c, d) và Y = (e, f, g, h) như sau:

X * = {(a, 0), (b, 0), (c, 0), (d, 0)} và Y * = {(e, 1), (f, 1), (g, 1) , (h, 1)}

Sau đó,

XU * Y = X * UY *

Do đó, tập hợp liên hợp rời rạc là {(a, 0), (b, 0), (c, 0), (d, 0), (e, 1), (f, 1), (g, 1), (h, 1)}

Bộ tách rời ghép đôi

Chúng ta có thể tiến hành định nghĩa một tập hợp rời rạc cho bất kỳ nhóm tập hợp nào. Một tập hợp các bộ là rời rạc theo cặp nếu hai bộ bất kỳ trong bộ sưu tập là rời rạc. Nó còn được gọi là các bộ rời rạc lẫn nhau.

Gọi P là tập hợp các tập hợp A và B bất kỳ.

tức là A, B ∈ P. Khi đó, P được gọi là rời rạc từng cặp nếu và chỉ khi A ≠ B. Do đó, A ∩ B = ϕ

Ví dụ:

• P = {{1}, {2, 3}, {4, 5, 6}} là một tập hợp rời rạc từng cặp.
• P = {{1, 2}, {2, 3}} không rời rạc từng cặp, vì chúng ta có 2 là phần tử chung trong hai tập hợp.

Hai tập hợp rỗng có rời rạc không?

Chúng ta biết rằng hai tập hợp là rời rạc nếu chúng không có bất kỳ phần tử chung nào trong tập hợp. Khi chúng ta lấy giao của hai tập hợp rỗng, tập hợp kết quả cũng là một tập hợp rỗng. Người ta có thể dễ dàng chứng minh rằng chỉ có các tập trống là rời rạc với chính nó. Định lý f ollowing chỉ ra rằng một tập hợp rỗng là rời rạc với chính nó.

Định lý:

Tập hợp trống là rời rạc với chính nó.

Ø ⋂ Ø = Ø

Sự khác biệt giữa bộ khớp và bộ rời

Xét hai tập hợp X và Y.

Giả sử rằng cả hai tập X và Y là các tập khác rỗng. Như vậy, X ⋂ Y cũng là một tập khác rỗng, các tập được gọi là tập hợp. Trong trường hợp, nếu X ⋂ Y dẫn đến một tập rỗng thì nó được gọi là tập rời rạc.

Ví dụ: X = {1, 5, 7} và Y = {3, 5, 6}

X ∩ Y = {5}

Do đó, X và Y là các tập hợp.

Ví dụ về bộ rời rạc

Câu 1: Chứng tỏ rằng hai tập hợp đã cho là hai tập hợp rời rạc.

A = {5, 9, 12, 14}

B = {3, 6}

Giải pháp:

Cho: A = {5, 9, 12, 14}, B = {3, 6}

A ∩ B = {5, 9, 12, 14} ∩ {3, 6}

Ở đây, tập hợp A và B không có phần tử chung nào

Đó là, A ∩ B = {}

Giao của tập A và tập B cho một tập rỗng.

Do đó, các tập A và B là các tập rời rạc.

Câu 2: Vẽ biểu đồ Venn tập hợp rời rạc biểu diễn hai tập hợp đã cho

X = {a, b, c, d, f} và Y = {e, g, h, i}

Giải pháp:

Cho: X = {a, b, c, d, f}, Y = {e, g, h, i}

Trong bài toán đã cho, chúng ta không có nhân tử chung.

Do đó, các tập hợp đã cho là rời rạc.

tức là A ∩ B = {}

Biểu đồ Venn tập hợp rời rạc được biểu diễn như sau:

Biểu đồ Venn cho thấy rõ ràng rằng các tập đã cho là các tập rời rạc.