ในทฤษฎีกราฟการยุบขอบ (Edge Contraction ) คือการดำเนินการที่ลบขอบออกจากกราฟพร้อมๆ กับการรวมจุดยอดสองจุดที่เคยเชื่อมต่อกัน การยุบขอบเป็นการดำเนินการพื้นฐานในทฤษฎีของกราฟไมเนอร์การระบุจุดยอด (Vertex Identification)เป็นรูปแบบที่ยืดหยุ่นกว่าของการดำเนินการนี้

การ ดำเนินการ หดตัวของขอบเกิดขึ้นโดยสัมพันธ์กับขอบเฉพาะขอบจะถูกลบออก และจุดยอดสองจุดที่เชื่อมต่อกับขอบนั้น คือและจะถูกรวมเข้าเป็นจุดยอดใหม่โดยที่ขอบที่เชื่อมต่อกับแต่ละจุดยอดจะสอดคล้องกับขอบที่เชื่อมต่อกับ หรือโดยทั่วไปแล้ว การดำเนินการนี้อาจดำเนินการกับชุดของขอบโดยการหดตัวแต่ละขอบ (ในลำดับใดก็ได้) ^{[ 1 ]}${\displaystyle e}$${\displaystyle e}$${\displaystyle u}$${\displaystyle v}$${\displaystyle w}$${\displaystyle w}$${\displaystyle u}$${\displaystyle v}$

กราฟที่ได้บางครั้งเขียนเป็น(เปรียบเทียบกับซึ่งหมายถึงการลบขอบโดยไม่รวมจุดยอดที่เชื่อมต่อกับขอบนั้น) ${\displaystyle G/e}$${\displaystyle G\setminus e}$${\displaystyle e}$

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

