서로소(Pairwise Disjoint Set) 와 파티션(Partition)
서로소(pairwise disjoint set)은 두 집합이 공유하는 요소가 없는 집합의 모음이다 (예를 들어, 그들의 교집합이 공집합인 경우). 가령, 다음의 집합의 모음들은 서로소들이다:{ }, {1, 2, 5}, {3, 6}, {4, 9} 여기에 서로소가 아닌 집합 모음이 있다:{2, 6, 7}, {6, 7, 9}, {3} 이 집합들은 서로소가 아닌데, 첫째와 둘째 집합의 교집합이 공집합이 아니기 때문이다({6, 7}). (원문이 조금 이상해서 수정함) 서로소의 합집합이 원래 집합이되는 부분집합들의 집합을 파티션이라고 부른다. 예를 들어, 다음은 집합 {1, 2, 3, 4, 5}의 파티션이다:{{1, 2}, {3}, {4, 5}} A pairwise disjoint collection (set) o..
2013. 11. 12.