이번에 더 배울 것
두 그래프 G와 H의 노드 사이에 일대일 대응이 있어서, G에서 이어진 두 노드는 H에서도 대응하는 두 노드가 이어지고 G에서 이어지지 않은 쌍은 H에서도 이어지지 않으면 두 그래프는 동형(isomorphic)입니다. 노드의 이름과 그림의 배치만 바꾼 것이므로, 연결 구조로 계산하는 모든 값(차수, 거리, 중심성, 커뮤니티)이 대응하는 노드끼리 같습니다.
동형인지 의심될 때는 먼저 불변량(invariant)을 비교합니다. 노드 수, 엣지 수, 차수를 크기순으로 늘어놓은 차수 수열, 삼각형 수, 연결 요소 수, 지름처럼 이름을 바꿔도 변하지 않는 값입니다. 하나라도 다르면 동형이 아닙니다. 하지만 모든 불변량이 같다고 동형이 보장되지는 않으므로, 마지막 확인은 실제 대응을 찾아 모든 엣지가 맞는지 대조하는 것입니다.
일반적인 그래프 동형 판정은 다항 시간 알고리즘이 있는지도, NP-완전인지도 알려지지 않은 드문 문제입니다. 바바이(Babai)가 2015년에 발표하고 2017년에 수정한 준다항 시간 알고리즘이 이론적 상한을 크게 낮췄습니다. 실무에서는 데이터 중복 찾기, 화학 구조 검색, 그래프 질의에서 같은 모양 찾기(부분 그래프 동형) 같은 형태로 이 문제를 만납니다.
작은 예제로 따라가기
G: 1–2, 2–3, 3–4, 4–1과 H: 가–다, 다–나, 나–라, 라–가는 둘 다 네모입니다. 1→가, 2→다, 3→나, 4→라로 대응시키면 G의 엣지 4개가 H의 엣지 4개와 정확히 일치하므로 동형입니다.
노드 6개짜리 고리와 삼각형 두 개는 노드 6개, 엣지 6개, 차수가 모두 2로 같지만, 고리는 연결 요소 1개·삼각형 0개이고 다른 쪽은 연결 요소 2개·삼각형 2개라 동형이 아닙니다.
동아리 네트워크는 민수↔보라, 지아↔유나, 서준↔태오, 하린↔도윤으로 이름을 바꿔도 엣지 목록이 그대로입니다. 이런 자기 자신과의 대응(자기 동형) 때문에 두 무리의 차수·매개 중심성·군집 계수가 대칭으로 같았습니다.
불변량으로 먼저 걸러 내기
두 그래프가 동형인지 판정하기 전에, 어떤 불변량에서 차이가 드러날지 먼저 예상하세요.
불변량이 모두 같아 동형 후보가 되었고, 1→가, 2→다, 3→나, 4→라 대응으로 엣지 4개를 대조해 확정했습니다.
학습을 시작하면 새 문제를 직접 풀고 확인 퀴즈를 마친 뒤 선택한 본과정 회차로 돌아갑니다.