ปัญหาสะพานทั้งเจ็ดแห่งเมืองโคนิกส์เบิร์ก
จากวิกิพีเดีย สารานุกรมเสรี
ปัญหาสะพานทั้งเจ็ดแห่งเมืองโคนิกส์เบิร์ก (Seven Bridges of Königsberg) เป็นปัญหาที่ได้รับแรงบันดาลใจมาจากสถานที่ คือ เมืองโคนิกส์เบิร์ก ในปรัสเซีย (ปัจจุบันคือ Kaliningrad ในรัสเซีย) ซึ่งตั้งอยู่บนแม่น้ำ Pregel และมีเกาะอยู่ 2 เกาะเชื่อมต่อถึงกันด้วยสะพานทั้ง 7 สะพาน คำถามคือ เป็นไปได้หรือไม่ที่จะเดินให้ครบทุกสะพาน โดยผ่านแต่ละสะพานเพียงครั้งเดียวและกลับมาที่จุดเริ่มต้นได้ ในพ.ศ. 2279 (ค.ศ. 1736) เลออนฮาร์ด ออยเลอร์ ได้พิสูจน์ว่าไม่มีทางเป็นไปได้
สารบัญ |
[แก้] คำตอบของออยเลอร์
ในการพิสูจน์นั้น ออยเลอร์ได้แปลงปัญหานี้ให้อยู่ในรูปทฤษฎีกราฟ โดยแทนที่ดินด้วยจุด ที่เรียกว่า จุดยอด (vertex) และแทนสะพานด้วยเส้น ที่เรียกว่า เส้นเชื่อม (edge)
ทฤษฎีกราฟเป็นสาขาหนึ่งของทอพอโลยี ซึ่งจะไม่สนใจรูปร่างของกราฟว่าเป็นอย่างไร นั่นคือเส้นที่เชื่อมระหว่างจุดยอดต่างๆจะเป็นเส้นตรงหรือเส้นโค้งก็ได้ แต่มันยังคงต้องเชื่อมจุดยอดนั้นอยู่ไม่เปลี่ยนแปลง
ออยเลอร์ได้แสดงให้เห็นว่า เราจะเดินผ่านเส้นเชื่อมทุกเส้นในกราฟเพียงครั้งเดียวและกลับมาที่จุดเริ่มต้นได้ ก็ต่อเมื่อ กราฟนั้นไม่มีจุดยอดที่มีจำนวนเส้นเชื่อมมาเชื่อมจุดยอดนั้นเป็นจำนวนคี่ ซึ่งแนวเดินนี้จะเรียกว่า วงจรออยเลอร์ (Eulerian circuit) ดังนั้น กราฟของสะพานทั้งเจ็ดจึงไม่มีทางทำได้
แต่ถ้าเราไม่สนใจว่าต้องเดินกลับมาที่จุดเริ่มต้น เราจะหาแนวเดินนั้นได้ ก็ต่อเมื่อ กราฟนั้นไม่มีจุดยอดที่มีจำนวนเส้นเชื่อมมาเชื่อมจุดยอดนั้นเป็นจำนวนคี่ หรือกราฟนั้นอาจมีจุดยอดดังกล่าวอยู่ 2 จุด ซึ่งแนวเดินนี้จะเรียกว่า รอยเดินออยเลอร์ (Eulerian trail) ดังนั้น กราฟของสะพานทั้งเจ็ดจึงทำไม่ได้เช่นเดียวกัน
[แก้] ความสำคัญในประวัติศาสตร์ของคณิตศาสตร์
ในประวัติศาสตร์ของคณิตศาสตร์ ปัญหานี้เป็นปัญหาแรกในทฤษฎีกราฟ และทฤษฎีกราฟนั้นเป็นส่วนหนึ่งของทอพอโลยี ซึ่งเป็นปัญหาแรกในทอพอโลยีด้วย
[แก้] ดัดแปลงปัญหา
[แก้] สะพานที่ 8 ของเจ้าชายน้ำเงิน
เจ้าชายน้ำเงิน ต้องการสร้างสะพานขึ้นมาสะพานหนึ่ง เพื่อให้เขาสามารถเดินครบทุกสะพาน โดยผ่านแต่ละสะพานครั้งเดียว และไปสิ้นสุดที่เกาะกลางได้
- เจ้าชายน้ำเงินจะสร้างสะพานที่ 8 ที่ไหนดี?
สร้างที่เกาะศาสนาเชื่อมกับปราสาทแดง
[แก้] ดูเพิ่ม
![]() |
ปัญหาสะพานทั้งเจ็ดแห่งเมืองโคนิกส์เบิร์ก เป็นบทความเกี่ยวกับ คณิตศาสตร์ ที่ยังไม่สมบูรณ์ ต้องการตรวจสอบ เพิ่มเนื้อหา หรือเพิ่มแหล่งอ้างอิง คุณสามารถช่วยเพิ่มเติมหรือแก้ไข เพื่อให้สมบูรณ์มากขึ้น ข้อมูลเกี่ยวกับ ปัญหาสะพานทั้งเจ็ดแห่งเมืองโคนิกส์เบิร์ก ในภาษาอื่น อาจสามารถหาอ่านได้จากเมนู ภาษาอื่น ด้านซ้ายมือ |