ปัญหาความเหมือนกันของกราฟคือปัญหาการคำนวณ เพื่อพิจารณาว่า กราฟจำกัดสอง กราฟ มีความเหมือนกัน หรือ ไม่^{[ 1 ]}

ปัญหาดังกล่าวยังไม่เป็นที่ทราบแน่ชัดว่าสามารถแก้ไขได้ในเวลาพหุนามหรือเป็นปัญหาNP-completeดังนั้นจึงอาจอยู่ในระดับความซับซ้อน ของการคำนวณ NP-intermediateเป็นที่ทราบกันว่าปัญหาการสมมาตรของกราฟอยู่ในลำดับชั้นต่ำของคลาส NPซึ่งหมายความว่าไม่ใช่ปัญหา NP-complete เว้นแต่ลำดับชั้นของเวลาพหุนามจะยุบตัวลงสู่ระดับที่สอง^{[ 2 ]} ในขณะเดียวกัน การสมมาตรสำหรับกราฟประเภทพิเศษหลายประเภทสามารถแก้ไขได้ในเวลาพหุนาม และในทางปฏิบัติ การสมมาตรของกราฟมักจะสามารถแก้ไขได้อย่างมีประสิทธิภาพ^{[ 3 ] [ 4 ]}

ปัญหานี้เป็นกรณีพิเศษของปัญหาไอโซมอร์ฟิซึมของกราฟย่อย [ ^{5 ]}ซึ่งถามว่ากราฟG ที่กำหนด มีกราฟย่อยที่เป็นไอโซมอร์ฟิกกับกราฟH ที่กำหนดอีกกราฟหนึ่ง ^หรือไม่ ปัญหานี้เป็นที่ทราบกันว่าเป็น NP-complete นอกจากนี้ยังเป็นที่ทราบกันว่าเป็นกรณีพิเศษของปัญหากลุ่มย่อยที่ซ่อนอยู่แบบไม่สลับที่บนกลุ่มสมมาตร^{[ 6 ]}

ในด้านการรับรู้ภาพเป็นที่รู้จักกันในชื่อปัญหาการจับคู่กราฟที่แม่นยำ^{[ 7 ]}

ในเดือนพฤศจิกายน 2015 László Babaiประกาศ อัลกอริทึม ที่มีเวลาทำงานแบบกึ่งพหุนามสำหรับกราฟทั้งหมด นั่นคือ อัลกอริทึมที่มีเวลาทำงานสำหรับค่าคงที่บางค่า[ ^{8 ] [ 9 ] [ 10 ] [ 11 ] ใน}วันที่ 4 มกราคม 2017 Babai ได้ถอนคำกล่าวอ้างเรื่องเวลาทำงานแบบกึ่งพหุนามและระบุ ขอบเขต เวลาแบบต่ำกว่าเลขชี้กำลังแทน หลังจากที่Harald Helfgottค้นพบข้อบกพร่องในการพิสูจน์ ในวันที่ 9 มกราคม 2017 Babai ประกาศการแก้ไข (เผยแพร่ฉบับเต็มในวันที่ 19 มกราคม) และคืนคำกล่าวอ้างเรื่องเวลาทำงานแบบกึ่งพหุนาม โดย Helfgott ยืนยันการแก้ไข^{[ 12 ] [ 13 ]} Helfgott ยังอ้างอีกว่าสามารถใช้c = 3 ได้ ดังนั้นเวลาทำงานจึงเป็น2 ^O(( log ^{n ) 3 ) [ 14 ] [ 15 ]} Babai ได้เผยแพร่ "รายงานเบื้องต้น" เกี่ยวกับงานที่เกี่ยวข้องในงานSymposium on Theory of Computing ปี 2019 ซึ่งอธิบายอัลกอริทึมกึ่งพหุนามสำหรับการสร้างกราฟมาตรฐาน [ ^{16 ] แต่}จนถึงปี 2025 เวอร์ชันเต็มของอัลกอริทึมเหล่านี้ยังไม่ได้รับการเผยแพร่ ${\displaystyle 2^{O((\log n)^{c})}}$${\displaystyle c>0}$

