วิธีมาตรฐานในการจัดการปัญหา isomorphism ของกราฟคือการแมปแต่ละกราฟลงในการแสดงสตริงเฉพาะที่เรียกว่าโค้ดหรือป้ายกำกับตามรูปแบบบัญญัติ ป้ายกำกับตามรูปแบบบัญญัติมีคุณสมบัติที่ว่าหากกราฟสองกราฟเป็นแบบ isomorphic ดังนั้นโค้ดของกราฟควรเท่ากัน
คุณสมบัตินี้ช่วยให้เราสามารถทดสอบ isomorphism ของกราฟโดยการวิเคราะห์ป้ายกำกับตามรูปแบบบัญญัติของกราฟ ขั้นตอนแรกในการสร้างป้ายกำกับตามรูปแบบบัญญัติของกราฟคือการค้นหาคำอธิบายเมทริกซ์ที่อยู่ติดกันสำหรับกราฟ มันแสดงให้เห็นตัวอย่างของเมทริกซ์ดังกล่าวสำหรับกราฟที่กำหนด
กราฟสามารถมีคำอธิบายเมทริกซ์ที่อยู่ติดกันได้มากกว่าหนึ่งรายการ เนื่องจากมีหลายวิธีในการเรียงลำดับจุดยอดในเมทริกซ์ที่อยู่ติดกัน แถวและคอลัมน์แรกสัมพันธ์กับจุดยอด a ที่มี 3 ขอบ แถวที่สองและคอลัมน์สัมพันธ์กับอีกจุดยอด a ที่มี 2 ขอบ ฯลฯ สามารถเปลี่ยนที่มาของคำอธิบายเมทริกซ์ที่อยู่ติดกันทั้งหมดสำหรับกราฟได้ ซึ่งจะต้องเป็น ปฏิบัติต่อการเปลี่ยนแปลงที่เป็นไปได้ทั้งหมดของแถวของเมทริกซ์
ตัวอย่าง − พิจารณาเมทริกซ์ต่อไปนี้
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
ขั้นตอนที่สองคือการกำหนดคำอธิบายสตริงสำหรับเมทริกซ์ที่อยู่ติดกันแต่ละเมทริกซ์ เนื่องจากเมทริกซ์ส่วนต่อประสานมีความสมมาตร จึงมีประสิทธิภาพในการสร้างคำอธิบายสตริงโดยขึ้นอยู่กับส่วนสามเหลี่ยมบนของเมทริกซ์
รหัสได้มาโดยการเชื่อมโยงรายการของเมทริกซ์สามเหลี่ยมบนในรูปแบบคอลัมน์ ขั้นตอนสุดท้ายคือการเชื่อมโยงคำอธิบายสตริงทั้งหมดของกราฟและเลือกรายการที่มีค่าพจนานุกรมศัพท์ต่ำที่สุด (หรือสูงสุด)
วิธีก่อนหน้านี้ดูมีค่าใช้จ่ายสูง เนื่องจากเราต้องกำหนดเมทริกซ์ความใกล้เคียงที่เป็นไปได้ทั้งหมดของกราฟ และประเมินคำอธิบายสตริงแต่ละรายการเพื่อค้นหาป้ายกำกับตามรูปแบบบัญญัติ นอกจากนี้ยังมีการเรียงสับเปลี่ยน kl ที่ควรได้รับการปฏิบัติสำหรับแต่ละกราฟที่มีจุดยอด k
มีวิธีการต่างๆ มากมายที่พัฒนาขึ้นเพื่อลดความซับซ้อนของงานนี้ โดยประกอบด้วยการแคชป้ายกำกับ Canonical ที่คำนวณไว้ก่อนหน้านี้ และลดจำนวนการเรียงสับเปลี่ยนที่จำเป็นในการตัดสินใจเลือกป้ายกำกับตามรูปแบบบัญญัติด้วยการรวมข้อมูลเพิ่มเติม รวมถึงป้ายกำกับจุดยอดและระดับของจุดยอด
