관계의 합성과 폐포

버스 노선에서 한 번에 갈 수 있는 정류장과, 한 번 갈아타고 갈 수 있는 정류장은 다릅니다. 갈아타기를 허락하면 갈 수 있는 곳이 늘어나고, 몇 번이든 갈아탈 수 있다면 더 늘어납니다. 이 글에서는 관계의 성질을 바탕으로, 두 관계를 이어 붙이는 합성과, 관계에 필요한 쌍을 더해 원하는 성질을 갖게 만드는 폐포를 계산합니다.

합성: 중간 원소를 거쳐 잇기

R이 A에서 B로의 관계이고 S가 B에서 C로의 관계일 때, a에서 R로 b에 가고 b에서 S로 c에 가는 중간 원소 b가 있으면 a와 c를 잇는 새 관계를 만들 수 있습니다. 이것을 R과 S의 합성(composition)이라 하고 $S\circ R$로 씁니다.

기호의 순서에 주의해야 합니다. $S\circ R$은 오른쪽의 R을 먼저, 왼쪽의 S를 나중에 적용합니다. 함수의 합성에서 $g\circ f$가 f를 먼저 적용하는 것과 같은 약속입니다. 교재에 따라 반대로 쓰기도 하므로, "R 다음 S"처럼 말로 확인해 두는 것이 안전합니다.

$R=\{(1,a),(2,a),(2,b)\}$, $S=\{(a,x),(b,y)\}$이면, 1→a→x에서 $(1,x)$, 2→a→x에서 $(2,x)$, 2→b→y에서 $(2,y)$를 얻습니다. 1에서 R로 b에 가는 쌍이 없으므로 $(1,y)$는 들어가지 않습니다. 아래 그림은 1에서 시작해 중간 원소 a를 거쳐 x에 닿는 과정입니다.

def compose(R, S):
    return {(a, c) for a, b in R for b2, c in S if b == b2}


R = {(1, "a"), (2, "a"), (2, "b")}
S = {("a", "x"), ("b", "y")}
print(sorted(compose(R, S)))
print(sorted((b, a) for a, b in R))

[(1, 'x'), (2, 'x'), (2, 'y')]
[('a', 1), ('a', 2), ('b', 2)]

compose는 R의 쌍 $(a,b)$와 S의 쌍 $(b_2,c)$를 모두 짝지어, 중간 원소가 같은 경우($b=b_2$)마다 $(a,c)$를 모읍니다. 둘째 줄은 R의 모든 순서쌍의 방향을 뒤집은 역관계(inverse relation) $R^{-1}$입니다. 역관계는 어떤 관계에나 있으며, 6장에서 볼 역함수가 있는지와는 다른 개념입니다.

폐포: 필요한 쌍만 더하기

관계 R이 원하는 성질을 갖지 않을 때, R의 쌍을 하나도 빼지 않고 필요한 쌍만 더해 그 성질을 갖게 만든 가장 작은 관계를 그 성질의 폐포(closure)라고 합니다. 반사 폐포는 R에 모든 $(a,a)$를 더한 것이고, 대칭 폐포는 R에 역관계를 합친 $R\cup R^{-1}$입니다. 추이 폐포는 R의 화살표를 한 번 이상 따라가 닿을 수 있는 모든 쌍의 집합입니다.

$A=\{1,2,3\}$ 위의 $R=\{(1,2),(2,3)\}$로 세 폐포를 구하면, 반사 폐포는 자기 쌍 세 개를 더한 5개, 대칭 폐포는 $(2,1)$과 $(3,2)$를 더한 4개, 추이 폐포는 $(1,3)$ 하나를 더한 3개입니다. 추이 폐포에는 자기 쌍이 들어가지 않는다는 점에 주의해야 합니다. 추이성은 "이어지는 두 쌍이 있으면"이라는 조건이라 자기 쌍을 저절로 요구하지 않습니다. 다만 1→2→1처럼 사이클이 있으면 두 번 따라가 1→1에 닿으므로 그때는 자기 쌍이 들어갑니다.

추이 폐포는 반복해서 구한다

