Jump to content

Disjoint sets

This is a fully translated article. Click here for more information.
From DawoumWiki, the free Mathematics self-learning
Original article: w:Disjoint sets
This article is about the mathematical concept. For the data structure, see Disjoint-set data structure.
Two disjoint sets.

수학(mathematics)에서, 두 집합(sets)은 만약 그들이 공통에서 원소(element)를 가지지 않으면 서로소 집합(disjoint sets)이라고 말합니다. 동등하게, 두 서로소 집합은 그의 교집합(intersection)이 빈 집합(empty set)인 집합입니다.[1] 예를 들어, {1, 2, 3} 및 {4, 5, 6}은 서로소 집합이지만, {1, 2, 3} 및 {3, 4, 5}는 서로소가 아닙니다. 두 집합보다 많은 모음이 만약 모음의 임의의 두 서로소 집합은 서로소이면 서로소라고 불립니다.

Generalizations

A disjoint collection of sets

서로소 집합의 이 정의는 집합의 가족(family of sets) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle (A_i)_{i\in I}} 으로 확장될 수 있습니다: 그 가족은 만약 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle i\neq j} 일 때마다 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle A_i\cap A_j=\varnothing} 이면 서로소입니다. 가족에 대해 쌍별 서로소(pairwise disjoint) 또는 서로 서로소(mutually disjoint)의 개념은 미묘하게 다른 방식에서 때때로 정의되며, 그것에서 반복된 동일한 구성원은 허용됩니다: 그 가족은 만약 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle A_i\neq A_j} 일 때마다 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle A_i\cap A_j=\varnothing} 이면 쌍별 서로소입니다 (그 가족에서 모든 각 두 서로소 집합은 서로소입니다).[2] 예를 들어, 집합 { {0,1,2}, {3,4,5}, {6,7,8}, ... }의 모음은, 정수의 두 패리티 클래스의 집합 { {...,-2,0,2,4,...}, {...,-3,-1,1,3,5 }}에서 처럼, 서로소입니다; 10 구성원을 가진 가족 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle (\{\,n+2k\mid k\in\mathbb Z\,\})_{n\in\{0,1,\ldots,9\}}} 은 서로소이지만 (왜냐하면 짝수와 홀수의 클래스는 각각 다섯 번 존재하기 때문입니다), 그것은 이 정의에 따라 쌍별 서로소입니다 (왜냐하면 우리는 두 구성원이 같은 클래스일 때 두 구성원의 비-빈 교집합을 오직 얻기 때문입니다).

두 집합은 만약 그들의 교집합이 어떤 의미에서 작으면 거의 서로소 집합(almost disjoint sets)이라고 말합니다. 예를 들어, 그들의 교집합이 유한 집합(finite set)인 두 무한 집합(infinite set)은 거의 서로소라고 말할 수 있습니다.[3]

토폴로지(topology)에서, 서로소성보다 더 엄격한 조건을 가진 분리된 집합(separated sets)의 다양한 개념이 있습니다. 예를 들어, 두 집합이 그들이 서로소 닫힘(closure) 또는 서로소 이웃(neighborhoods)을 가질 때 분리된 것으로 여길 수 있습니다. 비슷하게, 메트릭 공간(metric space)에서, 양으로 분리된 집합(positively separated sets)은 비-영 거리(distance)에 의해 분리된 집합입니다.[4]

Intersections

두 집합, 또는 집합의 가족의 서로소성은 그들의 쌍의 교집합(intersections)의 관점에서 표현될 수 있습니다.

두 집합 A와 B가 서로소인 것과 그들의 교집합 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:7231/localhost/v1/":): {\displaystyle A\cap B} 가 빈 집합(empty set)인 것은 필요충분 조건입니다.[1] 모든 각 집합은 빈 집합과 서로소이고, 빈 집합은 자체로부터 서로소인 유일한 집합인 이 정의로부터 따릅니다.[5]

만약 모음이 적어도 두 집합을 포함하면, 모음이 서로소라는 조건은 전체 모음의 교집합이 빈 것임을 의미합니다. 어쨌든, 집합의 모음은 서로소인 것없이 빈 교집합을 가질 수 있습니다. 추가적으로, 두 집합보다 작은 모음은 자명하게 서로소이지만, 비교할 쌍이 없기 때문에, 한 집합의 모음의 교집합은 해당 집합과 같으며, 이것은 비-빈일 수 있습니다.[2] 예를 들어, 세 세트 { {1, 2}, {2, 3}, {1, 3} }은 빈 교집합을 가지지만 서로소이지 않습니다. 실제로, 이 모음에서 두 서로소 집합이 없습니다. 역시 집합의 빈 가족은 쌍 서로소입니다.[6]