ก่อนหน้านี้ อัลกอริทึมเชิงทฤษฎีที่ได้รับการยอมรับดีที่สุดนั้นมาจากBabai & Luks (1983)ซึ่งอิงจากงานก่อนหน้าของLuks (1982)รวมกับ อัลกอริทึม แบบซับแฟกทอเรียลของ VN Zemlyachenko ( Zemlyachenko, Korneenko & Tyshkevich 1985 ) อัลกอริทึมนี้มีเวลาทำงาน 2 ^{O( √ n  log  n )}สำหรับกราฟที่มีnจุดยอด และอาศัยการจำแนกกลุ่มแบบง่ายจำกัดหากไม่มีทฤษฎีบทการจำแนก กลุ่มนี้ ขอบเขตที่อ่อนกว่าเล็กน้อย 2 ^{O( √ n  log 2  n )}ได้รับมาเป็นครั้งแรกสำหรับกราฟแบบปกติอย่างเข้มแข็งโดยLászló Babai  ( 1980 ) และต่อมาได้ขยายไปยังกราฟทั่วไปโดยBabai & Luks (1983)การปรับปรุงเลขชี้กำลัง√ nสำหรับกราฟแบบปกติอย่างเข้มแข็งนั้นทำโดยSpielman (1996 ) สำหรับไฮเปอร์กราฟที่มีอันดับจำกัด ขอบเขตบนย่อยเลขชี้กำลัง ที่ตรงกับกรณีของกราฟนั้นได้มาจากBabai & Codenotti (2008 )

มีอัลกอริทึมเชิงปฏิบัติหลายตัวที่แข่งขันกันสำหรับการหาความเหมือนกันของกราฟ เช่น อัลกอริทึมของMcKay (1981) , Schmidt & Druffel (1976) , Ullman (1976)และStoichev (2019)แม้ว่าอัลกอริทึมเหล่านี้จะทำงานได้ดีกับกราฟแบบสุ่มแต่ข้อเสียที่สำคัญของอัลกอริทึมเหล่านี้คือประสิทธิภาพด้านเวลาแบบเลขชี้กำลังในกรณีที่เลวร้ายที่สุด^{[ 17 ]}

ปัญหาไอโซมอร์ฟิซึมของกราฟเทียบเท่ากับการคำนวณกลุ่มออโตมอร์ฟิซึมของกราฟ^{[ 18 ] [ 19 ] [ 20 ]}และอ่อนกว่า ปัญหาไอโซมอร์ฟิซึม ของกลุ่มการเรียงสับเปลี่ยนและปัญหาการตัดกันของกลุ่มการเรียงสับเปลี่ยน สำหรับสองปัญหาหลังนี้Babai, Kantor & Luks (1983)ได้รับขอบเขตความซับซ้อนที่คล้ายกับไอโซมอร์ฟิซึมของกราฟ

ปัญหาความเหมือนกันของกราฟในกรณีพิเศษที่สำคัญหลายกรณีมีวิธีแก้ที่มีประสิทธิภาพและใช้เวลาในการประมวลผลแบบพหุนาม:

• ต้นไม้^{[ 21 ] [ 22 ]}
• กราฟระนาบ^{[ 23 ]} (อันที่จริง ไอโซมอร์ฟิซึมของกราฟระนาบอยู่ในปริภูมิล็อก [ ^{24 ] ซึ่ง}เป็นคลาสที่อยู่ในP )
• กราฟช่วง^{[ 25 ]}
• กราฟการเรียงสับเปลี่ยน^{[ 26 ]}
• กราฟวงกลม^{[ 27 ]}
• กราฟพารามิเตอร์ที่มีขอบเขต
  • กราฟของความกว้างต้นไม้ ที่จำกัด ^{[ 28 ]}
  • กราฟที่มีจีนัส จำกัด ^{[ 29 ]} (กราฟระนาบคือกราฟที่มีจีนัส 0)
  • กราฟที่มีดีกรี จำกัด ^{[ 30 ]}
  • กราฟที่มีความหลากหลายของค่าลักษณะเฉพาะ ที่จำกัด ^{[ 31 ]}
  • กราฟ k-หดตัวได้ (การวางนัยทั่วไปของดีกรีที่จำกัดและจีนัสที่จำกัด) ^{[ 32 ]}
  • ไอโซมอร์ฟิซึมที่รักษาสีของกราฟสี ที่มีจำนวนสีจำกัด (กล่าวคือ ^มี จุดยอด ไม่เกินkจุดที่มีสีเดียวกันสำหรับk ที่กำหนด ) อยู่ในคลาสNCซึ่งเป็นคลาสย่อยของP [ ^{33 ]}

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

