สะพานทั้งเจ็ดแห่งเมืองเคอนิชส์แบร์ค

แผนที่ของเมืองเคอนิกส์แบร์กในสมัยออยเลอร์ แสดงให้เห็นสะพานทั้งเจ็ด

สะพานทั้งเจ็ดแห่งเมืองเคอนิกส์แบร์ก (Seven Bridges of Königsberg) หรือ สะพานทั้งเจ็ดแห่งเมืองโคนิกส์เบิร์ก เป็นปัญหาที่ได้รับแรงบันดาลใจมาจากสถานที่ คือ เมืองเคอนิกส์แบร์ก ในปรัสเซีย (ปัจจุบันคือ Kaliningrad ในรัสเซีย) ซึ่งตั้งอยู่บนแม่น้ำ Pregel และมีเกาะอยู่ 2 เกาะเชื่อมต่อถึงกันด้วยสะพานทั้ง 7 สะพาน คำถามคือ เป็นไปได้หรือไม่ที่จะเดินให้ครบทุกสะพาน โดยผ่านแต่ละสะพานเพียงครั้งเดียวและกลับมาที่จุดเริ่มต้นได้ ในพ.ศ. 2279 (ค.ศ. 1736) เลออนฮาร์ด ออยเลอร์ ได้พิสูจน์ว่าไม่มีทางเป็นไปได้

คำตอบของออยเลอร์

ในการพิสูจน์นั้น ออยเลอร์ได้แปลงปัญหานี้ให้อยู่ในรูปทฤษฎีกราฟ โดยแทนที่ดินด้วยจุด ที่เรียกว่า จุดยอด (vertex) และแทนสะพานด้วยเส้น ที่เรียกว่า เส้นเชื่อม (edge)

→ →

ทฤษฎีกราฟเป็นสาขาหนึ่งของทอพอโลยี ซึ่งจะไม่สนใจรูปร่างของกราฟว่าเป็นอย่างไร นั่นคือเส้นที่เชื่อมระหว่างจุดยอดต่างๆจะเป็นเส้นตรงหรือเส้นโค้งก็ได้ แต่มันยังคงต้องเชื่อมจุดยอดนั้นอยู่ไม่เปลี่ยนแปลง

ออยเลอร์ได้แสดงให้เห็นว่า เราจะเดินผ่านเส้นเชื่อมทุกเส้นในกราฟเพียงครั้งเดียวและกลับมาที่จุดเริ่มต้นได้ ก็ต่อเมื่อ กราฟนั้นไม่มีจุดยอดที่มีจำนวนเส้นเชื่อมมาเชื่อมจุดยอดนั้นเป็นจำนวนคี่ ซึ่งแนวเดินนี้จะเรียกว่า วงจรออยเลอร์ (Eulerian circuit) ดังนั้น กราฟของสะพานทั้งเจ็ดจึงไม่มีทางทำได้

แต่ถ้าเราไม่สนใจว่าต้องเดินกลับมาที่จุดเริ่มต้น เราจะหาแนวเดินนั้นได้ ก็ต่อเมื่อ กราฟนั้นไม่มีจุดยอดที่มีจำนวนเส้นเชื่อมมาเชื่อมจุดยอดนั้นเป็นจำนวนคี่ หรือกราฟนั้นอาจมีจุดยอดดังกล่าวอยู่ 2 จุด ซึ่งแนวเดินนี้จะเรียกว่า รอยเดินออยเลอร์ (Eulerian trail) ดังนั้น กราฟของสะพานทั้งเจ็ดจึงทำไม่ได้เช่นเดียวกัน

ความสำคัญในประวัติศาสตร์ของคณิตศาสตร์

ในประวัติศาสตร์ของคณิตศาสตร์ ปัญหานี้เป็นปัญหาแรกในทฤษฎีกราฟ และทฤษฎีกราฟนั้นเป็นส่วนหนึ่งของทอพอโลยี ซึ่งเป็นปัญหาแรกในทอพอโลยีด้วย

ดัดแปลงปัญหา

สะพานที่ 8 ของเจ้าชายน้ำเงิน

เจ้าชายน้ำเงิน ได้วางแผนสร้างสะพานขึ้นมาสะพานหนึ่ง เพื่อให้เขาสามารถเริ่มเดินจากปราสาทสีน้ำเงินในตอนหัวค่ำโดยผ่านแต่ละสะพานหนึ่งครั้ง และไปจบที่เกาะกลางเพื่อดื่มเบียร์ฉลองชัยชนะ แน่นอนว่าเขาไม่ต้องการให้เจ้าชายสีแดงใช้สะพานนี้เพื่อจุดประสงค์เดียวกันกับเขา เจ้าชายน้ำเงินจะสร้างสะพานที่ 8 ที่ไหนดี?

สะพานที่ 9 ของเจ้าชายสีแดง

เจ้าชายแดงต้องการล้างแค้นเจ้าชายสีน้ำเงิน โดยการสร้างสะพานหนึ่งสะพานที่จะทำให้เขาเดินผ่านมันได้ทั้งหมดโดยไปจบที่เกาะกลาง และนอกจากนั้นเขายังต้องการกันไม่ให้เจ้าชายน้ำเงินทำได้อย่างที่เขาต้องการตอนสร้างสะพานที่ 8 เจ้าชายแดงจะสร้างสะพานที่ 9 ที่ไหนดี?

สะพานที่ 10 ของบาทหลวง

บาทหลวงอนาถใจกับความเหลวไหลของเจ้าชายทั้งสอง จึงต้องการสร้างสะพานที่ 10 เพื่อให้เจ้าชายทั้งสองกลับบ้านนอนแทนที่จะมาดื่มเหล้าเมามาย บาทหลวงจะสร้างสะพานที่ 10 ที่ไหนดี?

เฉลยปัญหาดัดแปลง

สะพานที่ 8 ของเจ้าชายน้ำเงิน

สร้างที่เกาะศาสนาเชื่อมกับปราสาทแดง

สะพานที่ 9 ของเจ้าชายแดง

สร้างระหว่างสองปราสาท

สะพานที่ 10 ของบาทหลวง

สร้างระหว่างเกาะกลางกับปราสาทแดง

ดูเพิ่ม

• ทฤษฎีกราฟ
• กราฟ (คณิตศาสตร์)