분리 집합

두 개의 분리된 집합

수학에서, 두 집합은 공통적인 요소가 없으면 분리된 집합이라고 한다.마찬가지로 두 개의 분리된 집합은 교차가 빈 ^[1]집합인 집합입니다.예를 들어 {1, 2, 3}과(와) {4, 5, 6}은(는) 분리된 집합이지만 {1, 2, 3}과(와) {3, 4, 5}은(는) 분리된 집합이 아닙니다.두 개 이상의 집합 집합이 서로 다른 두 집합 중 하나가 분리되면 분리 집합이라고 합니다.

일반화

집합의 분리된 집합

분리 집합의 정의는 집합 패밀리 $\left(A_{i}\right)_{i\in I}$ i ) $\left(A_{i}\right)_{i\in I}$ I $\left(A_{i}\right)_{i\in I}$ { $displaystyle \left(A_{i}\right)_{i\in$ I $\left(A_{i}\right)_{i\in I}$ 로 확장할 수 있습니다. 패밀리는 쌍으로 분리되거나 $A_{i}\cap A_{j}=\varnothing$ $A_{i}\cap A_{j}=\varnothing$ $A_{i}\cap A_{j}=\varnothing$ j $A_{i}\cap A_{j}=\varnothing$ ${\$ { $displaystyle A_{i}\cap A_jvar$ nothing $A_{i}\cap A_{j}=\varnothing$ $=$ $i\neq j$ ors는 이 개념을 나타낼 때도 disconnect라는 용어를 사용합니다.

패밀리의 경우 반복되는 동일한 멤버를 허용하기 위해 때로는 쌍별 분리 또는 상호 분리 개념이 미묘하게 다른 방식으로 정의되기도 한다. A i $A_{i}\neq A_{j}$ $A_{i}\cap A_{j}=\varnothing$ $A_{i}\cap A_{j}=\varnothing$ $A_{i}\neq A_{j}$ { $displaystyle A_{i$ $}$ \ $cap A_$ {j} = \ $varnothing$ $}$ 인 $A_{i}\cap A_{j}=\varnothing$ 경우 패밀리는 $A_{i}\neq A_{j}$ 쌍별 $분리$ 된다.패밀리의 개별 집합이 ^[2]분리된다.)예를 들어 {0, 1, 2}, {3, 4, 5}, {6, 7, 8}의 집합이 있습니다. }은(는) 2개의 정수의 패리티 클래스 중 세트 {..., -2, 0, 2, 4, ...}, {..., -3, -1, 1, 3, 5}과 같이 분리됩니다. $(\{n+2k\mid k\in \mathbb {Z} \})_{n\in \{0,1,\ldots ,9\}}$ + 2k $(\{n+2k\mid k\in \mathbb {Z} \})_{n\in \{0,1,\ldots ,9\}}$ k $(\{n+2k\mid k\in \mathbb {Z} \})_{n\in \{0,1,\ldots ,9\}}$ $(\{n+2k\mid k\in \mathbb {Z} \})_{n\in \{0,1,\ldots ,9\}}$ }) n $(\{n+2k\mid k\in \mathbb {Z} \})_{n\in \{0,1,\ldots ,9\}}$ , 1, $(\{n+2k\mid k\in \mathbb {Z} \})_{n\in \{0,1,\ldots ,9\}}$ …, $}$ \style $(\{n+2k$ } \ $mathbbbbb\in\$ mid kbbbb\in\in\in\in\md\in\md\md\md\md\m $)$ h는 5회 존재하지만 이 정의에 따라 쌍으로 분리됩니다(두 멤버가 같은 클래스일 경우에만 두 멤버의 빈 교집합을 얻을 수 있기 때문입니다).

어떤 의미에서 교차가 작으면 두 집합은 거의 분리된 집합이라고 한다.예를 들어, 교차가 유한 집합인 두 개의 무한 집합은 거의 ^[3]불연속이라고 할 수 있다.

토폴로지에서는 분리보다 엄격한 조건을 가진 분리 집합의 다양한 개념이 있습니다.예를 들어, 두 세트가 분리된 폐쇄 또는 분리된 인접 관계를 가진 경우 분리된 것으로 간주할 수 있다.마찬가지로 메트릭 공간에서는 확실히 분리된 집합은 ^[4]0이 아닌 거리로 구분된 집합입니다.

교차로

두 세트의 불연속성 또는 집합군의 불연속성은 쌍의 교차점으로 표현될 수 있다.

2개의 세트 $A와 B$ 는 각각의 $A\cap B$ $A\cap B$ A가 $A\cap B$ 빈 ^[1]세트일 $경우$ 에만 분리됩니다 $.$ 이 정의에 따라 모든 집합은 빈 집합에서 분리되며 빈 집합은 그 ^[5]자체에서 분리되는 유일한 집합입니다.

컬렉션에 두 개 이상의 집합이 포함되어 있는 경우 컬렉션이 분리된 조건은 전체 컬렉션의 교차가 비어 있음을 의미합니다.그러나 집합 집합은 분리되지 않고 빈 교차로를 가질 수 있습니다.또한 비교할 쌍이 없기 때문에 두 집합 미만의 집합이 3차적으로 분리되어 있는 반면, 한 집합의 집합의 교차는 해당 집합과 같으며,^[2] 이는 비어 있지 않을 수 있다.예를 들어 세 집합 {1,2}, {2,3}, {1,3} }은(는) 교차가 비어 있지만 연결이 끊어지지 않았습니다.실제로 이 컬렉션에는 두 개의 분리된 집합이 없습니다.또한 빈 집합 패밀리는 쌍으로 분리됩니다.^[6]

