creatio ex nihilo
BlogGang Popular Award#10


 
ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 42 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
วิธีที่ออยเลอร์ใช้แก้ปัญหาสะพานเคอนิกส์แบร์ก



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



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

ในบทความปี 1736 ออยเลอร์เริ่มต้นด้วยการแนะนำวิธีเขียนเส้นทางเดินโดยใช้ตัวอักษรของแผ่นดิน เช่น ถ้าคุณเดินข้ามสะพานจาก A ไป B ก็เขียนเส้นทางเดินว่า AB จากนั้นข้ามสะพานจากฝั่ง B ไปยัง C เส้นทางเดินก็เพิ่มขึ้นเป็น ABC หากต่อมาข้ามจาก C กลับมา A อีก เส้นทางก็เป็น ABCA



เมื่อเราเขียนอย่างนี้ ออยเลอร์บอกว่า เส้นทางที่เขียนด้วยตัวอักษร n ตัว ย่อมหมายความว่ามีการข้ามสะพานทั้งหมด n-1 สะพาน เช่น เส้นทาง ABCA มีตัวอักษร 4 ตัว เท่ากับการเดินข้ามสะพาน 4-1 = 3 สะพาน นั่นคือ ปัญหาสะพานเคอนิกส์แบร์ก ถ้าหากเราจะข้ามแต่ละสะพานแค่ครั้งเดียว เราต้องเขียนเส้นทางโดยใช้ตัวอักษร 8 ตัว (เพราะมี 7 สะพาน)

ต่อมา ออยเลอร์สำรวจข้อเท็จจริงพื้นฐานอย่างง่ายว่า ถ้าดินแดนใด ๆ มีสะพานอยู่ k สะพาน และ k เป็นจำนวนคี่ จำนวนตัวอักษรของดินแดนนั้นที่ปรากฎในเส้นทางสุดท้าย ย่อมเท่ากับ (k+1)/2 เช่น ถ้ามีดินแดน 2 ฝั่งคือ A กับ B และมีสะพานอยู่ 1 สะพาน เส้นทางคือ AB หรือ BA แต่ถ้ามีสะพานอยู่ 3 สะพาน เส้นทางคือ ABAB หรือ BABA (ขึ้นอยู่กับว่าคุณเริ่มเดินจากฝั่ง A หรือ B)



แต่ถ้า k เป็นจำนวนคู่ล่ะ เช่น 2 สะพาน เส้นทางอาจเป็น ABA หรือ BAB (ขึ้นอยู่กับว่าคุณเริ่มเดินจากดินแดนไหน) หรือกรณี 4 สะพาน เส้นทางอาจเป็น ABABA หรือ BABAB คงมองเห็นได้ไม่ยากว่า กรณีที่ k เป็นจำนวนคู่ จำนวนตัวอักษรของดินแดนนั้นที่ปรากฎในเส้นทางสุดท้าย ย่อมเท่ากับ (k/2) + 1 ถ้าเราเริ่มต้นในดินแดนนั้น หรือ k/2 ถ้าเราเริ่มต้นนอกดินแดนนั้น

จากนั้นออยเลอร์ก็ใช้หลักการเรียบง่ายอันนี้แหละครับ ย้อนกลับไปมองแผนที่เคอนิกส์แบร์ก ซึ่งมีบริเวณดินแดน 4 บริเวณคือ A B C D แต่ละบริเวณมีสะพาน 5 3 3 3 ตามลำดับ (ดูรูปด้านล่าง) ซึ่งเป็นจำนวนคี่ทั้งหมด ฉะนั้นแต่ละดินแดนจะมีตัวอักษรปรากฎ 3 2 2 2 ตามลำดับ ก็เป็นไปตามสูตร (k+1)/2 นะครับ



ทีนี้ พอเรารวมจำนวนตัวอักษรทั้งหมดที่ปรากฎ (รวม frequency) ได้ 3 + 2 + 2 + 2 = 9 มันฟ้องว่า เส้นทางที่ใช้ 9 ตัวอักษร ต้องมีสะพาน 9 - 1 = 8 สะพาน แต่เมืองเคอร์นิกส์แบร์กมีแค่ 7 สะพาน จึงเป็นไปไม่ได้แน่นอนที่เราจะเดินข้ามให้ครบทุกสะพาน โดยผ่านแค่เพียงสะพานละหนึ่งครั้ง

ออยเลอร์ไม่หยุดแค่เคอนิกส์แบร์ก ในบทความนั้น ออยเลอร์ยังยกตัวอย่างที่ซับซ้อนขึ้นอีก ดังรูป



ดินแดนที่มีเครื่องหมายดอกจัน (*) หมายถึงดินแดนที่มีจำนวนสะพานเป็นเลขคู่ ซึ่งในตาราง (รูปบน) ออยเลอร์เขียนความถี่ของตัวอักษรโดยใช้สูตร k/2 นั่นคือออยเลอร์สมมติว่าไม่ได้เริ่มต้นเดินจากในดินแดนเหล่านี้ ถ้าผลรวมของความถี่เท่ากับจำนวนสะพานพอดี ก็แปลว่าเราต้องหาทางเริ่มเดินจากดินแดนที่มีเครื่องหมายดอกจัน (เพื่อให้ผลรวมของความถี่เพิ่มขึ้นอีกหนึ่ง ตามสูตร (k/1)+1 และเท่ากับจำนวนตัวอักษรที่ต้องใช้บรรยายเส้นทางสุดท้าย-ซึ่งเท่ากับจำนวนสะพานบวกด้วยหนึ่ง) แต่ถ้าผลรวมความถี่มากกว่าจำนวนสะพานอยู่หนึ่ง (หรือพูดว่าผลรวมความถี่เท่ากับจำนวนตัวอักษรที่ใช้บรรยายเส้นทางสุดท้ายพอดี) ก็ให้เริ่มต้นเดินจากดินแดนที่ไม่มีเครื่องหมายดอกจัน จากรูป ผลรวมความถี่คือ 16 และจำนวนสะพานเท่ากับ 15 ดังนั้นจึงมีเส้นทางที่เราสามารถเดินครบทุกสะพานได้ โดยข้ามแต่ละสะพานแค่เพียงครั้งเดียว และเริ่มต้นในดินแดนที่ไม่มีเครื่องหมายดอกจัน ตัวอย่างเส้นทางแสดงดังรูป



ผลรวมของสะพานแต่ละดินแดนทุกดินแดน (ผลรวมในช่อง bridges) จะต้องเท่ากับ 2 เท่าของจำนวนสะพาน อันนี้ปัจจุบันเราเรียกว่า handshaking lemma เห็นชัดนะครับ ก็เพราะสะพาน 1 สะพานต้องเชื่อมดินแดนสองดินแดนเสมอ สุดท้ายออยเลอร์สรุปว่า ถ้ามีดินแดนมากกว่าสองดินแดนที่มีจำนวนสะพานเป็นจำนวนคี่ เราจะไม่สามารถเดินข้ามสะพานทุกสะพานได้ครบโดยเดินผ่านแค่เพียงสะพานและหนึ่งครั้ง



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


Create Date : 21 กุมภาพันธ์ 2555
Last Update : 21 กุมภาพันธ์ 2555 15:44:58 น. 0 comments
Counter : Pageviews.

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.