이산수학 4

4.1. 닫힘

집합 A에 관한 관계 R이 있고, R이 가질 수 있는 성질을 P라고 할 때,

집합 A에 관한 관계 R_1이 관계 R을 포함하면서 성질 P를 갖는다면,

관계 R_1을 관계 R에 대한 “P닫힘(또는 폐포)”이라고 표현합니다.

이때, P는 닫힘 또는 “폐포”로도 표현하고, 반사, 대칭, 추이 관계 등이 존재합니다.

R_1은 관계 R을 포함하면서 우리가 원하는 성질을 만족시키는 가장 작은 관계가 될 것입니다.

다음은 폐포의 종류 세 가지에 대해 나열 한 것입니다.

집합 A에 대한 관계 R이 정의 될 때,

1). “반사 폐포”(Reflexive Closure) : R \cup {(a, a) | a \in A} 인 가장 작은 관계 R_1을 “반사 폐포”라고 정의합니다.

2). “대칭 폐포”(Symmetric Closure) : R \cup {(b, a) \in A \times A | (a, b) \in R} 인 가장 작은 관계 R_1을 “대칭 폐포”라고 정의합니다.
( 쉽게 R \cup R^{-1} 라고도 표현 가능 합니다. )

3). “추이 폐포”(Transitive Closure) : R^{\inf}(연결관계)가 되는 가장 작은 관계 R_1을 “추이 폐포”라고 정의합니다.
(연결관계에 대한 내용은 3.3절에 자세하게 설명되어 있습니다. )

4.2. 와샬 알고리즘

추이 폐포를 구하기 위해서는 연결 관계를 구하면 된다는 것을 배웠습니다.

그런데 연결 관계의 정의는 모든 연결의 존재를 알기 위해서 부울곱과 \vee 연산을 반복하여 값을 구해내는데

이론적으로 무한 번 진행하면, 실제로는 더 이상 값의 변화가 없는 지점까지 진행하여 추이 폐포를 구할 수 있습니다.

물론 이렇게 값을 구하는 것은 효율적이지 않기에 실제로는 사용되는 방식은 아닙니다.

위의 방식을 코딩한다면, 시간복잡도를 언급 할 필요 없이 상당한 시간이 걸릴 것입니다.

“와샬 알고리즘”(Warshall Algorithm)은 해당 문제를 시간복잡도 O(n^3)에 풀리게 하는 알고리즘입니다.

와샬 알고리즘의 단계는 다음과 같습니다.

1). 와샬 알고리즘에서 사용하는 관계행렬을 W_k로 둔다면, W_1 = M_R (M_R은 관계 R의 관계 행렬) 이고,

M_R의 행(또는 열)의 크기를 n이라고 정의한다면, (즉, M_R은 n \times n 행렬) W_n까지 값을 구하고,

결과를 W_n으로 정합니다.

( 루프가 없다면, 모든 정점을 한 번씩 모두 지나는 루트가 가장 길 것이므로

매 최소 경로만 파악한다는 가정이 있으면, n회 만에 모든 경로를 정할 수 있게 됩니다. )

2). W_{k-1}값은 W_k에 그대로 전파되고, W_k의 i행 j열의 값을 \sum_{x = 1}^{n} W_k[i][x] \wedge W_k[x][j]으로 다음 추이 관계들을 구합니다.
( 잘 보면 부울곱의 식과 같다는 것을 볼 수 있습니다. 이유는 생각해보면 추이 관계를 구하는 과정이기에 그렇습니다. )

3). 해당 과정을 반복하여 W_n까지 구한다면, W_n은 M_{R^{\inf}}이 됩니다.

코드로 표현하면, 다음과 같습니다.

#include<iostream>

using namespace std;

int** warshall(int** graph, int n) {
    int** result = new int*[n];
    for (int i = 0; i < n; i++) {
        result[i] = new int[n];
        for (int j = 0; j < n; j++) {
            result[i][j] = graph[i][j];
        }
    }

    // Warshall's algorithm , O(n^3)
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < n; j++) {
                result[i][j] = result[i][j] || (result[i][k] && result[k][j]);
            }
        }
    }

    return result;
}

int main() {
    // Adjacency matrix of a directed graph
    int** graph = new int*[4];
    graph[0] = new int[4]{ 0, 1, 0, 0 };
    graph[1] = new int[4]{ 0, 0, 0, 1 };
    graph[2] = new int[4]{ 1, 0, 0, 0 };
    graph[3] = new int[4]{ 0, 0, 1, 0 };

    int** result = warshall((int**)graph, 4);

    // print W_n matrix
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4;j++) {
            cout << result[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

출력 결과는 다음과 같습니다.

1 1 1 1 
1 1 1 1 
1 1 1 1 
1 1 1 1

집합 A에 대한 동치 관계 R, S가 정의 될 때, R과 S가 둘 다 포함되는 가장 작은 동치 관계는 (R \cup S)^{\inf} 가 됩니다.

이 때, M_{R \cup S} = M_R \vee M_S 가 되고, 연결 관계는 동일하게 와샬 알고리즘으로 풀 수 있습니다.

W_0을 M_{R \cup S}로 둔다면, W_n : (n은 M_{R \cup S}의 행 (또는 열) 의 개수) 가 M_{(R \cup S)^{\inf}}

즉, 결과 값을 도출 할 수 있게 됩니다.