ผลต่างระหว่างรุ่นของ "สะพานทั้งเจ็ดแห่งเมืองเคอนิชส์แบร์ค"
ล Tvcccp ย้ายหน้า สะพานทั้งเจ็ดแห่งเมืองเคอนิจส์แบร์ก ไปยัง สะพานทั้งเจ็ดแห่งเมืองเคอนิชส์แบร์ค |
ไม่มีความย่อการแก้ไข ป้ายระบุ: การแก้ไขแบบเห็นภาพ แก้ไขจากอุปกรณ์เคลื่อนที่ แก้ไขจากเว็บสำหรับอุปกรณ์เคลื่อนที่ |
||
บรรทัด 3: | บรรทัด 3: | ||
[[ไฟล์:Konigsberg_bridges.png|frame|right|แผนที่ของเมืองเคอนิชส์แบร์คในสมัยออยเลอร์ แสดงให้เห็นสะพานทั้งเจ็ด]] |
[[ไฟล์:Konigsberg_bridges.png|frame|right|แผนที่ของเมืองเคอนิชส์แบร์คในสมัยออยเลอร์ แสดงให้เห็นสะพานทั้งเจ็ด]] |
||
'''สะพานทั้งเจ็ดแห่งเมืองเคอนิชส์แบร์ค''' ({{lang-en|Seven Bridges of Königsberg}}) เป็นปัญหาที่ได้รับแรงบันดาลใจมาจากสถานที่ คือ เมือง[[เคอนิชส์แบร์ค]] ใน |
'''สะพานทั้งเจ็ดแห่งเมืองเคอนิชส์แบร์ค''' ({{lang-en|Seven Bridges of Königsberg}}) เป็นปัญหาที่ได้รับแรงบันดาลใจมาจากสถานที่ คือ เมือง[[เคอนิชส์แบร์ค]] ในรัสเซีย (ปัจจุบันคือ[[คาลีนินกราด]] [[ประเทศรัสเซีย]] ในปัจจุบัน) ซึ่งตั้งอยู่บน[[แม่น้ำเพรเกิล]]และมีเกาะอยู่ 2 เกาะเชื่อมต่อถึงกันด้วย[[สะพาน]]ทั้ง 7 สะพาน คำถามคือ เป็นไปได้หรือไม่ที่จะเดินให้ครบทุกสะพาน โดยผ่านแต่ละสะพานเพียงครั้งเดียวและกลับมาที่จุดเริ่มต้นได้ ใน[[พ.ศ. 2279]] (ค.ศ. 1736) [[เลออนฮาร์ด ออยเลอร์]] ได้พิสูจน์ว่าไม่มีทางเป็นไปได้ |
||
== คำตอบของออยเลอร์ == |
== คำตอบของออยเลอร์ == |
รุ่นแก้ไขเมื่อ 18:41, 20 กันยายน 2562
บทความนี้ไม่มีการอ้างอิงจากแหล่งที่มาใด |
สะพานทั้งเจ็ดแห่งเมืองเคอนิชส์แบร์ค (อังกฤษ: Seven Bridges of Königsberg) เป็นปัญหาที่ได้รับแรงบันดาลใจมาจากสถานที่ คือ เมืองเคอนิชส์แบร์ค ในรัสเซีย (ปัจจุบันคือคาลีนินกราด ประเทศรัสเซีย ในปัจจุบัน) ซึ่งตั้งอยู่บนแม่น้ำเพรเกิลและมีเกาะอยู่ 2 เกาะเชื่อมต่อถึงกันด้วยสะพานทั้ง 7 สะพาน คำถามคือ เป็นไปได้หรือไม่ที่จะเดินให้ครบทุกสะพาน โดยผ่านแต่ละสะพานเพียงครั้งเดียวและกลับมาที่จุดเริ่มต้นได้ ในพ.ศ. 2279 (ค.ศ. 1736) เลออนฮาร์ด ออยเลอร์ ได้พิสูจน์ว่าไม่มีทางเป็นไปได้
คำตอบของออยเลอร์
ในการพิสูจน์นั้น ออยเลอร์ได้แปลงปัญหานี้ให้อยู่ในรูปทฤษฎีกราฟ โดยแทนที่ดินด้วยจุด ที่เรียกว่า จุดยอด (vertex) และแทนสะพานด้วยเส้น ที่เรียกว่า เส้นเชื่อม (edge)
ทฤษฎีกราฟเป็นสาขาหนึ่งของทอพอโลยี ซึ่งจะไม่สนใจรูปร่างของกราฟว่าเป็นอย่างไร นั่นคือเส้นที่เชื่อมระหว่างจุดยอดต่างๆจะเป็นเส้นตรงหรือเส้นโค้งก็ได้ แต่มันยังคงต้องเชื่อมจุดยอดนั้นอยู่ไม่เปลี่ยนแปลง
ออยเลอร์ได้แสดงให้เห็นว่า เราจะเดินผ่านเส้นเชื่อมทุกเส้นในกราฟเพียงครั้งเดียวและกลับมาที่จุดเริ่มต้นได้ ก็ต่อเมื่อ กราฟนั้นไม่มีจุดยอดที่มีจำนวนเส้นเชื่อมมาเชื่อมจุดยอดนั้นเป็นจำนวนคี่ ซึ่งแนวเดินนี้จะเรียกว่า วงจรออยเลอร์ (Eulerian circuit) ดังนั้น กราฟของสะพานทั้งเจ็ดจึงไม่มีทางทำได้
แต่ถ้าเราไม่สนใจว่าต้องเดินกลับมาที่จุดเริ่มต้น เราจะหาแนวเดินนั้นได้ ก็ต่อเมื่อ กราฟนั้นไม่มีจุดยอดที่มีจำนวนเส้นเชื่อมมาเชื่อมจุดยอดนั้นเป็นจำนวนคี่ หรือกราฟนั้นอาจมีจุดยอดดังกล่าวอยู่ 2 จุด ซึ่งแนวเดินนี้จะเรียกว่า รอยเดินออยเลอร์ (Eulerian trail) ดังนั้น กราฟของสะพานทั้งเจ็ดจึงทำไม่ได้เช่นเดียวกัน
ความสำคัญในประวัติศาสตร์ของคณิตศาสตร์
ในประวัติศาสตร์ของคณิตศาสตร์ ปัญหานี้เป็นปัญหาแรกในทฤษฎีกราฟ และทฤษฎีกราฟนั้นเป็นส่วนหนึ่งของทอพอโลยี ซึ่งเป็นปัญหาแรกในทอพอโลยีด้วย
ดัดแปลงปัญหา
สะพานที่ 8 ของเจ้าชายสีน้ำเงิน
เจ้าชายน้ำเงิน ได้วางแผนสร้างสะพานขึ้นมาสะพานหนึ่ง เพื่อให้เขาสามารถเริ่มเดินจากปราสาทสีน้ำเงินในตอนหัวค่ำโดยผ่านแต่ละสะพานหนึ่งครั้ง และไปจบที่เกาะกลางเพื่อดื่มเบียร์ฉลองชัยชนะ แน่นอนว่าเขาไม่ต้องการให้เจ้าชายสีแดงใช้สะพานนี้เพื่อจุดประสงค์เดียวกันกับเขา เจ้าชายน้ำเงินจะสร้างสะพานที่ 8 ที่ไหนดี?
สะพานที่ 9 ของเจ้าชายสีแดง
เจ้าชายแดงต้องการล้างแค้นเจ้าชายสีน้ำเงิน โดยการสร้างสะพานหนึ่งสะพานที่จะทำให้เขาเดินผ่านมันได้ทั้งหมดโดยไปจบที่เกาะกลาง และนอกจากนั้นเขายังต้องการกันไม่ให้เจ้าชายน้ำเงินทำได้อย่างที่เขาต้องการตอนสร้างสะพานที่ 8 เจ้าชายแดงจะสร้างสะพานที่ 9 ที่ไหนดี?
สะพานที่ 10 ของบาทหลวง
บาทหลวงอนาถใจกับความเหลวไหลของเจ้าชายทั้งสอง จึงต้องการสร้างสะพานที่ 10 เพื่อให้เจ้าชายทั้งสองกลับบ้านนอนแทนที่จะมาดื่มเหล้าเมามาย บาทหลวงจะสร้างสะพานที่ 10 ที่ไหนดี?
เฉลยปัญหาดัดแปลง
สะพานที่ 8 ของเจ้าชายน้ำเงิน
สร้างที่เกาะศาสนาเชื่อมกับปราสาทแดง..
สะพานที่ 9 ของเจ้าชายแดง
สร้างระหว่างสองปราสาท
สะพานที่ 10 ของบาทหลวง
สร้างระหว่างเกาะกลางกับปราสาทแดง