ในทฤษฎีกราฟซึ่งเป็นสาขาหนึ่งของคณิตศาสตร์ ปัญหาการหาฟอร์มมาตรฐานของกราฟ ( graph canonization)คือปัญหาของการหา ฟอร์มมาตรฐาน ของกราฟG ที่กำหนดให้ ฟอร์มมาตรฐานคือกราฟที่มีป้ายกำกับ Canon( G ) ที่สมมาตรกับGโดยที่กราฟทุกกราฟที่สมมาตรกับGจะมีฟอร์มมาตรฐานเดียวกันกับGดังนั้น จากการแก้ปัญหาการหาฟอร์มมาตรฐานของกราฟ เราสามารถแก้ปัญหาเรื่องความสมมาตรของกราฟ ได้เช่นกัน กล่าว คือ ในการทดสอบว่ากราฟGและHสมมาตรกันหรือไม่ ให้คำนวณฟอร์มมาตรฐาน Canon( G ) และ Canon( H ) ของกราฟทั้งสอง แล้วทดสอบว่าฟอร์มมาตรฐานทั้งสองนี้เหมือนกันหรือไม่

รูปแบบมาตรฐานของกราฟเป็นตัวอย่างของตัวแปรคงที่ของกราฟที่สมบูรณ์ : กราฟที่สมมาตรกันสองกราฟจะมีรูปแบบมาตรฐานเดียวกัน และกราฟที่ไม่สมมาตรกันสองกราฟจะมีรูปแบบมาตรฐานที่แตกต่างกัน^{[ 1 ] [ 2 ]}ในทางกลับกัน ตัวแปรคงที่ที่สมบูรณ์ของกราฟทุกตัวสามารถใช้สร้างรูปแบบมาตรฐานได้^{[ 3 ]}เซตของจุดยอดของ กราฟ n จุดยอด สามารถระบุได้ด้วยจำนวนเต็มตั้งแต่ 1 ถึงnและการใช้การระบุเช่นนี้ทำให้รูปแบบมาตรฐานของกราฟสามารถอธิบายได้ว่าเป็นลำดับการเรียงสับเปลี่ยนของจุดยอด รูปแบบมาตรฐานของกราฟยังเรียกว่าการกำหนดป้ายกำกับมาตรฐาน^{[ 4 ]}และการทำให้กราฟเป็นมาตรฐานบางครั้งก็เรียกว่าการทำให้กราฟเป็นมาตรฐาน

ปัญหาความเหมือนกันของกราฟเป็นปัญหาการคำนวณ ในการพิจารณาว่า กราฟจำกัดสอง กราฟ มีความเหมือนกันหรือไม่เห็นได้ชัดว่าปัญหาการทำให้เป็นมาตรฐานของกราฟนั้นยากในการคำนวณ อย่างน้อยก็ เท่ากับปัญหาความเหมือนกันของกราฟในความเป็นจริง ความเหมือนกันของกราฟสามารถลดรูปได้เป็นAC ⁰ไปสู่การทำให้เป็นมาตรฐานของกราฟ อย่างไรก็ตาม ยังคงเป็นคำถามที่เปิดอยู่ว่าปัญหาทั้งสองนั้นเทียบเท่ากันในเวลาพหุนาม หรือ ไม่^{[ 2 ]}

ในปี 2019 László Babaiได้ประกาศ อัลกอริทึม แบบกึ่งพหุนามเวลาสำหรับการสร้างกราฟมาตรฐาน นั่นคือ อัลกอริทึมที่มีเวลาทำงานสำหรับค่าคงที่บางค่า[ ^{5 ] แม้ว่า}การมีอยู่ของอัลกอริทึมแบบพหุนามเวลา (แบบกำหนดได้) สำหรับกราฟไอโซมอร์ฟิซึมยังคงเป็นปัญหาที่เปิดอยู่ในทฤษฎีความซับซ้อนของการคำนวณแต่ในปี 1977 László Babaiได้รายงานว่าด้วยความน่าจะเป็นอย่างน้อย 1 − exp(−O( n )) อัลกอริทึมการจำแนกจุดยอดแบบง่ายๆ จะสร้างป้ายกำกับมาตรฐานของกราฟที่เลือกแบบสุ่มอย่างสม่ำเสมอจากเซตของ กราฟ nจุดยอดทั้งหมดหลังจากขั้นตอนการปรับปรุงเพียงสองขั้นตอน การปรับเปลี่ยนเล็กน้อยและ ขั้นตอน การค้นหาแบบเจาะลึก ที่เพิ่มเข้ามา จะสร้างป้ายกำกับมาตรฐานของกราฟสุ่มที่เลือกอย่างสม่ำเสมอในเวลาที่คาดหวังเชิงเส้น ผลลัพธ์นี้ให้ความกระจ่างเกี่ยวกับคำถามที่ว่าทำไมอัลกอริทึมไอโซมอร์ฟิซึมของกราฟที่รายงานจำนวนมากจึงทำงานได้ดีในทางปฏิบัติ^{[ 6 ] [ 7 ]}นี่เป็นความก้าวหน้าครั้งสำคัญในทฤษฎีความซับซ้อนเชิงความน่าจะเป็นซึ่งเป็นที่รู้จักกันอย่างแพร่หลายในรูปแบบต้นฉบับ และยังคงถูกอ้างถึงว่าเป็น "ต้นฉบับที่ยังไม่ได้ตีพิมพ์" เป็นเวลานานหลังจากที่รายงานในงานสัมมนา ${\displaystyle 2^{O((\log n)^{c})}}$${\displaystyle c>0}$