โดยทั่วไปแล้ว สำหรับระดับความซับซ้อนภายในลำดับชั้นเวลาพหุนามปัญหาจะถูกเรียกว่าGI-hardหากมีการลดรูปทัวริงแบบเวลาพหุนามจากปัญหาใดๆ ในGIไปยังปัญหานั้น กล่าวคือ วิธีแก้ปัญหาแบบเวลาพหุนามสำหรับปัญหา GI-hard จะให้ผลลัพธ์เป็นวิธีแก้ปัญหาแบบเวลาพหุนามสำหรับปัญหาการสมมาตรของกราฟ (และดังนั้นสำหรับปัญหาทั้งหมดในGI ) ปัญหาจะถูกเรียกว่าสมบูรณ์สำหรับGIหรือGI-completeหากเป็นทั้ง GI-hard และวิธีแก้ปัญหาแบบเวลาพหุนามสำหรับปัญหา GI จะให้ผลลัพธ์เป็นวิธีแก้ปัญหาแบบเวลาพหุนามสำหรับปัญหานั้นด้วย ${\displaystyle X}$${\displaystyle X}$

ปัญหาความเหมือนกันของกราฟนั้นมีอยู่ในทั้งNPและ co- AM GI มีอยู่ในและอยู่ในระดับต่ำสำหรับParity Pเช่นเดียวกับมีอยู่ในคลาสSPPที่ อาจมีขนาดเล็กกว่ามาก ^{[ 35 ]}การที่มันอยู่ใน Parity P หมายความว่าปัญหาความเหมือนกันของกราฟนั้นไม่ยากไปกว่าการพิจารณาว่าเครื่องจักรทัวริงแบบไม่กำหนด ในเวลาพหุนาม มีจำนวนเส้นทางที่ยอมรับเป็นเลขคู่หรือเลขคี่ GI ยังมีอยู่ในและอยู่ในระดับต่ำสำหรับZPP ^NPด้วย^{[ 36 ]}โดยพื้นฐานแล้วหมายความว่าอัลกอริทึม Las Vegas ที่มีประสิทธิภาพ ซึ่งสามารถเข้าถึงออราเคิล NP สามารถแก้ปัญหาความเหมือนกันของกราฟได้ง่ายมากจนไม่ได้รับพลังใดๆ จากการได้รับความสามารถในการทำเช่นนั้นในเวลาคงที่

มีวัตถุทางคณิตศาสตร์หลายประเภทที่ปัญหาของไอโซมอร์ฟิซึมเป็นปัญหา GI-complete วัตถุเหล่านั้นบางส่วนเป็นกราฟที่มีคุณสมบัติหรือข้อจำกัดเพิ่มเติม: ^{[ 37 ]}

• ไดกราฟ^{[ 37 ]}
• กราฟที่มีป้ายกำกับโดยมีเงื่อนไขว่าไม่จำเป็นต้องมีไอโซมอร์ฟิซึมเพื่อรักษาป้ายกำกับ^{[ 37 ]}แต่มีเพียงความสัมพันธ์สมมูลที่ประกอบด้วยคู่ของจุดยอดที่มีป้ายกำกับเดียวกัน เท่านั้น
• "กราฟโพลาไรซ์" (สร้างจากกราฟสมบูรณ์ K _mและกราฟว่าง K _nบวกขอบบางส่วนที่เชื่อมต่อทั้งสองเข้าด้วยกัน ไอโซมอร์ฟิซึมของกราฟทั้งสองต้องรักษาการแบ่งส่วน) ^{[ 37 ]}
• กราฟ 2 สี ^{[ 37 ]}
• โครงสร้างจำกัดที่กำหนดไว้อย่างชัดเจน^{[ 37 ]}
• มัลติกราฟ^{[ 37 ]}
• ไฮเปอร์กราฟ^{[ 37 ]}
• ออโตมาตาจำกัด^{[ 37 ]}
• กระบวนการตัดสินใจแบบมาร์คอฟ^{[ 38 ]}
• เซมิกรุปแบบสลับชั้น 3 นิลโพเทนต์ (เช่นxyz = 0 สำหรับทุกองค์ประกอบx , y , z ) ^{[ 37 ]}
• พีชคณิตแบบเชื่อมโยง อันดับจำกัดเหนือฟิลด์ปิดพีชคณิตคงที่ที่มีรากกำลังสองเป็นศูนย์และปัจจัยสลับที่เหนือราก^{[ 37 ] [ 39 ]}
• ไวยากรณ์ที่ไม่ขึ้นกับบริบท^{[ 37 ]}
• เกมรูปแบบปกติ^{[ 40 ]}
• การออกแบบบล็อกที่ไม่สมบูรณ์ที่สมดุล^{[ 37 ]}
• การรับรู้ถึงไอโซมอร์ฟิซึมเชิงคอมบินาทอริกของโพลีโทปนูนที่แสดงโดยการเกิดร่วมกันของจุดยอดและหน้าตัด^{[ 41 ]}

