สารบัญ
3 ความสัมพันธ์: กราฟสองส่วนอภิธานศัพท์ทฤษฎีกราฟปัญหากระท่อมสามหลัง
กราฟสองส่วน
ในคณิตศาสตร์สาขาทฤษฎีกราฟ กราฟสองส่วน (bipartite graph) คือ กราฟที่เซตจุดยอดสามารถแบ่งได้เป็น 2 เซตที่ไม่มีส่วนร่วมกัน และจุดยอด 2 จุดใด ๆ ในเซตเดียวกัน จะไม่มีเส้นเชื่อมเชื่อมระหว่างกัน กราฟสองส่วนมีประโยชน์ในการแก้ปัญหาการจับคู่ (matching problems) เช่น ปัญหาการจัดงาน สมมติว่ามีคนอยู่ P คน และมีงานอยู่ J งาน ซึ่งแต่ละคนจะทำงานได้บางงานเท่านั้น เราจะแทนปัญหานี้ด้วยกราฟที่มีจุดยอด P + J จุด ถ้า p_i สามารถทำงาน j_i ได้ เราจะแทนด้วยเส้นเชื่อมเชื่อมระหว่าง p_i กับ j_i ทฤษฎีบทการสมรส (marriage theorem) นั้นใช้คุณสมบัติของกราฟเรื่อง การจับคู่สมบูรณ์ (perfect matchings).
ดู กราฟสองส่วนบริบูรณ์และกราฟสองส่วน
อภิธานศัพท์ทฤษฎีกราฟ
ทฤษฎีกราฟเติบโตอย่างรวดเร็วในวงการวิจัยด้านคณิตศาสตร์ และมีคำศัพท์เฉพาะทางอยู่หลายคำ บทความนี้จะรวบรวมคำและความหมายของศัพท์ในทฤษฎีกราฟ.
ดู กราฟสองส่วนบริบูรณ์และอภิธานศัพท์ทฤษฎีกราฟ
ปัญหากระท่อมสามหลัง
กราฟสองส่วนบริบูรณ์ K3,3 ปัญหากระท่อมสามหลัง (Three cottage problem) เป็นปัญหาทางคณิตศาสตร์ ซึ่งปัญหามีดังนี้.