การทำความเข้าใจการแบ่งส่วนในทฤษฎีกราฟ

ในทฤษฎีกราฟ การแบ่งส่วนสองส่วนของกราฟคือการแบ่งจุดยอดของมันออกเป็นชุดที่ไม่ต่อเนื่องกันสองชุด (เรียกว่า ชุดพาร์ไทต์) โดยที่ขอบทั้งหมดจะเชื่อมต่อจุดยอดจากชุดพาร์ไทต์ที่ต่างกัน กล่าวอีกนัยหนึ่ง ไม่มีขอบระหว่างจุดยอดในชุดพาร์ไทต์เดียวกัน ตัวอย่างเช่น ลองพิจารณากราฟที่มีจุดยอด 4 จุด {a,b,c,d} และเราแบ่งจุดยอดที่กำหนดออกเป็นสองส่วน : {a,b} และ {ซีดี}. กราฟเป็นแบบสองฝ่ายเนื่องจากขอบทั้งหมดเชื่อมต่อจุดยอดจากส่วนต่างๆ การแบ่งแบบสองส่วนสามารถใช้เพื่อลดความซับซ้อนของอัลกอริธึมสำหรับปัญหากราฟ เช่น การข้ามกราฟ การค้นหาเส้นทางที่สั้นที่สุด และการจับคู่กราฟ