9 관계 Relations 4

관계의 폐쇄Closures of Relations

컴퓨터 네트워크는 데이터 센터들을 가지고 있습니다. 위치는 Boston, Chicago, Denver, Detroit, New York, San Diego 입니다. 이 일방향 전화라인들이 다음 위치에 설치되어 있습니다. Boston to Chicago, Boston to Detroit, Chicago to Detroit, Detroit to Denver, New York, San Diego. R을 (a,b)로 구성된 관계라고 합시다. 이 순서쌍은 데이터 센터 a에서 b로의 전화선이 있음을 표시합니다. 어떻게하면 한 도시에서 다른 도시간에 전화연결이 되어있는지 판단할 수 있을까요?(간접적이더라도) 모든 선들이 직접적으로 연결된 것은 아니기 때문에, 예로 Boston 에서 Detroit을 통해서 Denver로 가는 전화선, 관계 R은 직접적인 해답이 되지 않을 수 있습니다. 

 관계의 표현으로는, R은 이행적이지 않다면, 연결될 수 있는 순서쌍을 포함하고 있지않습니다. (이것은 위의 예와 같습니다. 위의 전화선은 (Boston, Detroit), (Detroit, Denver) 을 포함하지만,  (Boston, Denver)를 포함하지는 않습니다. 따라서 이행적이지 않습니다.) 이번 섹션에서는, 우리는 전화선을 가진 데이터 센터들의 순서쌍을 찾아볼 것입니다. 이는 이행적인 관계 S를 만듦으로써 수행할 수 있습니다. S는 관계 R을 포함하는 모든 이행적인 관계의 부분 집합입니다. (말이어렵더라면 그냥 넘어가주세요. 직관적으로 이해한 뒤 이렇게 정리되는 글을 보면 왜 이렇게 썼는지 이해가 갑니다.) 여기서, S는 R을 포함하는 가장 작은 이행적 관계입니다. 이 관계를 R의 이행 폐쇄transitive closure 라고 합니다.

보편적으로, R을 집합 A 자신으로의 관계라 합시다. R은 어떤 속성 P를 가지거나 가지지 않을 수 있습니다, P는 반사적, 대칭적, 이행적 등일 수 있습니다. 만약 속성 P를 가진 관계 S가 R을 포함할 때, 이때 S는 속성 P를 가지면서 R을 포함하는 모든 관계들의 부분집합이다, S는 속성 P에 대한 R의 폐쇄라고 합니다. (특정 속성에 대한 한 관계의 폐쇄는 존재하지 않을 수도 있습니다.) 우선은 한 관계의 반사적reflexive, 대칭적symmetric, 이행적transitive 폐쇄를 살펴볼 것입니다.

폐쇄 Closures

관계 R = {(1,1),(1,2),(2,1),(3,2)}는 집합 A = {1,2,3} 자신으로의 관계입니다. 이 관계는 반사적이지 않습니다. 어떻게 R을 포함하는 반사적인 관계를 제공할 수 있습니까? 단 가능한한 작아야합니다. 그렇다면 (2,2)와 (3,3)을 R에 더하면, R은 반사적이 됩니다. 분명히, 이는 R을 포함하는 새로운 관계입니다. 더욱더, R을 포함하면서 반사적인 관계는 반드시 (2,2)와 (3,3)을 가집니다. 이 관계가 R을 포함하고, 반사적이기에, 그리고 R을 포함하는 반사적인 관계를 모두 포함하기에, 따라서 R의 반사적 폐쇄reflexive closure라고 불립니다.

 이 예제처럼, 집합 A 자신으로의 관계 R이 주어졌을때, R의 반사적 폐쇄reflexive closure는 관계 R에 포함되어있지 않은 집합 A의 임의의 원소 a에 대해 (a,a)를 더한 형태입니다. 이런 순서쌍들을 더하면 새로운 관계가 생성되며, 이는 R을 포함하고 반사적입니다. 그리고 R을 포함한 어떠한 반사적 관계를 포함하고 있습니다. 이제부터 R의 반사적 폐쇄reflexive closure는 R∪∆와 같음을 볼 것입니다. 여기서 ∆={(a,a) | a∈A} 는 집합 A 자신으로의 대각 관계입니다. 

예제 1

관계 R의 반사적 폐쇄reflexive closure은 무엇입니까? 여기서 R은 정수들의 집합에서 R = {(a,b)| a<b}

*** R의 반솨적 폐쇄는 다음과 같다. R∪∆ = {(a,b)| a<b}∪{(a,a)| a∈Z} = {(a,b)| a≤b}