คลาสของกราฟเรียกว่า GI-complete หากการรับรู้ไอโซมอร์ฟิซึมสำหรับกราฟจากคลาสย่อยนี้เป็นปัญหา GI-complete คลาสต่อไปนี้เป็น GI-complete: ^{[ 37 ]}

• กราฟที่เชื่อมต่อ^{[ 37 ]}
• กราฟของเส้นผ่านศูนย์กลาง 2 และรัศมี 1 ^{[ 37 ]}
• กราฟแบบไม่มีวงจรทิศทาง^{[ 37 ]}
• กราฟปกติ^{[ 37 ]}
• กราฟสองส่วนที่ ไม่มี กราฟย่อยปกติที่แข็งแกร่งที่ไม่ธรรมดา^{[ 37 ]}
• กราฟออยเลอร์แบบสองส่วน^{[ 37 ]}
• กราฟปกติแบบสองส่วน^{[ 37 ]}
• กราฟเส้น^{[ 37 ]}
• กราฟแยก^{[ 25 ]}
• กราฟคอร์ดัล^{[ 37 ]}
• กราฟเสริมตัวเองปกติ^{[ 37 ]}
• กราฟโพลีโทปของโพลีโทปนูนทั่วไป โพลีโทปนูน แบบง่ายและ โพลีโทปนูน เชิงซิมพลิเชียลในมิติใดๆ^{[ 42 ]}

กลุ่มของไดกราฟหลายประเภทก็เป็นกลุ่ม GI-complete เช่นกัน

นอกจากปัญหาไอโซมอร์ฟิซึมแล้ว ยังมีปัญหา GI-complete ที่ซับซ้อนอื่นๆ อีก

• การค้นหากลุ่มออโตมอร์ฟิซึมของกราฟ^{[ 18 ]}
• การนับออโตมอร์ฟิซึมของกราฟ^{[ 18 ]}
• การรับรู้ถึงความสมบูรณ์ในตัวเองของกราฟหรือไดกราฟ^{[ 43 ]}
• ปัญหาคลิกสำหรับคลาสของสิ่งที่เรียกว่าM-กราฟ แสดงให้เห็นว่าการหาไอโซมอร์ฟิซึมสำหรับ กราฟ nจุดยอดเทียบเท่ากับการหา คลิก nจุดในM-กราฟขนาดn ²ข้อเท็จจริงนี้น่าสนใจเพราะปัญหาการหาคลิกอันดับ (1 −  ε ) nในM-กราฟขนาดn ²เป็นปัญหา NP-complete สำหรับ ε บวกที่เล็กมาก^{[ 44 ]}
• ปัญหาของโฮมีโอเมอร์ฟิซึมของคอมเพล็กซ์ 2 ตัว^{[ 45 ]}
• ปัญหาความสามารถในการกำหนดสำหรับตรรกะลำดับแรกอินพุตของปัญหานี้คืออินสแตนซ์ฐานข้อมูลเชิงสัมพันธ์Iและความสัมพันธ์Rและคำถามที่ต้องตอบคือมีการสอบถามลำดับแรกQ (โดยไม่มีค่าคงที่) อยู่หรือไม่ ซึ่งQที่ประเมินบนIจะให้ R เป็นคำตอบ^{[ 46 ]}

