ค้นหา

ทฤษฎีกราฟเบื้องต้น (Graph Theory)

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

เรื่องนี้ไม่ยากน่ะสนุกดี  ก่อนอื่นต้องขอเล่าความเป็นมาของ พวกทฤษฏีกราฟก่อนน่ะคับว่ามีความเป็นมาอย่างไร ผู้ที่อยู่เบื้องหลังของเรื่องนี้ก็คือชายผู้เลื่องชื่อในด้านคณิตศาสตร์ผู้มีนามว่า  LEONHARD  EULER นักคณิตศาสตร์ชาวสวิตเซอร์แลนด์  เราต้องเคารพบูชาท่านนะคับ คือถ้าไม่มีท่านคงไม่มีเรื่องสนุกๆให้เราได้เรียนกัน  ท่านผู้นี้เป็นผู้ที่ได้ชื่อว่าเป็นบิดาแห่ง ทฤษฎีกราฟ น่ะคับ คือเรื่องราวเกี่ยวกับทฤษฎีกราฟนี้ มีจุดกำเนิดอยู่ว่าที่เมืองคอนนิกส์เบอร์ก(KONIGSBERG)นี้ มีแม่น้ำชื่อว่าแม่น้ำพรีเกล(PREGEL) และมีเกาะอยู่สองเกาะอยู่กลางแม่น้ำและมีสะพานอยู่ 7 สะพาน ดังรูปข้างล่างน่ะคับ

A และ D คือ ฝั่งสองฝั่ง   B และ C คือเกาะสองเกาะคับ

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

ตัวอย่างเช่น

เส้นทางเดินรถไฟฟ้า BTS สามรถจำลองให้อยู่ในรูปของกราฟได้

แผนวงจรไฟฟ้า ก็จำลองให้อยู่ในรูปของกราฟได้เช่นกัน

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

ติดต่อเรา wisanu.kkung@gmail.com