ผลต่างระหว่างรุ่นของ "สะพานทั้งเจ็ดแห่งเมืองเคอนิชส์แบร์ค"
ล โรบอต เพิ่ม: eu:Königsberg-eko zazpi zubietako ebazkizuna |
ล แทนที่คำอัตโนมัติ (-[[ภาพ: +[[ไฟล์:) ด้วยบอต |
||
บรรทัด 1: | บรรทัด 1: | ||
{{ต้องการอ้างอิง}} |
{{ต้องการอ้างอิง}} |
||
[[ |
[[ไฟล์:Konigsberg_bridges.png|frame|right|แผนที่ของเมืองเคอนิกส์แบร์กในสมัยออยเลอร์ แสดงให้เห็นสะพานทั้งเจ็ด]] |
||
'''สะพานทั้งเจ็ดแห่งเมืองเคอนิกส์แบร์ก''' (Seven Bridges of Königsberg) หรือ '''สะพานทั้งเจ็ดแห่งเมืองโคนิกส์เบิร์ก''' เป็นปัญหาที่ได้รับแรงบันดาลใจมาจากสถานที่ คือ เมือง[[เคอนิกส์แบร์ก]] ในปรัสเซีย (ปัจจุบันคือ [[Kaliningrad]] ใน[[ประเทศรัสเซีย|รัสเซีย]]) ซึ่งตั้งอยู่บนแม่น้ำ Pregel และมีเกาะอยู่ 2 เกาะเชื่อมต่อถึงกันด้วย[[สะพาน]]ทั้ง 7 สะพาน คำถามคือ เป็นไปได้หรือไม่ที่จะเดินให้ครบทุกสะพาน โดยผ่านแต่ละสะพานเพียงครั้งเดียวและกลับมาที่จุดเริ่มต้นได้ ใน[[พ.ศ. 2279]] (ค.ศ. 1736) [[เลออนฮาร์ด ออยเลอร์]] ได้พิสูจน์ว่าไม่มีทางเป็นไปได้ |
'''สะพานทั้งเจ็ดแห่งเมืองเคอนิกส์แบร์ก''' (Seven Bridges of Königsberg) หรือ '''สะพานทั้งเจ็ดแห่งเมืองโคนิกส์เบิร์ก''' เป็นปัญหาที่ได้รับแรงบันดาลใจมาจากสถานที่ คือ เมือง[[เคอนิกส์แบร์ก]] ในปรัสเซีย (ปัจจุบันคือ [[Kaliningrad]] ใน[[ประเทศรัสเซีย|รัสเซีย]]) ซึ่งตั้งอยู่บนแม่น้ำ Pregel และมีเกาะอยู่ 2 เกาะเชื่อมต่อถึงกันด้วย[[สะพาน]]ทั้ง 7 สะพาน คำถามคือ เป็นไปได้หรือไม่ที่จะเดินให้ครบทุกสะพาน โดยผ่านแต่ละสะพานเพียงครั้งเดียวและกลับมาที่จุดเริ่มต้นได้ ใน[[พ.ศ. 2279]] (ค.ศ. 1736) [[เลออนฮาร์ด ออยเลอร์]] ได้พิสูจน์ว่าไม่มีทางเป็นไปได้ |
||
บรรทัด 10: | บรรทัด 10: | ||
<SPAN STYLE="font-size: 300%;"> |
<SPAN STYLE="font-size: 300%;"> |
||
[[ |
[[ไฟล์:Konigsberg_bridges.png|180px]] → |
||
[[ |
[[ไฟล์:7_bridges.png|179px]] → |
||
[[ |
[[ไฟล์:konigsburg_graph.png|180px]] |
||
</SPAN> |
</SPAN> |
||
บรรทัด 26: | บรรทัด 26: | ||
== ดัดแปลงปัญหา == |
== ดัดแปลงปัญหา == |
||
[[ |
[[ไฟล์:7_bridgesID.png|300px]] |
||
=== สะพานที่ 8 ของเจ้าชายน้ำเงิน === |
=== สะพานที่ 8 ของเจ้าชายน้ำเงิน === |
รุ่นแก้ไขเมื่อ 19:18, 28 เมษายน 2553
บทความนี้ไม่มีการอ้างอิงจากแหล่งที่มาใด |
สะพานทั้งเจ็ดแห่งเมืองเคอนิกส์แบร์ก (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 ของบาทหลวง
สร้างระหว่างเกาะกลางกับปราสาทแดง