ปริศนาคณิตศาสตร์ - สะพานทั้งเจ็ดแห่ง Konigsberg

กระทู้คำถาม

ธรณีวิทยา ประวัติศาสตร์ การออกแบบเพื่อสิ่งแวดล้อม ภาพวาดสีน้ำ

ล้อมรอบระหว่างโปแลนด์และลิทัวเนียตามชายฝั่งทะเลบอลติก เป็นพื้นที่ส่วนหนึ่งของรัสเซียที่อยู่ห่างจากชายแดนรัสเซีย 200 ไมล์ ดินแดนKaliningrad ซึ่งเป็นเขตยกเว้นของรัสเซียเดิมเป็นรัฐปรัสเซีย ก่อนที่จะถูกย้ายไปยังสหภาพโซเวียตหลังสิ้นสุดสงครามโลกครั้งที่สองเมื่อมหาอำนาจพันธมิตรพบกันที่ Potsdam เพื่อตัดสินว่าใครจะได้ดินแดนใด ย้อนกลับไปก่อนหน้านั้น Kaliningrad เป็นที่รู้จักกันในชื่อ Königsberg กับการไขปริศนาทางคณิตศาสตร์

ความสัมพันธ์ของ Königsberg กับวิทยาศาสตร์และคณิตศาสตร์ย้อนกลับไปในศตวรรษที่ 18 ในปี 1735 ตอนนั้นเมืองนี้เป็นศูนย์กลางของเวทมนตร์ศาสตร์และวัฒนธรรมจากเยอรมนี โปแลนด์ และลิทัวเนีย ซึ่ง Königsberg เป็นบ้านเกิดของนักคณิตศาสตร์ชื่อดังอย่าง Christian Goldbach ซึ่งทุกวันนี้หากจำได้ถึงการคาดเดาของ Goldbach ซึ่งเป็นหนึ่งในปัญหาที่ไม่ได้รับการแก้ไขที่เก่าแก่ที่สุด และเป็นที่รู้จักกันดีที่สุดในทฤษฎีจำนวน David Hilbert ผู้สร้างช่องว่างของ Hilbert และ Carl Neumann สำหรับ Neumann series (คณิตศาสตร์อนุกรม) ที่โด่งดังที่ถูกสอนในโรงเรียนมัธยม

Königsberg ยังเป็นบ้านของ Gustav Kirchhoff นักฟิสิกส์ชื่อดัง (กฎหมายของ Kirchhoff เป็นพื้นฐานในการออกแบบวงจรไฟฟ้าและอิเล็กทรอนิกส์) และ Otto Wallach นักเคมีผู้ได้รับรางวัลโนเบล และ Immanuel Kant นักปรัชญาผู้มีชื่อเสียงอีกคนหนึ่งที่เกิดในเมืองนี้ที่ภูมิใจในเมืองบ้านเกิดของเขามากจนแทบไม่ได้ออกจากที่นี่เลยตลอดชีวิต

ในขณะที่เหล่าผู้ที่มีพรสวรรค์เหล่านี้ทั้งหมดของ Königsberg ทำให้เมืองนี้ภาคภูมิใจ แต่ Leonard Euler นักคณิตศาสตร์ชาวสวิสเป็นผู้ซึ่งทำให้ชื่อของ Königsberg เป็นอมตะ

แผนที่ Königsberg ที่มีป้ายชื่อสะพานเจ็ดแห่งราวปี 1905

ตอนนี้ Konigsberg หรือ Kaliningrad ตั้งอยู่บนแม่น้ำ Pregel เมื่อแม่น้ำไหลผ่านเมืองทำให้เกิดเกาะใหญ่สองเกาะคือ Kneiphof และ Lomse ย้อนกลับไปในศตวรรษที่ 18 หมู่เกาะเหล่านี้เชื่อมต่อกับฝั่งเหนือและฝั่งใต้ของแม่น้ำ รวมทั้งสะพานเจ็ดแห่งที่เชื่อมต่อกันซึ่งเป็นศูนย์กลางชีวิตของเมือง ทำให้เมืองนี้เจริญรุ่งเรืองด้วยเศรษฐกิจการค้า และสาเหตุส่วนหนึ่งที่ทำให้เมืองสามารถทำทุกอย่างได้ดีเพราะมีโครงสร้างที่น่าสนใจเป็นพิเศษ

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

