BIPARTITE GRAPHS
..........คือกราฟที่มีสมบัติว่าสามารถแบ่งเซตของจุดออกเป็น 2 เซ็ตย่อย โดยที่เซ็ตย่อยนั้นจะมีเส้นที่เชื่อมระหว่างจุด ในอีกเซ็ตย่อยหนึ่ง แต่ต้องไม่มีเส้นเชื่อมจุดใน เซ็ตย่อย เดียวกัน ตัวอย่าง กราฟที่แสดงการแต่งงานระหว่างคนในหมู่บ้าน,แต่ละคนจะถูกแทนด้วยจุด และการแต่งงานถูกแทน ด้วยเส้นที่เชื่อมในกราฟนี้ subset หนึ่งจะถูกแทนด้วยฝ่ายชาย และ อีกsubset จะถูกแทนด้วยฝ่ายหญิง นิยามที่5 กราฟอย่างง่าย G จะเป็น bipartite graph ถ้า เซตของจุด V สามารถแบ่งได้เป็น 2 เซต ชื่อว่า V1 และ V2 โดยที่ V1? { } และ V2 ? { } และสองจุดใดๆในV1 ต้องไม่มีเส้นเชื่อม และในสองจุดใดๆ ใน V2 ต้องไม่มีเส้นเชื่อมด้วย ..........ในตัวอย่างที่ 8 เราจะเห็นกราฟ C6 เป็น bipartite graph และ กราฟ K3 ในตัวอย่างที่ 9 ไม่เป็น bipartite graph ตัวอย่างที่8 C6 เป็น bipartite graph,เช่นที่แสดงใน รูปที่ 7 สามารถแบ่งได้เป็นสองเซตคือ V1 = {v1, v3, v5} และ V2 = {v2, v4, v6} และทุกๆเส้นที่ติดต่อใน C6 จะติดต่อกับทุกๆจุดใน V1 และ V2
รูปที่ 7 แสดง C6 เป็น bipartite graph
 ตัวอย่างที่9 กราฟรูป K3 ไม่ใช่ bipartite graph เพราะถ้าเราแบ่งเซตของจุดของ K3 เป็นสองเซต หนึ่งในสอง เซตนั้นต้องประกอบด้วยจุดสองจุด.ถ้าเป็น bipartite graph , สองจุดนั้นต้องติดต่อถึงกัน,แต่ใน K3 ทุกๆจุดจะมี เส้นเชื่อมติดต่อกัน ตัวอย่างที่10 พิจารณากราฟ G และ H ใน Figure 8 เป็น bipartite graph หรือไม่?

Figure 8 Undirected Graphs G และ H

 วิธีทำ : กราฟ G เป็น bipartite graph เพราะสามารถแบ่งเซตของจุดเป็นสองเส้นคือ V1 ={a,b,d} และ V2 ={c,e,f,g}, โดยที่แต่ละจุดใน V1 ไม่มีเส้นเชื่อม และใน V2 ก็ไม่มีเส้นเชื่อมเช่นเดียวกัน (กราฟ G เป็น bipartite graph ไม่จำเป็นต้องทุกๆจุดใน {a,b,d}ต้องอยู่ติดกับทุกๆจุดใน{c,e,f,g} ตัวอย่าง, b และ g ไม่ได้อยู่ติดกัน) กราฟ H ไม่ใช่ bipartite graph เพราะเซตของจุดไม่สามารถแบ่งได้เป็น 2 เซตย่อย โดยที่แต่ละเซตย่อย 2 จุดใดๆในเซตย่อยนั้นไม่มีเส้นเชื่อม ดังนั้น จะไม่สามารถติดต่อจุดสองจุดจาก subset ที่เหมือนกัน (ผู้อ่านควร พิสูจน์โดยพิจารณาจากจุด a,b,f) ตัวอย่างที่11 Complete Bipartite Graphs: complete bipartite graph Km,n เป็นกราฟที่ เซตของจุดถูก แบ่งได้เป็น 2 subset ที่มี m และ n จุด,ตามลำดับโดยที่มีเส้นเชื่อมระหว่างสองจุดใดๆในแต่ละเซตย่อย จุดหนึ่ง จุดใน เซตย่อย แรกและจุดอื่นๆใน เซตย่อย ที่สอง.เช่น complete bipartite graphs K2,3 , K3,3 , K3,5, และ K2,6 ใน Figure 9

Figure 9 บาง complete bipartite graphs
| Home | Introduction | Simple Graph | Bipartite Graph | Applications Graph | Subgraph | Exercises | Links |