집합 {1,2,3} 자신으로의 관계 {(1,1),(1,2),(2,2),(2,3),(3,1),(3,2)}는 대칭적이지 않습니다. 대칭적인 관계를 어떻게 만들수 있습니까? 이 관계는 가능한 작아야하며, R을 포함해야합니다. 목적을 달성하기위해서, (2,1)과 (1,3)을 더하면 됩니다. 왜냐하면 (a,b)∈R이지만 R에 포함되지 않은 (b,a)들이기 때문입니다. 이 새로운 관계는 대칭적symmetric이며 R을 포함합니다. 더욱더, R을 포함하는 어떤 대칭적 관계는 반드시 이 새로운 관계를 포함해야합니다. 왜냐하면 R을 포함하는 대칭적 관계symmetric relation는 반드시 (2,1), (1,3)을 포함해야합니다. 따라서, 이 새로운 관계는 R의 대칭적 폐쇄symmetric closure라고 불립니다.

 앞에 예에서 서술되었듯, 관계 R의 대칭적 폐쇄symmetric closure는 다음과 같은 방법으로 생성될 수 있습니다. (b,a)형식의 순서쌍을 모두 더합니다, 여기서 (a,b)가 관계에 존재하면서, (b,a)는 현재 관계 R에 존재하지 않습니다. 이 (b,a) 순서쌍들을 더하는건, 대칭적이면서 R을 포함하는 새로운 관계를 만드는 것입니다. 그리고 R을 포함한 어느 대칭적인 관계들을 포함하고 있습니다. 관계의 대칭적 폐쇄symmetric closure는 그 관계와 역 관계의 합으로 생성될 수 있습니다. 즉, R∪R^(-1)은 R의 대칭적 폐쇄이며, 여기서 R^(-1) = {(b,a)|(a,b)∈R } 입니다.

예제 2 

양의 정수들의 집합 자신으로의 관계 R = {(a,b)| a>b}의 대칭적 폐쇄symmetric closure는 무엇입니까?

*** R의 대칭적 폐쇄는 다음과 같습니다. R∪R^(-1) = {(a,b) | a>b}∪{(b,a) | a>b} = {(a,b) | a≠b}

R의 모든 순서쌍들은 양의 정수들이며, 여기서 첫 번째 원소는 두 번째 원소보다 커야합니다. R^(-1)은 모든 양의 정수들의 순서쌍들이며, 여기서 두 번째 원소는 첫 번째 원소보다 커야합니다. 따라서 a≠b이 도출됩니다.

R이 이행적이지 않다고 가정합시다. R을 포함하면서 이행적인 관계를 어떻게 만들 수 있습니까? 이 새로운 관계는 R을 포함하는 어떠한 이행적인 관계들을 포함합니다. 관계 R의 이행적 폐쇄transitive closure은 (a,c)형의 순서쌍들을 더함으로써 도출될 수 있습니까? 여기서 (a,b)와 (b,c)가 이미 관계내에 있습니다. 예로, 다음 관계를 고려해봅시다. 집합 {1,2,3,4} 자신으로의 관계 R = {(1,3),(1,4),(2,1),(3,2)}이 있습니다. 이 관계는 이행적이지 않습니다. 왜냐하면 관계 R내에 존재하는 (a,b)와 (b,c)에 대해 모든 (a,c)형식의 순서쌍들을 포함하지 않았기 때문입니다. 관계 R에 순서쌍 (1,2), (2,3), (2,4), (3,1)이 존재하지 않습니다. 그런데 이런 순서쌍들을 더하는 것은 이행적인 관계를 만드는 것이 아닙니다. 왜냐하면 결과로 나온 새로운 관계는 (3,1) (1,4)을 포함하지만 (3,4)를 포함하지 않기 때문입니다. 이는 한 관계의 반사적 폐쇄, 대칭적 폐쇄보다 이행적 폐쇄를 도출하는게 더욱 복잡하다는 것을 보여줍니다. 이 섹션의 마지막에서 볼 것이지만, 한 관계의 이행적 폐쇄는 현재에 반드시 포함해야하는 순서쌍을 더하고 그리고 이 프로세스를 어떠한 새로운 순서쌍이 필요없을 때 까지 반복해야합니다.

방향 그래프에서의 경로 Paths in Directed Graphs

관계를 방향그래프directed graph로 표현하면 이행적 폐쇄를 만드는데 도움이 됨을 보일 것입니다. 우선은 앞서, 이 작업을 수행하기위해서 필요한 용어 몇 개를 소개할까 합니다.

방향그래프에서 경로path란 선들을 가로지르면서 구할 수 있습니다. 