รูปแบบมาตรฐานที่รู้จักกันทั่วไปคือ กราฟ ที่เล็กที่สุดตามลำดับตัวอักษรภายในคลาสไอโซมอร์ฟิซึมซึ่งเป็นกราฟของคลาสที่มีเมทริกซ์ประชิด ที่เล็กที่สุด ตามลำดับตัวอักษรซึ่งถือว่าเป็นสตริงเชิงเส้น อย่างไรก็ตาม การคำนวณกราฟที่เล็กที่สุดตามลำดับตัวอักษรเป็นปัญหา NP- hard ^{[ 8 ]}

สำหรับต้นไม้ อัลกอริทึมการกำหนดมาตรฐานแบบกระชับในเวลาพหุนามที่ต้องการพื้นที่O ( n ) ได้รับการนำเสนอโดย Read (1972) [ ^{9 ] เริ่ม}ต้นด้วยการติดป้ายกำกับแต่ละจุดยอดด้วยสตริง 01 ทำซ้ำสำหรับx ที่ไม่ใช่ใบ ให้ลบ 0 ที่อยู่ข้างหน้าและ 1 ที่อยู่ข้างหลังออกจาก ป้ายกำกับของ xจากนั้นเรียงลำดับ ป้ายกำกับของ xพร้อมกับป้ายกำกับของใบที่อยู่ติดกันทั้งหมดตามลำดับตัวอักษร รวมป้ายกำกับที่เรียงลำดับเหล่านี้เข้าด้วยกัน เพิ่ม 0 ที่อยู่ข้างหน้าและ 1 ที่อยู่ข้างหลังกลับเข้าไป ทำให้เป็นป้ายกำกับใหม่ของxและลบใบที่อยู่ติดกัน หากเหลือจุดยอดสองจุด ให้รวมป้ายกำกับของจุดยอดทั้งสองเข้าด้วยกันตามลำดับตัวอักษร

การทำให้กราฟเป็นแบบมาตรฐานเป็นหัวใจสำคัญของอัลกอริทึมการเปรียบเทียบกราฟหลายๆ แบบ หนึ่งในเครื่องมือชั้นนำคือ Nauty ^{[ 10 ]}

การประยุกต์ใช้การทำให้กราฟเป็นแบบมาตรฐานโดยทั่วไปคือการขุดข้อมูล กราฟิก โดยเฉพาะอย่างยิ่งในแอปพลิเคชันฐานข้อมูลทางเคมี^{[ 11 ]}

ตัวระบุสารเคมีจำนวนหนึ่งเช่นSMILESและInChIใช้ขั้นตอนการกำหนดมาตรฐานในการคำนวณ ซึ่งโดยพื้นฐานแล้วคือการกำหนดมาตรฐานของกราฟที่แสดงถึงโมเลกุล^{[ 12 ] [ 13 ] [ 14 ]}ตัวระบุเหล่านี้ได้รับการออกแบบมาเพื่อจัดหาวิธีมาตรฐาน (และบางครั้งมนุษย์สามารถอ่านได้) ในการเข้ารหัสข้อมูลโมเลกุลและเพื่ออำนวยความสะดวกในการค้นหาข้อมูลดังกล่าวในฐานข้อมูลและบนเว็บ

• รูปแบบมาตรฐาน  – การแสดงผลแบบมาตรฐานของวัตถุทางคณิตศาสตร์
• การทำให้ เป็นรูปแบบมาตรฐาน (Canonicalization)  – กระบวนการแปลงข้อมูลให้เป็นรูปแบบ "มาตรฐาน" "ปกติ" หรือรูปแบบมาตรฐาน