Graph Isomorphism
Graph Isomorphism 은 G 의 노드 u 와 v 가 인접하면, H 의 u와 v 도 인접하는 일대일 대응을 Edge Preserving bijection 이라고 한다.
Graph Isomorphism Problem 은 두개의 유한한 그래프가 isomorphic 한지 판단하는 복잡도 문제이다.
injection : 일대일함수, One-to-one 함수, 단사함수,
bijection : One-to-one correspondence, 일대일 대응, 전단사 함수
surjection : 전사함수, onto 함수
그래프 동형성을 파악할 때, 그래프가 연결되어 있지 않아도(disconnected) 동형성을 파악하는 것 가능하다고 생각한다. 그래프 동형성 문제란 눈으로는 다르게 보이지만, 실제로는 같은 것을 찾아내는 것을 의미한다.
Last updated
