จั่น
ข้อสอบ CT203 – Bipartite Graph เรื่องกราฟ(ปี 2008)
แสดงความเห็นโดย จั่น บน กรกฎาคม 17, 2008
จากรูปเป็น Bipartite Graph หรือไม่
คำตอบ ต้องทำการวาดรูปโดยนึกว่าต้องพยายามทำให้เป็น bipartite graph ก่อน (เริ่มจากจุด a แล้วลากเส้นทาง Edge ไปให้ครบทุกด้าน จะได้ดังรูปด้านล่าง)
เขียนอธิบาย กราฟนี้ G ประกอบด้วยจุดยอด V และด้าน E
G(V,E) โดยที่จุดยอด V ประกอบด้วย
V = {V1, V2}
เซตจุดยอด V1 = {a, b, d, e} และจุดยอด V2 = {f, c}
ส่วนด้าน E = {af, ac, bf, bc, ef, ec, df, dc}
จะเห็นว่าจุดยอด V1 และ จุดยอด V2 เป็นเซตต่างสมาชิกกัน ดังนั้นกราฟนี้จึงเป็น Bipartite Graph
