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

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

แผนที่ของเมืองเคอนิชส์แบร์คในสมัยออยเลอร์ แสดงให้เห็นสะพานทั้งเจ็ด
https://th.wikipedia.org/wiki/%E0%B9%84%E0%B8%9F%E0%B8%A5%E0%B9%8C:Konigsberg_bridges.png

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

https://th.wikipedia.org/wiki/%E0%B9%84%E0%B8%9F%E0%B8%A5%E0%B9%8C:Leonhard_Euler.jpg
ภาพของเลออนฮาร์ด ออยเลอร์ วาดโดยจิตรกร เอ็มมานูเอล ฮันด์มันน์ (Emanuel Handmann) เมื่อ ค.ศ.1753

เลออนฮาร์ด ออยเลอร์ เป็นนักคณิตศาสตร์ที่ยิ่งใหญ่ที่สุดคนหนึ่งของโลก มีผลงานทางคณิตศาสตร์มากมาย ที่น้องๆนักเรียนอาจเคยได้ยินกัน อาทิ แผนภาพออยเลอร์ ที่ใช้ในการอธิบายความสัมพันธ์ของเซตต่าง ๆนั่นเอง

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

ออยเลอร์ เริ่มต้นโดยการเปลี่ยนแผนที่สะพาน ให้กลายเป็นภาพที่เข้าใจง่ายขึ้น โดยแทนแผ่นดินทั้ง 4 ส่วนด้วยตัวอักษร A B C และ D

https://www.bloggang.com/data/z/zol/picture/1329810584.jpg
  • หากเดินจาก แผ่นดิน A ไป B ให้แทนด้วย อักษร AB
  • หากเดินจาก แผ่นดิน A ไป B และไป C ให้แทนด้วย อักษร ABC
  • หากเดินจาก แผ่นดิน A ไป B ไป C ไป ฺB ให้แทนด้วย อักษร ABCB

บทสรุปแรก

  • ถ้าหาก มี 1 สะพาน จะข้ามไปได้ 2 จุด หรือ 2ตัวอักษร เช่น AB หรือ BA
  • ถ้าหาก มี 2 สะพาน จะข้ามไปได้ 3 จุด หรือ 3 ตัวอักษร เช่น ABA หรือ BAB
  • ถ้าหาก มี 3 สะพาน จะข้ามไปได้ 4 จุด หรือ 4 ตัวอักษร เช่น ABCD หรือ BABC

จำนวนสะพาน = จำนวนอักษร + 1

ดังนั่น เมืองโคนิกสเบิร์ก มี 7 สะพาน เส้นทางต้องมี 8 อักษร

บทสรุปที่สอง

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

เช่น สมมุติให้มี 2 แผ่นดิน คือ A และ B

  • ถ้ามี 1 สะพาน จะข้ามได้ AB หรือ BA (ไม่สามารถกลับมาจุดเริ่มต้นได้)
  • ถ้ามี 2 สะพาน จะข้ามได้ ABA หรือ BAB (สามารถกลับมาจุดเริ่มต้นได้)
  • ถ้ามี 3 สะพาน จะข้ามได้ ABAB หรือ BABA (ไม่สามารถกลับมาจุดเริ่มต้นได้)
  • ถ้ามี 4 สะพาน จะข้ามได้ ABABA หรือ BABAB (สามารถกลับมาจุดเริ่มต้นได้)

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

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

สรุป ออยเลอร์ ใช้การคิดเชิงนามธรรม เปลี่ยนแผนที่เมือง ให้กลายเป็นภาพอย่างง่าย แล้วนำมาอธิบาย พิสูจน์ปัญหา ต่อมาแนวคิดนี้ถูกต่อยอดกลายเป็นทฤษฎีกราฟ ที่ใช้งานอย่างแพร่หลาย เป็นหนึ่งในตัวอย่างของการใช้การคิดเชิงนามธรรมมาสร้างเป็นองค์ความรู้ใหม่ๆครับ

สำหรับคนที่ชอบบทความนี้ อย่าลืมกด share หรือ กด like ที่ช่อง Fackbook: https://www.facebook.com/KidsCodeOnlineTH/ เพื่อเป็นกำลังใจให้กับทีมงานด้วยนะครับ

2 thoughts on “ปริศนาสะพานทั้งเจ็ดแห่งเมืองโคนิกสเบิร์ก

  1. บทความอื่นๆ วิทยาการคำนวณ วิทยาการคำนวณ ม.1
    ปริศนาสะพานทั้งเจ็ดแห่งเมืองโคนิกสเบิร์ก

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: