การแก้ปัญหาของออยเลอร์

อยเลอร์ เสนอวิธีการแก้ปัญหานี้โดยการแทนพื้นดิน แต่ละแห่งเป็นจุดซึ่งเรียกว่า จุดเชื่อมโยง (Vertices) และเรียกสะพานซึ่งเป็นการเชื่อมระหว่างจุดเหล่านี้ว่า เส้นเชื่อมโยงระหว่างจุด (arcs) ดังนั้นสะพานเคอนิกส์เบอร์กจึงเขียนแทนด้วยเส้นข้ามสะพานระหว่าง Vertices กับ arcs

เมื่อเขียนเส้นเชื่อมระหว่างจุด ปัญหาสะพานทั้งเจ็ด มีลักษณะเป็นกราฟ ดังรูป

ปัญหานี้จึงอยู่ที่การลากเส้นด้วยดินสอโดยการเขียนเส้นโดยไม่ต้องยกดินสอออกจากกระดาษ โดยแต่ละเส้นที่เชื่อมระหว่างจุดจะมีการลากผ่านเพียงครั้งเดียว

สังเกตว่ามีจุด 4 จุด และมีด้าน (arc) อยู่ทั้งหมดเป็นเลขคี่ (ในนี้มี 7 arcs) เริ่มจากจุดใดจุดหนึ่งแล้วลากตามเส้น เพื่อให้ผ่านเส้นครั้งเดียว ลองทดลองดูจะเห็นว่าไม่สามารถทำได้

ทฤษฎีกราฟของออยเลอร์


ที่มา : รศ. ยืน ภู่วรวรรณ, สำนักบริการคอมพิวเตอร์ มหาวิทยาลัยเกษตรศาสตร์