헬리 가족(Helly family)은 빈 교집합을 갖는 오직 부분-가족이 쌍별 서로소인 것들 이내에서 집합의 시스템입니다. 예를 들어, 실수(real number)의 닫힌 구간(closed interval)은 헬리 패밀리를 형성합니다: 만약 닫힌 구간의 가족이 빈 교집합을 가지고 최소이면 (즉, 가족의 부분-가족이 빈 교집합을 가지지 않으면), 그것은 쌍별 서로소이어야 합니다. [7]

Disjoint unions and partitions

집합 X의 분할(partition of a set)은 그의 합집합(union)이 X인 서로 서로소 비-빈 집합의 임의의 모음입니다.[8] 모든 각 분할은 동치 관계(equivalence relation), 두 원소가 분할에서 같은 집합에 속하는지 여부를 설명하는 이항 관계(binary relation)에 의해 동등하게 설명될 수 있습니다.[8] 서로소-집합 데이터 구조(Disjoint-set data structure)[9]와 분할 세분화(partition refinement)[10]는, 각각, 두 집합을 병합하는 합집합 연산 또는 하나의 집합을 둘로 나누는 세분화 연산에 따라 집합의 분할을 효율적으로 유지하는 것에 대해 컴퓨터 과학에서 두 가지 기술입니다.

서로소 합집합(disjoint union)은 두 가지 중 하나를 의미할 수 있습니다. 가장 간단하게, 그것은 서로소인 집합의 합집합을 의미할 수 있습니다.[11] 그러나 만약 둘 이상의 집합이 이미 서로소가 아니면, 그들의 서로소 합집합은 수정된 집합의 합집합을 형성하기 전에 그들을 서로소로 만들기 위해 집합을 수정함으로써 형성될 수 있습니다.[12] 예를 들어, 두 집합은 각 원소를 원소의 순서화된 쌍과 그것이 첫 번째 또는 두 번째 집합에 속하는지 여부를 나타내는 이진 값으로 대체함으로써 서로소로 만들어질 수 있습니다.[13] 두 집합보다 많은 것의 가족에 대해, 우리는 각 원소를 원소의 순서화된 쌍과 그것을 포함하는 집합의 인덱스를 비슷하게 대체할 수 있습니다.[14]

See also

References

  1. ^ a b Halmos, P. R. (1960), Naive Set Theory, Undergraduate Texts in Mathematics, Springer, p. 15, ISBN 9780387900926.
  2. ^ a b Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2010), A Transition to Advanced Mathematics, Cengage Learning, p. 95, ISBN 978-0-495-56202-3.
  3. ^ Halbeisen, Lorenz J. (2011), Combinatorial Set Theory: With a Gentle Introduction to Forcing, Springer monographs in mathematics, Springer, p. 184, ISBN 9781447121732.
  4. ^ Copson, Edward Thomas (1988), Metric Spaces, Cambridge Tracts in Mathematics, vol. 57, Cambridge University Press, p. 62, ISBN 9780521357326.
  5. ^ Oberste-Vorth, Ralph W.; Mouzakitis, Aristides; Lawrence, Bonita A. (2012), Bridge to Abstract Mathematics, MAA textbooks, Mathematical Association of America, p. 59, ISBN 9780883857793.
  6. ^ See answers to the question ″Is the empty family of sets pairwise disjoint?″
  7. ^ Bollobás, Béla (1986), Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability, Cambridge University Press, p. 82, ISBN 9780521337038.
  8. ^ a b Halmos (1960), p. 28.
  9. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Chapter 21: Data structures for Disjoint Sets", Introduction to Algorithms (Second ed.), MIT Press, pp. 498–524, ISBN 0-262-03293-7.
  10. ^ Paige, Robert; Tarjan, Robert E. (1987), "Three partition refinement algorithms", SIAM Journal on Computing, 16 (6): 973–989, doi:10.1137/0216062, MR 0917035.
  11. ^ Ferland, Kevin (2008), Discrete Mathematics: An Introduction to Proofs and Combinatorics, Cengage Learning, p. 45, ISBN 9780618415380.
  12. ^ Arbib, Michael A.; Kfoury, A. J.; Moll, Robert N. (1981), A Basis for Theoretical Computer Science, The AKM series in Theoretical Computer Science: Texts and monographs in computer science, Springer-Verlag, p. 9, ISBN 9783540905738.
  13. ^ Monin, Jean François; Hinchey, Michael Gerard (2003), Understanding Formal Methods, Springer, p. 21, ISBN 9781852332471.
  14. ^ Lee, John M. (2010), Introduction to Topological Manifolds, Graduate Texts in Mathematics, vol. 202 (2nd ed.), Springer, p. 64, ISBN 9781441979407.

External links

Retrieved from "https://dawoum.duckdns.org/w/index.php?title=Disjoint_sets&oldid=83189"