Helly 패밀리는 빈 교차를 가진 유일한 하위 패밀리가 쌍으로 분리된 패밀리의 집합 시스템입니다.예를 들어, 실수의 닫힌 간격은 Helly 패밀리를 형성한다. 닫힌 간격의 패밀리가 빈 교차로를 가지며 최소인 경우(즉, 패밀리의 하위 패밀리가 빈 교차로를 가지지 않음), 쌍으로 분리되어야 한다.^[7]

유니언 및 파티션 분리

집합 X의 파티션은 결합이 ^[8]X인 서로 분리된 비어 있지 않은 집합의 집합입니다.모든 파티션은 동등하게 두 요소가 파티션의 동일한 집합에 ^[8]속하는지 여부를 설명하는 이진 관계인 등가 관계로 설명할 수 있습니다.분리 집합 데이터 구조와^[9] 파티션^[10] 미세화는 컴퓨터 과학에서 2개의 집합을 병합하는 결합 연산 또는 1개의 집합을 2개로 분할하는 정제 연산 각각 대상 집합의 파티션을 효율적으로 유지하기 위한 두 가지 기술입니다.

분열 조합은 두 가지 중 하나를 의미할 수 있다.가장 간단히 말하면,^[11] 분리된 집합의 결합을 의미할 수 있습니다.단, 둘 이상의 세트가 아직 분리되지 않은 경우에는 변경된 ^[12]세트의 결합을 형성하기 전에 분리되도록 세트를 수정하여 분리 결합을 형성할 수 있다.예를 들어 각 요소를 요소의 순서쌍과 그것이 제1세트에 ^[13]속하는지 제2세트에 속하는지 여부를 나타내는 2진수치에 의해 치환함으로써 2세트를 분리할 수 있다.집합이 3개 이상인 경우 마찬가지로 각 요소를 요소의 순서 쌍과 해당 ^[14]요소를 포함하는 집합의 색인으로 대체할 수 있습니다.

「」를 참조해 주세요.

분리 볼록 집합의 초평면 분리 정리
상호 배타적 이벤트
비교적 소수이며, 소수 집합의 서로 다른 집합이 있는 수
세퍼로이드
세트 패킹, 세트 패밀리에서 가장 큰 분리 하위 패밀리를 찾는 문제

레퍼런스

^ ^a ^b 를 클릭합니다Halmos, P. R. (1960), Naive Set Theory, Undergraduate Texts in Mathematics, Springer, p. 15, ISBN 9780387900926.
^ ^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.
^ 를 클릭합니다Halbeisen, Lorenz J. (2011), Combinatorial Set Theory: With a Gentle Introduction to Forcing, Springer monographs in mathematics, Springer, p. 184, ISBN 9781447121732.
^ 를 클릭합니다Copson, Edward Thomas (1988), Metric Spaces, Cambridge Tracts in Mathematics, vol. 57, Cambridge University Press, p. 62, ISBN 9780521357326.
^ 를 클릭합니다Oberste-Vorth, Ralph W.; Mouzakitis, Aristides; Lawrence, Bonita A. (2012), Bridge to Abstract Mathematics, MAA textbooks, Mathematical Association of America, p. 59, ISBN 9780883857793.
^ "쌍으로 구성된 빈 집합 패밀리는 분리되었는가?"라는 질문에 대한 답변을 참조하십시오.″
^ 를 클릭합니다Bollobás, Béla (1986), Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability, Cambridge University Press, p. 82, ISBN 9780521337038.
^ ^a ^b Halmos(1960), 페이지 28
^ 를 클릭합니다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.
^ 를 클릭합니다Paige, Robert; Tarjan, Robert E. (1987), "Three partition refinement algorithms", SIAM Journal on Computing, 16 (6): 973–989, doi:10.1137/0216062, MR 0917035, S2CID 33265037.
^ 를 클릭합니다Ferland, Kevin (2008), Discrete Mathematics: An Introduction to Proofs and Combinatorics, Cengage Learning, p. 45, ISBN 9780618415380.
^ 를 클릭합니다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.
^ 를 클릭합니다Monin, Jean François; Hinchey, Michael Gerard (2003), Understanding Formal Methods, Springer, p. 21, ISBN 9781852332471.
^ 를 클릭합니다Lee, John M. (2010), Introduction to Topological Manifolds, Graduate Texts in Mathematics, vol. 202 (2nd ed.), Springer, p. 64, ISBN 9781441979407.

외부 링크

Weisstein, Eric W. "Disjoint Sets". MathWorld.

[halmos-1] 를 클릭합니다Halmos, P. R. (1960), Naive Set Theory, Undergraduate Texts in Mathematics, Springer, p. 15, ISBN 9780387900926.

[douglas-2] 를 클릭합니다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] "쌍으로 구성된 빈 집합 패밀리는 분리되었는가?"라는 질문에 대한 답변을 참조하십시오.″

[7] 를 클릭합니다Bollobás, Béla (1986), Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability, Cambridge University Press, p. 82, ISBN 9780521337038.

[h60-28-8] Halmos(1960), 페이지 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, S2CID 33265037.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Search

분리 집합

네임스페이스

더

목차

일반화

교차로

유니언 및 파티션 분리

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

분리 집합

일반화

교차로

유니언 및 파티션 분리

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.