วิธีมาตรฐานสำหรับจัดการ graph isomorphism issues คือ map แต่ละ graph เป็น string representation เฉพาะเจาะจง เรียกว่า code หรือ canonical label Canonical label มี property ว่า ถ้า two graphs เป็น isomorphic codes ของพวกเขาจะต้องเท่ากัน
Property นี้ช่วยให้เรา test graph isomorphism ได้โดยเปรียบเทียบ canonical labels ของ graphs ขั้นตอนแรกสู่การสร้าง canonical label ของ graph คือหา adjacency matrix representation สำหรับ graph แสดงตัวอย่าง matrix สำหรับ graph ที่ให้มา
Graph หนึ่งอาจมี adjacency matrix representations มากกว่า 1 เพราะมีหลายวิธี order vertices ใน adjacency matrix Row และ column แรกสอดคล้องกับ vertex a ที่มี 3 edges row และ column ที่สองสอดคล้องกับ vertex a อีกตัวที่มี 2 edges เป็นต้น เพื่อ derive ทุก adjacency matrix representations ต้อง consider all possible permutations of rows ของ matrix
Example − พิจารณา matrix ต่อไปนี้
M = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Permutation matrix ต่อไปนี้ใช้สลับ row แรก (และ column) กับ row ที่สามของ M −
P13 = 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1
โดยที่ P13 ได้มาจากการสลับ row แรกและ row ที่สามของ identity matrix เพื่อสลับ row แรกและ row ที่สาม (และ columns) คูณ permutation matrix กับ M −
M' = P13T X M X P13 = 11 10 9 12 7 6 5 8 3 2 1 4 15 14 13 16
ขั้นตอนที่สองคือกำหนด string representation สำหรับแต่ละ adjacency matrix เนื่องจาก adjacency matrix เป็น symmetric จึงมีประสิทธิภาพที่จะสร้าง string representation จาก upper triangular part ของ matrix
Code ได้มาจากการ concatenate entries ของ upper triangular matrix แบบ column-wise ขั้นตอนสุดท้ายคือเปรียบเทียบ string representations ทั้งหมดของ graph และเลือกตัวที่มี lexicographic value ต่ำสุด (หรือสูงสุด)
แนวทางก่อนหน้านี้ดู costly เพราะต้อง determine ทุก possible adjacency matrices และ evaluate string representations ทุกตัวเพื่อหา canonical label ยิ่งไปกว่านั้น มี k! permutations ที่ต้อง consider สำหรับ graph ที่มี k vertices
มีหลาย methods พัฒนาลด complexity เช่น caching previously computed canonical labels และลดจำนวน permutations โดย incorporate ข้อมูลเพิ่มเติม เช่น vertex labels และ degree ของ vertex
