ใน สาขา คณิตศาสตร์ของทฤษฎีกราฟส่วนเติมเต็มหรือส่วนกลับของกราฟGคือกราฟH บน จุดยอดเดียวกันโดยที่จุดยอดสองจุดที่แตกต่างกันจะอยู่ติดกัน (เชื่อมต่อกัน) ในH ก็ต่อเมื่อ จุดยอดทั้งสองนั้น ไม่อยู่ติดกันในG กล่าวคือ ในการสร้างส่วนเติมเต็มของกราฟ จะต้องเติม ขอบที่ขาดหายไปทั้งหมดที่จำเป็นในการสร้างกราฟสมบูรณ์และลบขอบทั้งหมดที่มีอยู่ก่อนหน้านี้^{[ 1 ]}

ส่วนเติมเต็มของกราฟไม่ใช่ส่วนเติมเต็มเซตของกราฟ: มีเพียงขอบเท่านั้นที่เป็นส่วนเติมเต็ม

ให้G = ( V , E )เป็น กราฟแบบไม่มีทิศทาง ^{อย่าง}ง่ายและให้Pประกอบด้วยคู่ของจุดยอดที่แตกต่างกันทั้งหมดในV จากนั้น กราฟแบบไม่มีทิศทาง อย่าง ง่ายH = ( V , P \ E )เป็นส่วนเติมเต็มของG [ ^{2 ]}โดยที่P \ Eเป็นส่วนเติมเต็มสัมพัทธ์ของEในP

ให้G = ( V , A )เป็นกราฟทิศทางแบบง่ายและให้Oประกอบด้วยคู่ลำดับของจุดยอดที่แตกต่างกันทั้งหมดในVแล้ว กราฟทิศทางแบบง่ายH = ( V , O \ A )คือกราฟส่วนเติมเต็มของ G

ให้Gเป็นกราฟแบบง่ายที่ไม่มีทิศทาง/มีทิศทาง ให้Kเป็น กราฟแบบง่ายที่ สมบูรณ์ที่ไม่มีทิศทาง/มีทิศทาง ซึ่งมีจำนวนจุดยอดเท่ากัน (กล่าวคือ ค่าทุกค่าเป็น 1 ยกเว้นค่าในแนวทแยงมุมที่เป็น 0) ให้และเป็นเมทริกซ์ประชิดของGและK ตามลำดับ แล้วเมทริกซ์ประชิดของส่วนเติมเต็มHของGคือ: ${\displaystyle \mathbb {A} (G)}$${\displaystyle \mathbb {A} (K)}$${\displaystyle \mathbb {A} (H)=\mathbb {A} (K)-\mathbb {A} (G)}$

ส่วนเติมเต็มไม่ได้ถูกกำหนดไว้สำหรับมัลติกราฟ

สำหรับกราฟที่อนุญาตให้มีวงวนในตัวเอง (แต่ไม่อนุญาตให้มีการเชื่อมต่อหลายจุด) กราฟส่วนเติมเต็มของกราฟGอาจถูกกำหนดโดยการเพิ่มวงวนในตัวเองให้กับทุกจุดยอดที่ไม่มีวงวนในตัวเองในGลบวงวนในตัวเองออกจากทุกจุดยอดที่มีวงวนในตัวเองในGและใช้สูตรเดียวกันกับข้างต้นในส่วนอื่นๆ อย่างไรก็ตาม การดำเนินการนี้แตกต่างจากการดำเนินการสำหรับกราฟแบบง่าย เนื่องจากหากนำไปใช้กับกราฟที่ไม่มีวงวนในตัวเอง จะได้กราฟที่มีวงวนในตัวเองบนทุกจุดยอด

แนวคิดทางทฤษฎีกราฟหลายอย่างมีความสัมพันธ์กันผ่านส่วนเติมเต็ม:

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

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

กราฟหลายประเภทสามารถเป็นส่วนเติมเต็มในตัวเองได้ กล่าวคือ ส่วนเติมเต็มของกราฟใดๆ ในประเภทหนึ่งเหล่านี้ ก็คือกราฟอีกกราฟหนึ่งในประเภทเดียวกันนั่นเอง

• กราฟสมบูรณ์คือกราฟที่สำหรับกราฟย่อยเหนี่ยวนำทุกกราฟจำนวนสีจะเท่ากับขนาดของคลิกสูงสุด ข้อเท็จจริงที่ว่าส่วนเติมเต็มของกราฟสมบูรณ์ก็เป็นกราฟสมบูรณ์เช่นกันคือทฤษฎีบทกราฟสมบูรณ์ของLászló Lovász ^{[ 4 ]}
• โคกราฟถูกนิยามว่าเป็นกราฟที่สามารถสร้างขึ้นจากจุดยอดเดี่ยวโดยใช้ การดำเนิน การรวมและการเติมเต็มที่ไม่ทับซ้อนกัน โคกราฟเหล่านี้ก่อตัวเป็นกลุ่มกราฟที่เติมเต็มตัวเองได้ กล่าวคือ ส่วนเติมเต็มของโคกราฟใดๆ ก็คือโคกราฟอีกอันหนึ่งที่แตกต่างกัน สำหรับโคกราฟที่มีจุดยอดมากกว่าหนึ่งจุด จะมีกราฟเชื่อมต่อกันเพียงหนึ่งกราฟในแต่ละคู่ที่เติมเต็มกัน และนิยามที่เทียบเท่ากันของโคกราฟก็คือกราฟย่อยที่เหนี่ยวนำที่ เชื่อมต่อกันแต่ละกราฟ จะมีส่วนเติมเต็มที่ไม่เชื่อมต่อกัน อีกนิยามหนึ่งที่เติมเต็มตัวเองได้ก็คือ โคกราฟเป็นกราฟที่ไม่มีเส้นทางสี่จุดยอดเป็นกราฟย่อยที่เหนี่ยวนำ^{[ 5 ]}
• กราฟคลาสเสริมตัวเองอีกคลาสหนึ่งคือคลาสของกราฟแยกซึ่งเป็นกราฟที่จุดยอดสามารถแบ่งออกเป็นคลิกและเซตอิสระได้ การแบ่งแบบเดียวกันนี้ให้เซตอิสระและคลิกในกราฟเสริม^{[ 6 ]}
• กราฟเกณฑ์คือกราฟที่เกิดจากการเพิ่มจุดยอดอิสระ (จุดยอดที่ไม่มีเพื่อนบ้าน) หรือจุดยอดสากล (จุดยอดที่อยู่ติดกับจุดยอดที่เพิ่มเข้ามาก่อนหน้านี้ทั้งหมด) ซ้ำๆ การดำเนินการทั้งสองนี้เป็นส่วนเติมเต็มซึ่งกันและกัน และจะสร้างคลาสของกราฟที่เติมเต็มตัวเอง^{[ 7 ]}

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