추이 폐포를 구하는 간단한 방법은, 이어지는 두 쌍 $(a,b)$와 $(b,c)$가 있는데 $(a,c)$가 없으면 더하는 일을 새 쌍이 생기지 않을 때까지 되풀이하는 것입니다. 한 번만 하고 멈추면 안 됩니다. 새로 더한 쌍이 다른 쌍과 이어져 또 새 쌍을 만들 수 있기 때문입니다.

def one_round(R):
    return R | {(a, d) for a, b in R for c, d in R if b == c}


def transitive_closure(R):
    closure = set(R)
    while True:
        new = {(a, d) for a, b in closure for c, d in closure if b == c} - closure
        if not new:
            return closure
        closure |= new


R = {(1, 2), (2, 3), (3, 4)}
print(sorted(one_round(R)))
print(sorted(transitive_closure(R)))
print(sorted(transitive_closure({("a", "b"), ("b", "a")})))

[(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)]
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
[('a', 'a'), ('a', 'b'), ('b', 'a'), ('b', 'b')]

한 번만 더하면 두 단계 경로의 $(1,3)$과 $(2,4)$만 생기고, 세 단계 경로의 $(1,4)$는 빠집니다. $(1,4)$는 새로 생긴 $(1,3)$과 원래의 $(3,4)$가 이어져야 나오기 때문입니다. 반복하는 함수는 둘째 차례에 $(1,4)$를 더하고, 셋째 차례에 새 쌍이 없어 멈춥니다. 원소가 n개이면 쌍은 많아야 $n^2$개이므로, 차례마다 적어도 하나씩 쌍이 늘어나는 이 반복은 반드시 끝납니다. 마지막 예는 a와 b가 서로를 가리키는 사이클이라 자기 쌍 $(a,a)$와 $(b,b)$가 생겼습니다.

R을 정확히 k번 이어 붙인 관계를 $R^k$라 하면, 추이 폐포는 $R^+=R\cup R^2\cup R^3\cup\cdots$로도 쓸 수 있습니다. 여기에 한 번도 따라가지 않는 경우, 곧 모든 자기 쌍까지 넣은 것을 반사 추이 폐포 $R^*$라고 합니다. 추이 폐포는 Warshall 알고리즘이 구하는 도달 가능성의 표와 같은 것이고, 행렬로 계산하는 방법은 관계 행렬에서 다룹니다.

정리

• 관계의 합성 $S\circ R$은 R 다음 S를 적용해, 중간 원소를 거쳐 이어지는 쌍을 모은 관계입니다. 기호의 순서와 적용 순서가 반대라는 점에 주의합니다.
• 역관계 $R^{-1}$은 모든 순서쌍의 방향을 뒤집은 관계이며, 어떤 관계에나 있습니다.
• 폐포는 원래 쌍을 빼지 않고 필요한 쌍만 더해 원하는 성질을 갖게 만든 가장 작은 관계입니다. 반사 폐포는 자기 쌍을, 대칭 폐포는 역관계를 더합니다.
• 추이 폐포는 한 번 이상 따라가 닿을 수 있는 모든 쌍이며, 새 쌍이 생기지 않을 때까지 반복해 구합니다. 한 번만 더하면 긴 경로를 놓칩니다.
• 추이 폐포는 사이클이 있을 때만 자기 쌍을 포함하고, 모든 자기 쌍까지 넣은 것은 반사 추이 폐포 $R^*$입니다.

연습 문제

1. 네 원소의 추이 폐포

$A=\{1,2,3,4\}$ 위의 $R=\{(1,2),(2,3),(3,4)\}$에 대해, 추이 폐포를 구하는 반복이 각 차례에 어떤 쌍을 더하는지 쓰세요.

2. 사이클과 자기 쌍

$A=\{a,b,c\}$ 위의 $R=\{(a,b),(b,a)\}$에 대해 $R^+$와 $R^*$를 구하고 차이를 설명하세요.

3. 합성의 순서

본문의 R과 S에 대해 $R\circ S$를 계산할 수 있나요? 계산할 수 없다면 그 이유를 설명하세요.

합성의 순서가 헷갈리면 화살표를 실제로 따라가 보세요. 같은 무리로 묶는 관계의 조건은 다음 글 동치관계와 부분순서에서 이어집니다.