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

Transcript

เมืองคาลินินกราด ประเทศรัสเซีย

เมืองรัสเซียเมืองนี้ ครั้งหนึ่งเคยเป็นส่วนหนึ่งของประเทศเยอรมนี

ก่อนหน้านี้รู้จักกันในชื่อ เมืองเคอนิกส์เบิร์ก ตั้งอยู่บนแม่น้ำเพรเกล ซึ่งเป็นเหตุให้เกิดปริศนาทางคณิตศาสตร์อันโด่งดัง

เมืองเคอนิกส์เบิร์ก ถูกสร้างขึ้นบนทั้งสองฝั่งของแม่น้ำเพรเกล และรวมไปถึงเกาะกลางแม่น้ำเกาะหนึ่ง ที่แม่น้ำแยกออกเป็นสองสาย

เมืองนี้ได้มีการก่อสร้างสะพานหลายอัน เพื่อเชื่อมต่อส่วนต่างๆ… และสะพานเหล่านี้เองที่บันดาลใจให้เกิดปริศนาสะพานทั้งเจ็ดแห่งเมืองเคอนิกส์เบิร์กขึ้น

ปริศนาถามไว้ว่าจะเดินรอบเมืองอย่างไร โดยข้ามสะพานแต่ละสะพานเพียงแค่ครั้งเดียว

มีความพยายามที่จะเดินผ่านหลากหลายเส้นทาง เพื่อแก้ปัญหานี้ แต่มันยังคงทำให้ผู้คนที่ทดลองเดินต้องสับสนอยู่

ลีออนฮาร์ด ออยเลอร์
ค.ศ. 1707 - 1883

ในปี ค.ศ.1735 นักคณิตศาสตร์ชาวสวิส ลีออนฮาร์ด ออยเลอร์ ก็แก้ปัญหานี้ได้ในที่สุด โดยพิสูจน์ว่า มันเป็นไปไม่ได้!

ออยเลอร์ รู้ดีว่าสิ่งสำคัญคือการเชื่อมต่อเข้าด้วยกัน ของสะพานต่างๆ

ดังนั้น เขาจึงทำให้ปัญหานี้เข้าใจได้ง่ายขึ้น โดยแทนที่แต่ละผืนแผ่นดินด้วยจุด

สะพานถูกแทนด้วยเส้นเชื่อมต่อ

การทำเช่นนี้จะได้เครือข่าย หรือ กราฟแบบง่ายๆ

และหากคุณลองพยายามวาดกราฟนี้ขึ้นมาใหม่ โดยไม่ลากทับเส้นเดิมเลย จะเห็นว่ามันทำไม่ได้

ออยเลอร์ อธิบายโดยแสดงว่า หากคุณผ่านจุดๆ หนึ่งไป จะต้องมีเส้นเชื่อมต่อที่จุดนั้น สองเส้น เส้นหนึ่งผ่านเข้ามา... และเส้นหนึ่งผ่านออกไป

ดังนั้น จำนวนเส้นเชื่อมต่อที่บรรจบลงที่จุดๆ หนึ่งต้องเป็นเลขคู่ ยกเว้นจุดเริ่มต้น และจุดสิ้นสุด

สำหรับทุกๆ เส้นเชื่อมต่อที่ผ่านเข้ามา เส้นเชื่อมต่ออีกเส้นหนึ่งต้องผ่านออกไป

เนื่องจาก มีจุดเริ่มต้นเพียงหนึ่งจุด… และจุดสิ้นสุดหนึ่งจุด มันจะมีเพียงสองจุดในกราฟเท่านั้น ที่สามารถมีจำนวนเส้นเชื่อมต่อเป็นเลขคี่ได้

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

ออยเลอร์ได้ประยุกต์กฏนี้กับกราฟอื่นๆ ด้วย และเรียกเส้นทางต่อเนื่องที่เป็นไปได้ว่า เส้นทางออยเลอร์

เส้นทางออยเลอร์:
เส้นทางต่อเนื่องระหว่างจุดสองจุด
ที่ผ่านเส้นเชื่อมจุดทุกเส้นหนึ่งครั้ง

ผลงานของออยเลอร์ในเรื่องเส้นทางออยเลอร์ กลายเป็นพื้นฐานสำคัญของทฤษฎีกราฟ ซึ่งเป็นคณิตศาสตร์สาขาหนึ่งที่ถูกนำไปใช้ในด้านวิศวกรรมไฟฟ้า วิทยาการคอมพิวเตอร์ และชีวเคมี

แต่ออยเลอร์ได้พิสูจน์แล้วว่า ไม่มีเส้นทางออยเลอร์อยู่ในเมืองเคอนิกส์เบิร์ก

มันเป็นไปไม่ได้ที่จะเดินรอบเมืองนี้ โดยไม่เหยียบซ้ำที่เดิมเลย