분리합집합

3. 성질

임의의 집합 $A\_i$는 $\backslash bigsqcup\_\{i\backslash in\; I\}A\_i$로 매장된다. 이는 다음과 같은 함수로 표현된다.

:$\backslash iota\backslash colon\; A\_i\backslash hookrightarrow\backslash bigsqcup\_\{i\backslash in\; I\}A\_i$

:$\backslash iota\backslash colon\; a\backslash mapsto(a,i)$

각 집합 $A\_i$는 다음 집합과 표준적으로 동형이다.

:$A\_i^*\; =\; \backslash left\backslash \{(x,i)\; :\; x\; \backslash in\; A\_i\backslash right\backslash \}$

이 동형 사상을 통해, $A\_i$가 분리합집합에 표준적으로 포함되어 있다고 간주할 수 있다. $i\; \backslash neq\; j$이면, 집합 $A\_i^*$와 $A\_j^*$는 $A\_i$와 $A\_j$가 서로소 집합이 아니더라도 서로소이다.

집합족 $A\_i$가 서로소이면, 즉 $i\; \backslash ne\; j$이면 $A\_i\; \backslash cap\; A\_j\; =\; \backslash empty$를 만족할 때, 자연스러운 동형 $\backslash bigsqcup\_i\; A\_i\; \backslash to\; \backslash bigcup\_i\; A\_i$가 존재한다.

3. 1. 집합의 크기(cardinality)

3. 2. 범주론적 성질

4. 예시

두 집합 $A=\backslash \{a,b\backslash \}$, $B=\backslash \{b,c,d\backslash \}$의 분리 합집합은 $A\backslash sqcup\; B=\backslash \{(a,0),(b,0),(b,1),(c,1),(d,1)\backslash \}$이며, 그 크기는 5이다.

집합 $A\_0\; =\; \backslash \{5,\; 6,\; 7\backslash \}$과 $A\_1\; =\; \backslash \{5,\; 6\backslash \}$을 생각해 보자. 집합 요소들을 집합의 기원에 따라 색인할 수 있으며, 관련 집합을 다음과 같이 형성할 수 있다.

:$$

\begin{align}

A^*_0 & = \{(5, 0), (6, 0), (7, 0)\} \\

A^*_1 & = \{(5, 1), (6, 1)\}, \\

\end{align}



여기서 각 쌍의 두 번째 요소는 기원 집합의 아래 첨자와 일치한다 (예를 들어, $(5,\; 0)$의 $0$은 $A\_0$의 아래 첨자와 일치한다). 그 다음 분리 합집합 $A\_0\; \backslash sqcup\; A\_1$은 다음과 같이 계산할 수 있다.

:$A\_0\; \backslash sqcup\; A\_1\; =\; A^*\_0\; \backslash cup\; A^*\_1\; =\; \backslash \{(5,\; 0),\; (6,\; 0),\; (7,\; 0),\; (5,\; 1),\; (6,\; 1)\backslash \}.$

집합 $A\_0\; =\; \backslash \{1,\; 2,\; 3\backslash \}$ 와 $A\_1\; =\; \backslash \{1,\; 2\backslash \}$ 의 분리합집합 $A\_0\; \backslash sqcup\; A\_1$ 또는 $A\_0\; \backslash cup^*\; A\_1$^[3]는

:$$

\begin{align}

A^*_0 & = \{(1, 0), (2, 0), (3, 0)\} \\

A^*_1 & = \{(1, 1), (2, 1)\}

\end{align}



를 사용하여

:$$

A_0 \sqcup A_1 = A_0 \cup^* A_1 := A^*_0 \cup A^*_1 = \{(1, 0), (2, 0), (3, 0), (1, 1), (2, 1)\}



와 같이 계산된다.

5. 표기법

분리 합집합은 여러 가지 기호로 표현된다. 예를 들어, 집합족 $\backslash left(A\_i\; :\; i\; \backslash in\; I\backslash right)$의 분리합집합은 $\backslash bigsqcup\_\{i\backslash in\; I\}A\_i$ 또는 $\backslash sum\_\{i\backslash in\; I\}A\_i$로 나타낼 수 있다. 두 집합 A와 B의 분리합집합은 $A+B$로 표기하기도 한다. 이러한 표기법은 분리합집합의 기수가 각 집합의 기수의 합과 같다는 사실을 보여준다.

범주론에서는 분리합집합을 집합 범주에서의 코곱으로 정의하며, 이때 쌍대곱을 나타내는 기호인 $\backslash coprod$를 사용하기도 한다.^[1] 이는 분리합집합이 데카르트 곱의 범주론적 쌍대임을 의미한다.

6. 응용

분리합집합은 주어진 원소들을 겹치지 않는 부분 집합으로 나누는 자료구조로, 다음과 같은 다양한 분야에서 응용된다.

• 최소 신장 트리 (Minimum Spanning Tree) 알고리즘: 크루스칼 알고리즘은 분리합집합을 이용하여 그래프에서 최소 신장 트리를 찾는 데 사용된다. 간선들을 가중치 순으로 정렬한 후, 분리합집합을 이용하여 사이클을 형성하지 않는 간선들을 추가하는 방식으로 동작한다.
• 그래프 연결성 판별: 분리합집합을 이용하여 그래프 내의 두 노드가 연결되어 있는지 여부를 효율적으로 판별할 수 있다. 두 노드에 대해 `find` 연산을 수행하여 같은 집합에 속하는지 확인하면 된다.
• 이미지 처리: 이미지 분할(image segmentation) 알고리즘에서 픽셀들을 묶어 영역을 구분하는 데 사용될 수 있다.
• 네트워크 분석: 소셜 네트워크 등에서 서로 연결된 그룹을 찾거나, 네트워크의 연결성을 분석하는 데 활용될 수 있다.

참조

_[1] 문서 ProofWiki
_[2] 문서 nlab
_[3] 문서 MathWorld