รูปแสดงเซต U และเซต V ที่มีเส้นเชื่อมระหว่างจุดยอดด้วยกัน
กราฟทวิภาค ในทางคณิตศาสตร์ สาขาทฤษฎีกราฟ,กราฟทวิภาค (bipartite graph,bigraph) เป็นกราฟที่มีจุดยอดที่ซึ่งสามารถแบ่งในสองเซตที่ไม่มีสมาชิกร่วมกับกับเซตใดๆ โดยที่เซต U และเซต V จะมีเส้นที่เชื่อมระหว่างจุดยอด ในอีกเซตนึง แต่ต้องไม่มีเส้นเชื่อมจุดยอดในเซตเดียวกัน ดังนั้น U และ V จึงเป็นเซตอิสระ นั้นเท่ากับว่ากราฟทวิภาคนั้นจะไม่มีวงจรที่มีความยาวเป็นเลขคี่โดยเด็ดขาด
เซต U และเซต V นั้นจะมีสีของแต่ละเซต เช่นให้ทุกจุดยอดของเซต U เป็นสีฟ้า และทุกจุดยอดของเซต V เป็นสีเขียว และทุกเส้นที่เชื่อมจะเชื่อมไปยังจุดยอดที่สีต่างกันเสมอ หากไม่เชื่อมไปยังจุดยอดที่สีต่างกันจะไม่ถือว่าเป็นกราฟทวิภาค
กราฟทวิภาคเรียกว่ากราฟคู่ด้วยก็ได้ เป็นกราฟที่ 2 จุดแยกเป็น 2 เซ็ทที่ทั้ง 2 กราฟไม่ติดกัน กราฟทวิภาคนั้นเป็นกรณีพิเศษของ k-bipartite graph ด้วย k = 2 กราฟทวิภาคนั้นมีค่าเท่ากับกราฟสองสี และกราฟเป็นทวิภาคที่มีเงื่อนไขและเท่านั้นเป็นวงจรของ ความเท่ากันของความยาว กราฟทวิภาคสองสีสามารถพบด้วยการใช้สองสีทางคณิตศาสตร์
ตัวอย่าง[]
- ไม่ว่ากราฟใดๆที่ไม่มีวงจรคี่ จะได้ผลดังนี้
- ทุกๆต้นไม้จะแบ่งออกเป็นสองส่วน
- กราฟวงจรที่มีจำนวนจุดเป็นคู่จะเป็นทวิภาค
การประยุกต์ใช้[]
กราฟทวิภาคนั้นใช้สำหรับ การเอาปัญหามาเข้ากัน ตัวอย่างเช่นงานการหาความเข้ากันของปัญหา สมมุติว่าเรามีเซตของประชาชน(ในที่นี้คือเซตP)และเซ็ตJ ของงาน ด้วยความที่ประชาชนทั้งหมดไม่ได้เหมาะสมแค่งานนี้ เราสามารถจำลองกราฟทวิภาค(P,J,E) ถ้าผู้คนPxเหมาะสำหรับงาน Jy มันคือขอบเขตระหว่าง Px กับ Jy ในกราฟ ทฤษฎี marriage ได้จัดให้ ลักษณะเฉพาะ ของ กราฟทวิภาคนี้เป็นการเข้ากันได้แบบสมบูรณ์
กราฟทวิภาคนั้นมีการใช้อย่างกว้างขวางในทฤษฎีการถอดรหัสสมัยใหม่ โดยเฉพาะอย่างยิ่งการแกะรหัสคำที่ได้รับจากช่องทาง Factor graphs และ Tanner graphs คือตัวอย่างดังต่อไปนี้
ในวิทยาศาสตร์คอมพิวเตอร์ Petri net คือ เครื่องมือสร้างสมมุติฐานทางคณิตศาสตร์ ใช้ในการวิเคราะห์และจำลองของระบบที่เกิดขึ้นพร้อมกัน ระบบเป็นตัวสมมุติเหมือนกับ bipartite directed graph ด้วย 2 เซ็ตของnodes เซ็ตของnodes"สถานที่"นั้นเก็บทรัพยากร และเซ็ตของnodes"เหตุการณ์"สิ่งที่ทำให้เกิดและหรือใช้ทรัพยากร นั่นคือข้อจำกัดที่เพิ่มขึ้นบนnodesและedgesนั้น
Petri nets ใช้ประโยชน์คุณสมบัติของ bipartite directed graphs และ คุณสมบัติอื่นๆที่ยอมรับทางคณิตศาสตร์ พิสูจน์โดยพฤติกรรมของระบบระหว่างเช่นเดียวกับการอนุญาติให้ลงมือทำ เพื่อให้งานประสบความสำเร็จอย่างง่ายดายของการจำลองของระบบ
ในการฉายภาพเรขาคณิต Levi graphs คือรูปแบบของกราฟทวิภาค ถูกใช้เป็นโมเดลของอัตราการเกิดระหว่างจุดและเส้นในองค์ประกอบ
คุณสมบัติ[]
- กราฟนี้แบ่งออกเป็น๒ส่วน ก็ต่อเมื่อ มันไม่ได้ประกอบด้วย odd cycle เพราะฉะนั้น กราฟที่เป็น 2 ส่วนนี้ ไม่สามารถมีกลุ่ม ของขนาด 3 อัน หรือ มากกว่านั้น
- กราฟนี้แบ่งออกเป็น 2 ส่วน ก็ต่อเมื่อเป็น 2 สี (ตัวอย่าง มันคือเลขที่เกี่ยวกับสี ที่น้อยกว่าหรือเท่ากับ 2)
- ขนาดของจุดสุดยอดที่น้อยที่สุดนั้นเท่ากับขนาดของการเข้ากันที่มากที่สุด
- ขนาดของเซ็ตที่สมาชิกไม่ซ้ำกันที่มากที่สุดบวกกับขนาดของการเข้ากันที่มากที่สุด
- สำหรับกราฟ 2 ส่วน ขนาดของขอบที่น้อยที่สุดจะเท่ากับขนาดของเซ็ตที่สมาชิกไม่ซ้ำกันที่มากที่สุด
- สำหรับกราฟ 2 ส่วนที่เชื่อมต่อกัน ขนาดของขอบที่น้อยที่สุดบวกกับขนาดของจุดยอดที่น้อยที่สุด จะเท่ากับหมายเลข ของจุดยอดหลายๆอัน
- ทุกๆกราฟ 2 ส่วนคือกราฟที่สมบูรณ์แบบ
- แถบสีหลายหลากสีของกราฟนั้นสมมาตรกันก็ต่อเมื่อเป็นกราฟ 2 ส่วนเท่านั้น
กราฟทวิภาคสมบูรณ์[]
ตัวอย่าง K(3,2) K(2,5)
กราฟทวิภาคสมบูรณ์คือกราฟทวิภาคที่ซึ่งทุกๆคู่ของกราฟ จุดยอดในทั้งสองเซ็ตนั้นเชื่อมกัน ถ้านั่นคือจุดยอดของกราฟ p และ q ในจุดยอดของทั้งสองเซ็ต 2 เซต, กราฟทวิภาคสมบูรณ์ (หรือบางทีก็เรียกว่า กราฟคู่สมบูรณ์) ที่แสดงจำนวนจุดยอด K_(p,q) จากตัวอย่างจะแสดงให้เห็นว่า K_(3,2) และ K_(2,5) K_(3,3) ก็เป็นที่รู้จักโดยทั่วไปได้เช่นกับ utility graph และมันคือ unique 4-cage graph
แหล่งข้อมูลภายนอก[]
http://en.wikipedia.org/wiki/Bipartite_graph