306 ปีออยเลอร์ - 1001

[brid.ladawan]

306 ปีออยเลอร์ - 1001

เมื่อวันที่ 15 เมษายน ที่ผ่านมา เป็นวันคล้ายวันเกิดของบุคคลสำคัญคนหนึ่ง สำคัญถึงขนาดที่กูเกิลเอามาสร้างเป็นดูเดิล (doodle) หรือที่หลายคนเรียกมันเป็นโลโก้ของกูเกิลที่อยู่ในหน้าหลัก เวลาเราเข้าไปค้นหาคำค้นต่าง ๆ นั่นแหละครับ (เพื่อให้หลายคนได้ปลื้ม กูเกิลเปลี่ยนดูเดิลเพื่อต้อนรับวันสงกรานต์ในวันที่ 13-14 เมษายนเช่นกัน)

นักเรียน นักศึกษา ในด้านศาสตร์คอมพิวเตอร์ จะต้องเคยเรียนทฤษฎีหลายอันที่คิดโดยเขาคนนี้ เลออนฮาร์ด ออยเลอร์ (Leonhard Euler) ซึ่งเป็นนักคณิตศาสตร์และนักฟิสิกส์ชื่อดังชาวสวิตเซอร์แลนด์ เกิดเมื่อวันที่ 15 เมษายน เมื่อ 306 ปีที่แล้ว ถือเป็นบุคคลที่มีความสำคัญยิ่งต่อวงการคณิตศาสตร์ โดยเฉพาะอย่างยิ่งวิชาคณิตศาสตร์แบบไม่ต่อเนื่อง หรือ Discrete Mathematics (ราชบัณฑิตยสถานใช้คำว่า คณิตศาสตร์วิยุต) ที่ในทางคอมพิวเตอร์มีการนำมาใช้กันอย่างแพร่หลาย

ออยเลอร์ได้เสนอแนวคิดไว้หลายเรื่องด้วยกัน ผมจะเริ่มจากสมการที่อยู่บนตัวโอตัวแรกในดูเดิล ซึ่งหลายท่านน่าจะสังเกตเห็น นั่นคือ สมการ V – E + F = 2 ซึ่งถือเป็นสมการที่บอกลักษณะ (Euler Characteristic) ของรูปทรงเหลี่ยม เช่น พีระมิดฐานสามเหลี่ยม (Tetrahedron) ที่เป็นรูปอยู่ในตัว O ตัวแรก จะมีมุม 4 มุม (มุม ก็คือ V หรือ Vertex) มีสัน 6 เส้น (สัน คือ E หรือ Edge) และมีพื้นผิว 4 อัน (พื้นผิว คือ F หรือ Face) เมื่อนำมารวมกันเป็นสมการแล้ว จะได้ 4 – 6 + 2 = 2 นั่นเอง ซึ่งสมการนี้จะเป็นจริงสำหรับรูปกราฟเชิงระนาบ หรือ Planar Graph ด้วย ที่ถือว่าผู้เรียนวิชาคณิตศาสตร์แบบไม่ต่อเนื่องทุกคนต้องผ่านมาแล้วทั้งสิ้น

แนวคิดที่โด่งดังมากของออยเลอร์อีกอันหนึ่ง คือ การใช้วิธีเส้นทางของออยเลอร์ หรือ Euler Path เพื่อบอกว่า การเดินข้ามสะพานทั้งเจ็ดแห่งของเมืองเคอนิกส์แบร์ก (Knigsberg) ตามรูปด้านล่างของตัว O ตัวแรกในดูเดิล ปัญหานี้มีอยู่ว่า จะทำอย่างไร จึงจะเที่ยวชมเมืองนี้ได้โดยจะต้องข้ามสะพานทั้งเจ็ดแห่งและข้ามสะพานแต่ละแห่งได้เพียงแค่ครั้งเดียวเท่านั้น ซึ่งจะเริ่มต้นและจบตรงไหนก็ได้

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

เป็นอย่างไรครับ ลากได้ไหมเอ่ย?

ออยเลอร์แปลงรูปสะพานทั้งเจ็ดแห่ง และพื้นดินที่สะพานเหล่านี้เชื่อมอยู่ให้เป็นกราฟ แล้วบอกว่า การจะทำได้แบบนั้น จะต้องข้ามสะพานเข้าและออกจากพื้นดินที่ไม่ใช่ต้นทางและปลายทางเป็นจำนวนคู่ และจะต้องมีพื้นดินที่มีสะพานเชื่อมเป็นจำนวนคี่ เพียงสองแห่งเท่านั้น คือ พื้นดินต้นทางกับปลายทาง จากรูปที่มีตัวอักษรกำกับ จะเห็นว่า มีสะพานเชื่อมกับพื้นดิน A, C และ D สามแห่ง ในขณะที่มีสะพานเชื่อมกับพื้นดิน B ห้าแห่งด้วยกัน ซึ่งเป็นไปไม่ได้ที่จะหาทางเดินตามเงื่อนไขดังกล่าวได้ ซึ่งออยเลอร์แปลงปัญหานี้ให้อยู่ในรูปของกราฟ (ที่อยู่ด้านล่างระหว่างตัว O สองตัวในดูเดิลของกูเกิลครับ)

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

สุกรี สินธุภิญโญ
(sukree.s@chula.ac.th)
ภาควิชาวิศวกรรมคอมพิวเตอร์
คณะวิศวกรรมศาสตร์ จุฬาลงกรณ์มหาวิทยาลัย

ที่มา : เดลินิวส์ออนไลน์
วันศุกร์ที่ 19 เมษายน พ.ศ.2556