그래프 동형 문제를 처리하는 표준 방법은 각 그래프를 해당 코드 또는 표준 레이블이라고 하는 특정 문자열 표현으로 매핑하는 것입니다. 표준 레이블에는 두 그래프가 동형이므로 코드가 같아야 하는 속성이 있습니다.
이 속성을 사용하면 그래프의 표준 레이블을 분석하여 그래프 동형을 테스트할 수 있습니다. 그래프의 표준 레이블을 구축하기 위한 첫 번째 단계는 그래프에 대한 인접 행렬 설명을 찾는 것입니다. 주어진 그래프에 대한 그러한 행렬의 인스턴스를 보여줍니다.
인접 행렬의 꼭짓점을 정렬하는 여러 방법이 있기 때문에 그래프는 하나 이상의 인접 행렬 설명을 가질 수 있습니다. 첫 번째 행과 열은 3개의 모서리가 있는 꼭짓점 a와 연관되고 두 번째 행과 열은 2개의 모서리가 있는 다른 꼭짓점 a와 연관됩니다. 그래프에 대한 모든 인접 행렬 설명을 파생시킬 수 있습니다. 행렬 행의 가능한 모든 순열을 처리했습니다.
예 − 다음 매트릭스를 고려하십시오.
M = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
다음 순열 행렬을 사용하여 첫 번째 행(및 열)을 M -
의 세 번째 행으로 변환할 수 있습니다.P13 = 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1
여기서 P13 단위 행렬의 첫 번째 행과 세 번째 행을 교환하여 획득합니다. 첫 번째 및 세 번째 행(및 열)을 교환할 수 있으며, 순열 행렬에 M −
를 곱합니다.M′ = P13T X M X P13= 11 10 9 12 7 6 5 8 3 2 1 4 15 14 13 16
두 번째 단계는 각 인접 행렬에 대한 문자열 설명을 결정하는 것입니다. 인접행렬은 대칭이기 때문에 행렬의 상부 삼각 부분에 따라 문자열 설명을 생성하는 것이 효율적입니다.
코드는 열 방향 방식으로 상부 삼각 행렬의 항목을 연결하여 획득됩니다. 마지막 단계는 그래프의 모든 문자열 설명을 연관시키고 가장 낮은(또는 가장 높은) 사전 값을 가진 것을 선택하는 것입니다.
이전 접근 방식은 그래프의 가능한 모든 인접 행렬을 결정하고 표준 레이블을 발견하기 위해 각 문자열 설명을 평가해야 했기 때문에 비용이 많이 듭니다. 또한 k개의 꼭짓점을 포함하는 각 그래프에 대해 처리해야 하는 kl개의 순열이 있습니다.
이 작업의 복잡성을 낮추기 위해 개발된 다양한 방법에는 이전에 계산된 표준 레이블을 캐싱하고 정점 레이블 및 정점의 정도를 포함하여 더 많은 데이터를 통합하여 표준 레이블을 결정하는 데 필요한 순열 수를 줄이는 것이 포함됩니다.