표준 레이블의 정의
그래프 동형성(graph isomorphism) 문제를 다루는 표준적인 방법 중 하나는 각 그래프를 코드(code) 또는 표준 레이블(canonical label)이라 불리는 특정 문자열 표현으로 변환하는 것입니다. 표준 레이블의 가장 중요한 성질은 다음과 같습니다.
두 그래프가 동형(isomorphic)이라면, 두 그래프의 코드는 반드시 동일해야 한다.
이 성질 덕분에 우리는 그래프 자체를 직접 비교하는 대신, 각 그래프의 표준 레이블만 분석함으로써 동형성 여부를 손쉽게 판별할 수 있습니다.
1단계: 인접 행렬(Adjacency Matrix) 구하기
그래프의 표준 레이블을 만드는 첫 번째 단계는 해당 그래프에 대한 인접 행렬(adjacency matrix) 표현을 찾는 것입니다.
그러나 하나의 그래프는 인접 행렬을 여러 가지 방식으로 표현할 수 있습니다. 그 이유는 인접 행렬에서 정점(vertex)들을 배치하는 순서가 다양할 수 있기 때문입니다. 예를 들어 첫 번째 행과 열은 3개의 간선(edge)을 가진 정점 a에 대응하고, 두 번째 행과 열은 2개의 간선을 가진 또 다른 정점에 대응하는 식으로 배열 순서를 바꿀 수 있습니다.
따라서 그래프의 모든 인접 행렬 표현을 도출하려면, 행렬의 행들에 대해 가능한 모든 순열(permutation)을 고려해야 합니다.
2단계: 치환 행렬을 이용한 행렬 변환 예제
예제 행렬 M
M = 1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
다음과 같은 치환 행렬(permutation matrix)을 사용하면 행렬 M의 첫 번째 행(및 열)과 세 번째 행(및 열)을 서로 교환할 수 있습니다.
치환 행렬 P₁₃
P₁₃ = 0 0 1 0
0 1 0 0
1 0 0 0
0 0 0 1
여기서 P₁₃은 단위 행렬(identity matrix)의 첫 번째 행과 세 번째 행을 맞바꾸어 얻은 행렬입니다. 첫 번째와 세 번째 행(및 열)을 교환하려면, 치환 행렬을 M과 곱하면 됩니다.
변환된 행렬 M′
M′ = P₁₃ᵀ × M × P₁₃ = 11 10 9 12
7 6 5 8
3 2 1 4
15 14 13 16
3단계: 문자열 표현 생성 및 최종 레이블 선택
두 번째 단계는 각 인접 행렬에 대한 문자열 표현(string representation)을 결정하는 것입니다. 인접 행렬은 대칭(symmetric) 구조를 가지므로, 행렬 전체가 아닌 상삼각행렬(upper triangular part) 부분만 이용하여 문자열을 생성하는 것이 효율적입니다.
코드는 상삼각행렬의 원소들을 열(column) 방향으로 연결하여 얻습니다. 마지막 단계는 그래프의 모든 문자열 표현을 서로 비교한 뒤, 그중 사전순(lexicographic)으로 가장 작은 값(또는 가장 큰 값)을 가진 것을 표준 레이블로 선택하는 것입니다.
계산 복잡도 문제와 최적화 방법
앞서 설명한 방식은 계산 비용이 매우 큽니다. 그래프의 가능한 모든 인접 행렬을 구하고, 각 행렬의 문자열 표현을 일일이 평가하여 표준 레이블을 찾아야 하기 때문입니다. 실제로 정점이 k개인 그래프의 경우 k!개의 순열을 모두 처리해야 하므로, 정점 수가 늘어나면 계산량이 기하급수적으로 증가합니다.
이러한 복잡도를 낮추기 위해 다음과 같은 다양한 기법들이 개발되었습니다.
- 캐싱(caching): 이전에 계산된 표준 레이블을 저장해 두었다가 재사용하여 중복 계산을 방지합니다.
- 순열 수 축소: 정점 레이블(vertex label)이나 정점의 차수(degree) 같은 추가 정보를 활용하여, 표준 레이블을 결정하는 데 필요한 순열의 개수를 줄입니다.
이러한 최적화 기법들을 통해 표준 레이블 기반의 그래프 동형성 검사를 더욱 효율적으로 수행할 수 있습니다.