ผลต่างระหว่างรุ่นของ "สะพานทั้งเจ็ดแห่งเมืองเคอนิชส์แบร์ค"
ล บอต: ลิงก์บทความคัดสรร ru:Семь мостов Кёнигсберга |
ล บอต: ลิงก์บทความคัดสรร sv:Königsbergs sju broar |
||
บรรทัด 64: | บรรทัด 64: | ||
[[pt:Sete pontes de Königsberg]] |
[[pt:Sete pontes de Königsberg]] |
||
[[ru:Семь мостов Кёнигсберга]] {{Link FA|ru}} |
[[ru:Семь мостов Кёнигсберга]] {{Link FA|ru}} |
||
[[sv:Königsbergs sju broar]] |
[[sv:Königsbergs sju broar]] {{Link FA|sv}} |
||
[[vi:Bài toán bảy cây cầu Euler]] |
[[vi:Bài toán bảy cây cầu Euler]] |
||
[[zh:柯尼斯堡七桥问题]] |
[[zh:柯尼斯堡七桥问题]] |
รุ่นแก้ไขเมื่อ 15:30, 27 ธันวาคม 2550
สะพานทั้งเจ็ดแห่งเมืองโคนิกส์เบิร์ก (Seven Bridges of Königsberg) เป็นปัญหาที่ได้รับแรงบันดาลใจมาจากสถานที่ คือ เมืองโคนิกส์เบิร์ก ในปรัสเซีย (ปัจจุบันคือ Kaliningrad ในรัสเซีย) ซึ่งตั้งอยู่บนแม่น้ำ Pregel และมีเกาะอยู่ 2 เกาะเชื่อมต่อถึงกันด้วยสะพานทั้ง 7 สะพาน คำถามคือ เป็นไปได้หรือไม่ที่จะเดินให้ครบทุกสะพาน โดยผ่านแต่ละสะพานเพียงครั้งเดียวและกลับมาที่จุดเริ่มต้นได้ ในพ.ศ. 2279 (ค.ศ. 1736) เลออนฮาร์ด ออยเลอร์ ได้พิสูจน์ว่าไม่มีทางเป็นไปได้
คำตอบของออยเลอร์
ในการพิสูจน์นั้น ออยเลอร์ได้แปลงปัญหานี้ให้อยู่ในรูปทฤษฎีกราฟ โดยแทนที่ดินด้วยจุด ที่เรียกว่า จุดยอด (vertex) และแทนสะพานด้วยเส้น ที่เรียกว่า เส้นเชื่อม (edge)
ทฤษฎีกราฟเป็นสาขาหนึ่งของทอพอโลยี ซึ่งจะไม่สนใจรูปร่างของกราฟว่าเป็นอย่างไร นั่นคือเส้นที่เชื่อมระหว่างจุดยอดต่างๆจะเป็นเส้นตรงหรือเส้นโค้งก็ได้ แต่มันยังคงต้องเชื่อมจุดยอดนั้นอยู่ไม่เปลี่ยนแปลง
ออยเลอร์ได้แสดงให้เห็นว่า เราจะเดินผ่านเส้นเชื่อมทุกเส้นในกราฟเพียงครั้งเดียวและกลับมาที่จุดเริ่มต้นได้ ก็ต่อเมื่อ กราฟนั้นไม่มีจุดยอดที่มีจำนวนเส้นเชื่อมมาเชื่อมจุดยอดนั้นเป็นจำนวนคี่ ซึ่งแนวเดินนี้จะเรียกว่า วงจรออยเลอร์ (Eulerian circuit) ดังนั้น กราฟของสะพานทั้งเจ็ดจึงไม่มีทางทำได้
แต่ถ้าเราไม่สนใจว่าต้องเดินกลับมาที่จุดเริ่มต้น เราจะหาแนวเดินนั้นได้ ก็ต่อเมื่อ กราฟนั้นไม่มีจุดยอดที่มีจำนวนเส้นเชื่อมมาเชื่อมจุดยอดนั้นเป็นจำนวนคี่ หรือกราฟนั้นอาจมีจุดยอดดังกล่าวอยู่ 2 จุด ซึ่งแนวเดินนี้จะเรียกว่า รอยเดินออยเลอร์ (Eulerian trail) ดังนั้น กราฟของสะพานทั้งเจ็ดจึงทำไม่ได้เช่นเดียวกัน
ความสำคัญในประวัติศาสตร์ของคณิตศาสตร์
ในประวัติศาสตร์ของคณิตศาสตร์ ปัญหานี้เป็นปัญหาแรกในทฤษฎีกราฟ และทฤษฎีกราฟนั้นเป็นส่วนหนึ่งของทอพอโลยี ซึ่งเป็นปัญหาแรกในทอพอโลยีด้วย
ดัดแปลงปัญหา
สะพานที่ 8 ของเจ้าชายน้ำเงิน
เจ้าชายน้ำเงิน ต้องการสร้างสะพานขึ้นมาสะพานหนึ่ง เพื่อให้เขาสามารถเดินครบทุกสะพาน โดยผ่านแต่ละสะพานครั้งเดียว และไปสิ้นสุดที่เกาะกลางได้
- เจ้าชายน้ำเงินจะสร้างสะพานที่ 8 ที่ไหนดี?
สร้างที่เกาะศาสนาเชื่อมกับปราสาทแดง