정의 1

방향 그래프 G에서 a에서 b로의 경로path란 G에 존재하는 선들의 나열입니다. (x0,x1), (x1,x2), (x2,x3) , ..., (x(n-1),xn) 여기서 n은 음이아닌 정수이고 x0=a 이고 xn = b입니다. 즉, 선을 이루는 나열은 여기서 선의 마지막 꼭지점은 그 경로의 닫음 선의 첫 번째 꼭지점과 같아야합니다. 이 경로는 다음과 같이 표기됩니다. x0, x1, x2, ...., xn-1, xn 그리고 길이는 n입니다. 선들의 공집합은 a에서 a 자신으로의 길이 0인 경로로 볼 것 입니다. 길이 n≥1이면서 시작 꼭지점과 끝 꼭지점이 같은 경로는 순회(회로)circuit 또는 순환cycle이라고 부릅니다. 

방향 그래프에서 경로path는 한 개 이상의 꼭지점을 통과할 수 있습니다. 더욱더, 방향 그래프에서 선은 한 경로 내에 한 번 이상 발생할 수 있습니다.

예제 3

다음은 아래의 그래프에 존재하는 경로들입니다. 각각의 길이는 몇 인가요? a,b,e,d; a,e,c,d,b; b,a,c,b,a,a,b; d,c; c,b,a; e,b,a,b,a,b,e 또한 이들 중 어떤 경로가 순회circuit합니까? 

*** 각각의 길이는 3, x, 6, 1, 2, 6 입니다. a, e, c, d, b 경로에서 c에서 d로 경로는 그래프상에서 존재하지 않으므로 길이를 정의할 수 없습니다. b, a, c, ... ,b 와 e, b, a ... ,e가 순회합니다.

경로path는 관계relations에도 응용될 수 있습니다. 방향 그래프의 정의를 관계로 들고오면, 관계 R에서 a에서 b로의 경로가 존재한다 만약 엘리먼트의 나열 a, x1, x2, ..., x(n-1), b가 존재하며 (a, x1)∈R, (x1,x2) ∈R 그리고 (x(n-1),b) ∈R. 정리 1은 관계에서의 경로의 정리를 얻어낼 수 있습니다.   

정리 1

집합 A 자신으로의 관계 R이 있다고 하자. a에서 b로의 길이 n의 경로가 존재함은, 여기서 n은 양의 정수, (a,b)∈R^n임의 필요충분조건이다.

증명

수학적 귀납법mathematical induction을 사용할 것이다. 정의에 따라, a에서 b로의 길이 1인 경로가 있음은 (a,b)∈R의 필요 충분조건이다. 따라서 n=1일 때 참이다. (기본단계)

위 정리가 양의 정수 n에 대해 만족한다고 가정하자. 이는 귀납적 가설이다. a에서 b로의 길이 n+1의 경로가 있음은 집합 A에 원소 c가 존재함의 필요충분조건이다. 여기서 c는 a에서 c로의 길이가 1임을 만족하고, 즉 (a,c)∈R이고 c에서 b로의 경로가 길이 n임을,즉 (c,b)∈R^n 만족한다. 결과적으로, 귀납적 가설에 따라, a에서 b로의 길이 n+1인 경로가 존재함은 (a,c)∈R 그리고 (c,b)∈R^n을 만족하는 원소 c가 존재함의 필요충분조건이다. 그러나 그런 엘리먼트가 존재함은 (a,b)∈R^(n+1)임에 대해 필요충분조건이다. 그러므로 a에서 b로의 길이 n+1인 경로가 존재함은 (a,b) ∈R^(n+1)임에 대해 필요충분조건이다.

이행적 폐쇄transitive closures

지금부터 한 관계의 이행적 폐쇄를 알아내는 것은 결합된 방향그래프associated directed graph에서 어떤 꼭지점 순서쌍이 경로에의해 연결되었는지 판단하는 것과 동치임을 볼 것입니다. 이를 명심하고, 다음의 새 관계에 대해 정의합니다.

정의 2

집합 A 자신으로의 관계 R이 있다고하자. 접속 관계connectivity relation R*는 순서쌍 (a,b)로 이루어져있습니다. 이 순서쌍들은 관계에서 a에서 b까지의 길이가 적어도 1 이상인 경로가 존재합니다.

R^n은 순서쌍 (a,b)로 구성되며 a에서 b로의 길이가 n이상인 경로에 해당하므로, R*는 모든 R^n 집합들의 합집합이다. 다른표현으로는 R* =⋃R^n 입니다.

접속 관계는 많은 모델에서 유용합니다.

예제 4