การทำความเข้าใจกราฟแยกส่วน: คำจำกัดความและตัวอย่าง

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

ตัวอย่างเช่น กราฟที่มีสองกลุ่มที่แยกจากกัน (นั่นคือ ชุดจุดยอดที่แยกจากกันสองชุดที่เชื่อมต่อถึงกันทั้งหมด) จะเป็นกราฟแยกส่วน