ให้ G เป็นกราฟ ( หรือกราฟทิศทาง ) ที่มีขอบโดยที่ให้เป็นฟังก์ชันที่แมปทุกจุดยอดใน ไปยังตัวมันเอง และแมปไปยังจุดยอดใหม่ในกรณีอื่น ๆการยุบรวมของ จะได้กราฟใหม่โดยที่, , และสำหรับทุกจะเชื่อมต่อกับขอบ ก็ ต่อ เมื่อ ซึ่ง เป็น ขอบที่สอดคล้องกันเชื่อมต่อกับใน${\displaystyle G=(V,E)}$${\displaystyle e=(u,v)}$${\displaystyle u\neq v}$${\displaystyle f}$${\displaystyle V\setminus \{u,v\}}$${\displaystyle w}$${\displaystyle e}$${\displaystyle G'=(V',E')}$${\displaystyle V'=(V\setminus \{u,v\})\cup \{w\}}$${\displaystyle E'=E\setminus \{e\}}$${\displaystyle x\in V}$${\displaystyle x'=f(x)\in V'}$${\displaystyle e'\in E'}$${\displaystyle e\in E}$${\displaystyle x}$${\displaystyle G}$

การระบุจุดยอด (บางครั้งเรียกว่าการหดตัวของจุดยอด ) จะขจัดข้อจำกัดที่ว่าการหดตัวจะต้องเกิดขึ้นกับจุดยอดที่มีขอบร่วมกัน (ดังนั้น การหดตัวของขอบจึงเป็นกรณีพิเศษของการระบุจุดยอด) การดำเนินการนี้อาจเกิดขึ้นกับจุดยอดคู่ใดก็ได้ (หรือเซตย่อย) ในกราฟ บางครั้งขอบระหว่างจุดยอดสอง จุด ที่หดตัวจะถูกลบออก หากและเป็นจุดยอดของส่วนประกอบที่แตกต่างกันของแล้วเราสามารถสร้างกราฟใหม่ได้โดยการระบุและในเป็นจุดยอดใหม่ใน^{[ 4 ]}โดยทั่วไปแล้ว เมื่อกำหนดพาร์ติชัน ของเซตจุดยอด เราสามารถระบุจุดยอดในพาร์ติชัน ได้กราฟที่ได้เรียกว่ากราฟผลหาร ${\displaystyle v}$${\displaystyle v'}$${\displaystyle G}$${\displaystyle G'}$${\displaystyle v}$${\displaystyle v'}$${\displaystyle G}$${\displaystyle {\textbf {v}}}$${\displaystyle G'}$

การแบ่งจุดยอด (Vertex cleaving ) ซึ่งเหมือนกับการแยกจุดยอด (Vertex splitting) หมายถึงการแยกจุดยอดหนึ่งจุดออกเป็นสองจุด โดยจุดยอดใหม่ทั้งสองจะอยู่ติดกับจุดยอดเดิม นี่เป็นการดำเนินการย้อนกลับของการระบุจุดยอด (Vertex identification) แม้ว่าโดยทั่วไปแล้วสำหรับการระบุจุดยอด จุดยอดที่อยู่ติดกันของจุดยอดทั้งสองที่ระบุได้นั้นจะไม่ใช่กลุ่มเดียวกันก็ตาม

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

พิจารณากราฟสองกราฟที่ไม่ทับซ้อนกันและโดยที่ประกอบด้วยจุดยอดและและประกอบด้วยจุดยอดและสมมติว่าเราสามารถสร้างกราฟ ได้^โดยการระบุจุดยอดของและของเป็นจุดยอดของและระบุจุดยอดของและของเป็นจุดยอดของในการบิดของเมื่อเทียบกับเซตจุดยอดเราจะระบุ แทนด้วยและด้วย^{[ 5} ]${\displaystyle G_{1}}$${\displaystyle G_{2}}$${\displaystyle G_{1}}$${\displaystyle u_{1}}$${\displaystyle v_{1}}$${\displaystyle G_{2}}$${\displaystyle u_{2}}$${\displaystyle v_{2}}$${\displaystyle G}$${\displaystyle u_{1}}$${\displaystyle G_{1}}$${\displaystyle u_{2}}$${\displaystyle G_{2}}$${\displaystyle u}$${\displaystyle G}$${\displaystyle v_{1}}$${\displaystyle G_{1}}$${\displaystyle v_{2}}$${\displaystyle G_{2}}$${\displaystyle v}$${\displaystyle G}$${\displaystyle G'}$${\displaystyle G}$${\displaystyle \{u,v\}}$${\displaystyle u_{1}}$${\displaystyle v_{2}}$${\displaystyle v_{1}}$${\displaystyle u_{2}}$

เมื่อกำหนดเซตของขอบที่จำกัด^{ลำดับ}ในการดำเนินการหดตัวบนกราฟจะไม่เปลี่ยนแปลงผลลัพธ์ (จนถึงไอโซมอร์ฟิซึม) ผลลัพธ์จะลดลงเหลือเพียงการแสดงว่าไอโซมอร์ฟิกกับสำหรับขอบสองขอบของ[ ^{6 ]}${\displaystyle G/e/(f/e)}$${\displaystyle G/f/(e/f)}$${\displaystyle e,f}$${\displaystyle G}$

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

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

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

อีกตัวอย่างหนึ่งคือการรวมกลุ่มที่ดำเนินการในการจัดสรรรีจิสเตอร์การระบายสีกราฟทั่วโลกซึ่งจุดยอดจะถูกรวมเข้าด้วยกัน (ในกรณีที่ปลอดภัย) เพื่อกำจัดการดำเนินการย้ายระหว่างตัวแปรที่แตกต่างกัน

การลดจำนวนขอบ (Edge contraction) ถูกนำมาใช้ในโปรแกรมสร้างแบบจำลอง 3 มิติ (ไม่ว่าจะด้วยตนเองหรือผ่านฟีเจอร์บางอย่างของซอฟต์แวร์สร้างแบบจำลอง) เพื่อลดจำนวนจุดยอดอย่างสม่ำเสมอ ซึ่งช่วยในการสร้างแบบจำลองที่มีจำนวนโพลีกอนต่ำ

• การแบ่งย่อย (ทฤษฎีกราฟ)

• ไวส์สไตน์, เอริค ดับเบิลยู. "การหดตัวของขอบ" . แมธเวิลด์ .