• ปัญหาของการนับจำนวนไอโซมอร์ฟิซึมระหว่างกราฟสองกราฟนั้นเทียบเท่ากับปัญหาของการบอกว่ามีอยู่จริงหรือไม่ในเวลาพหุนาม^{[ 47 ]}
• ปัญหาในการตัดสินใจว่าโพลีโทปนูน สองอัน ที่กำหนดโดยคำอธิบาย Vหรือคำอธิบาย Hนั้นเป็นไอโซมอร์ฟิกเชิงโปรเจกทีฟหรือเชิงแอฟฟินหรือไม่ อย่างหลังหมายถึงการมีอยู่ของแผนที่เชิงโปรเจกทีฟหรือเชิงแอฟฟินระหว่างพื้นที่ที่บรรจุโพลีโทปทั้งสอง (ไม่จำเป็นต้องมีมิติเดียวกัน) ซึ่งเหนี่ยวนำให้เกิดการจับคู่แบบหนึ่งต่อหนึ่งระหว่างโพลีโทป^{[ 42 ]}

Manuel Blumและ Sampath Kannan ( 1995 ) ได้แสดงตัวตรวจสอบความน่าจะเป็นสำหรับโปรแกรมสำหรับการหาความเหมือนกันของกราฟ สมมติว่าPเป็นขั้นตอนที่อ้างว่าใช้เวลาพหุนามในการตรวจสอบว่ากราฟสองกราฟเหมือนกันหรือไม่ แต่ขั้นตอนดังกล่าวไม่ได้รับความไว้วางใจ ในการตรวจสอบว่ากราฟGและHเหมือนกันหรือไม่:

• ถามPว่าGและHเป็นไอโซมอร์ฟิกหรือไม่
  • ถ้าคำตอบคือ "ใช่":
    • พยายามสร้างกราฟที่สมมาตรกันโดยใช้Pเป็นซับรูทีน กำหนดจุดยอดuในGและvในHแล้วแก้ไขกราฟเพื่อให้แตกต่างกัน (ด้วยการเปลี่ยนแปลงเล็กน้อยในระดับท้องถิ่น) ถามPว่ากราฟที่แก้ไขแล้วสมมาตรกันหรือไม่ ถ้าไม่ใช่ ให้เปลี่ยนvเป็นจุดยอดอื่น แล้วค้นหาต่อไป
    • จะพบความเหมือนกัน (และสามารถตรวจสอบได้) หรือไม่ก็Pจะขัดแย้งกับตัวเอง
  • ถ้าคำตอบคือ "ไม่":
    • ทำซ้ำขั้นตอนต่อไปนี้ 100 ครั้ง เลือกกราฟGหรือH แบบสุ่ม และสลับตำแหน่งจุดยอดของกราฟแบบสุ่ม ถามPว่ากราฟที่ได้นั้นเป็นกราฟสมมาตรกับGและHหรือไม่ (เช่นเดียวกับใน โปรโตคอล AMสำหรับการตรวจสอบว่ากราฟไม่เป็นสมมาตรกัน)
    • หากการทดสอบใดๆ ล้มเหลว ให้ตัดสิน ว่าโปรแกรม Pไม่ถูกต้อง มิเช่นนั้น ให้ตอบว่า "ไม่"

กระบวนการนี้ใช้เวลาในการประมวลผลแบบพหุนาม และจะให้คำตอบที่ถูกต้องหากPเป็นโปรแกรมที่ถูกต้องสำหรับการหาความเหมือนกันของกราฟ หากPไม่ใช่โปรแกรมที่ถูกต้อง แต่ตอบคำถามGและH ได้ถูกต้อง ตัวตรวจสอบจะให้คำตอบที่ถูกต้อง หรือตรวจพบพฤติกรรมที่ไม่ถูกต้องของPหากPไม่ใช่โปรแกรมที่ถูกต้อง และตอบคำถามGและH ได้ไม่ถูกต้อง ตัวตรวจสอบจะตรวจพบพฤติกรรมที่ไม่ถูกต้องของPด้วยความน่าจะเป็นสูง หรือตอบผิดด้วยความน่าจะเป็น2 ⁻¹⁰⁰

ที่น่าสังเกตคือPถูกใช้เป็นเพียงกล่องดำเท่านั้น

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

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

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

ในการออกแบบอัตโนมัติทางอิเล็กทรอนิกส์กราฟไอโซมอร์ฟิซึมเป็นพื้นฐานของ ขั้นตอนการออกแบบวงจร Layout Versus Schematic (LVS) ซึ่งเป็นการตรวจสอบว่าวงจรไฟฟ้าที่แสดงโดยแผนผังวงจรและเลย์เอาต์วงจรรวมเหมือนกันหรือไม่^{[ 52 ]}

• ปัญหาการแปลงกราฟอัตโนมัติ
• การกำหนดมาตรฐานกราฟ