ปัญหากระท่อมสามหลัง

จากวิกิพีเดีย สารานุกรมเสรี
กราฟสองส่วนบริบูรณ์ K3,3

ปัญหากระท่อมสามหลัง (อังกฤษ: Three cottage problem) เป็นปัญหาทางคณิตศาสตร์ ซึ่งปัญหามีดังนี้

มีกระท่อมสามหลัง แต่ละหลังต้องการต่อสายสำหรับน้ำประปา, ไฟฟ้า และแก๊ส จะสามารถต่อสายทั้งหมดโดยไม่ให้สายตัดกันได้หรือไม่?

คำตอบ[แก้]

โดยใช้ทฤษฎีกราฟ ปัญหาดังกล่าวสมมูลกับการสร้างกราฟสองส่วนบริบูรณ์ K3,3 ซึ่งไม่สามารถสร้างให้เส้นไม่ทับกันได้ ดังนั้นปัญหาดังกล่าวจึงไม่มีคำตอบ