เมื่อ Leonhard Euler นักคณิตศาสตร์และนักฟิสิกส์ชาวสวิสได้ยินเกี่ยวกับปัญหาที่น่าสนใจของเมือง Königsberg ที่กำลังเผชิญอยู่ ปริศนาดังกล่าวมีชื่อว่า " The Seven Bridges of Königsberg Problem " ปัญหาซึ่งดูเหมือนจะเป็นเรื่องง่าย เพราะมีสะพานตั้งเจ็ดแห่งเพื่อเชื่อมต่อเกาะทั้งสองและส่วนท้ายน้ำของเมือง แม้ Euler เองก็ยังสงสัยว่าคน ๆ หนึ่งจะสามารถเดินข้ามสะพานทั้งเจ็ดได้เพียงครั้งเดียวเพื่อสัมผัสทุกส่วนของเมืองได้หรือไม่ โดยไม่มีข้อกำหนดว่าจุดเริ่มต้นและจุดสิ้นสุดต้องเป็นจุดเดียวกัน

เมือง Königsberg Cr.Historic Cities Research Project

ในที่สุด เขาก็แก้ปัญหานี้ด้วยมุมมองที่แตกต่างออกไปโดยใช้คณิตศาสตร์เพื่อพิสูจน์ว่า จะข้ามสะพานทั้งเจ็ดเพียงครั้งเดียวและเยี่ยมชมทุกส่วนของเมือง Königsberg ได้ โดยวิธีแก้ปัญหานั้นจะต้องมองว่าแต่ละสะพานเป็นจุดสิ้นสุด (จุดยอดในแง่คณิตศาสตร์) และเป็นการเชื่อมต่อกันระหว่างแต่ละสะพาน (โดยจุดยอด) ซึ่งตอนแรก Euler คิดว่ามีแต่สะพานจำนวนคู่เท่านั้นที่ให้ผลลัพธ์ที่ถูกต้องในการสัมผัสทุกส่วนของเมืองโดยไม่ต้องข้ามสะพานสองครั้ง

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

จากการวิเคราะห์สมุดบันทึกของ Euler ที่จัดทำโดยสมาคมคณิตศาสตร์แห่งอเมริกา เขาแทนแผ่นดินเป็นตัวพิมพ์ใหญ่ - A, B, C, D - และติด track
ตามสะพานที่ข้ามไปจากจุดเริ่มต้นและจุดสิ้นสุด ตัวอย่างเช่น ในการข้ามจากพื้นดิน A ไปยัง B การเดินทางบนสะพานจะเรียกว่า AB และหากต้องข้ามจากจุดบก B ไปยัง D การเดินทางทั้งหมดจะเป็น ABD เพื่อแสดงถึงการข้ามสะพานสองแห่งและสัมผัสกับมวลแผ่นดินสามแห่ง

ในกระบวนการทำแบบฝึกหัดนี้ Euler ตระหนักว่าในการที่จะข้ามสะพานทั้งเจ็ดแห่งแบบในเมือง Königsberg ปัญหานั้นจำเป็นต้องมี “landmasses” อย่างน้อยแปดแห่งหรือลำดับตัวอักษรเพื่อแก้ปัญหา

ภาพวาดต้นฉบับของ Euler (Solutio problematis ad geometriam situs pertinenti) , Cr.MAA Euler Archive

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

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

ในเวลาต่อมา สะพานทั้งเจ็ดในสมัยของ Euler สองแห่งได้แก่ Krämerbrückenfest หรือ Merchant's Bridge และสะพาน Green Bridge ที่นำไปสู่และออกจากเกาะ Kneiphof ไม่รอดจากสงครามโลกครั้งที่สองในปี 1942 และถูกแทนที่ด้วยสะพานลอยคอนกรีตยาว 500 เมตร

สะพานอีกสองแห่ง - Schmiedebrückeหรือ Forge bridge และ Köttelbrücke ไม่รอดจากการทิ้งระเบิดครั้งใหญ่ในช่วงสงครามโลกครั้งที่สองและไม่ได้ถูกแทนที่

Honigbrücke หรือ Honey Bridge ที่เชื่อมระหว่างเกาะ Lomse กับ Kneiphof ทางทิศตะวันออก สะพานนี้เป็นสะพาน Kneiphof แห่งเดียวที่รอดพ้นจากสงครามโลกครั้งที่สองและยังคงพบเห็นได้ในปัจจุบัน และสะพานแห่งที่ 7 และสะพานสุดท้าย Hohe Brücke หรือสะพาน High Bridge ที่เคยข้ามไปยัง Lomse พังยับเยินและแทนที่ด้วยสะพานใหม่เช่นกัน

Seven Bridges of Königsberg ในรูปแบบกราฟ