กราฟสองฝ่ายคืออะไร - คำจำกัดความจาก techopedia

คำจำกัดความ - Bipartite Graph หมายถึงอะไร

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

กราฟสองฝ่ายเป็นที่รู้จักกันว่าเป็นกราฟขนาดใหญ่

Techopedia อธิบาย Bipartite Graph

กราฟสองฝ่ายมีจุดยอดสองชุดตัวอย่างเช่น A และ B ที่มีความเป็นไปได้ที่เมื่อมีการวาดขอบการเชื่อมต่อควรจะสามารถเชื่อมต่อระหว่างจุดสุดยอดใด ๆ ใน A กับจุดสุดยอดใด ๆ ใน B หากกราฟไม่มี วงจรคี่ (จำนวนจุดยอดในกราฟเป็นคี่) จากนั้นสเปกตรัมของมันจะสมมาตร หมายเลขรงค์ซึ่งเป็นจำนวนขั้นต่ำของสีที่ต้องใช้เพื่อจุดสีที่ไม่มีจุดยอดติดกันที่ใช้สีเดียวกันต้องน้อยกว่าหรือเท่ากับสองในกรณีของกราฟสองส่วน กราฟ acyclic ทุกชนิด (กราฟที่ไม่มีรอบกราฟ) เป็นตัวอย่างของกราฟ bipartite กราฟวงกลมถือเป็นสองฝ่ายถ้าวัฏจักรที่เกี่ยวข้องทั้งหมดมีความยาวเท่ากัน ตามทฤษฎีบทการระบายสีเส้นของ Koning กราฟสองฝ่ายทั้งหมดเป็นกราฟคลาส 1

กราฟสองส่วนใช้กันอย่างแพร่หลายในทฤษฎีการเข้ารหัสสมัยใหม่นอกเหนือจากการใช้ในการสร้างแบบจำลองความสัมพันธ์