ทฤษฎีกราฟเบื้องต้น | วิชาการ.คอม


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

สารบัญ

ความเป็นมาของทฤษฎีกราฟ

      ปัญหาสะพานโคนิกส์เบอร์ก (Konigsberg Bridge Problem)ซึ่งเป็นเมืองที่ประกอบด้วย เกาะ 2 เกาะ และสะพาน 7 สะพาน[[62737]]ปัญหาคือเป็นไปได้หรือไม่ ที่จะเริ่มต้น ณ ที่ใดที่หนึ่งแล้วเดินข้ามสะพานทั้ง 7 สะพานโดยที่ผ่านสะพานแต่ละสะพานเพียงครั้งเดียวเท่านั้นแล้วกลับมายังจุดเริ่มต้น [[62738]]ผู้ที่แก้ปัญหานี้ได้คือเลออนฮาร์ด ออยเลอร์ (Leonhard Euler)นักคณิตศาสตร์ชาวสวิสเซอร์แลนด์ ซึ่งเขาพิสูจน์ด้วยการสร้างแผนภาพจำลองปัญหาโดยกำหนดจุด แทน เกาะและดินแดน 2 ฝั่งแม่น้ำ และกำหนดเส้น แทน สะพานซึ่งเชื่อมจุด[[62739]] จากปัญหาเมื่อสร้างแผนภาพจำลองปัญหาจึงมีจุด 4 จุดและเส้น 7 เส้น [[62740]] แนวการตอบปัญหาของออยเลอร์คือเริ่มต้นเดินจากจุดใด ๆ แล้วจะต้องเดินผ่านทุก ๆ เส้น เส้นละ 1 ครั้ง แล้วกลับมาที่เดิม เป็นไปไม่ได้ เพราะไม่ว่าจะเริ่มออกจากจุดใด จะต้องมีการเดินทางเข้าจุดนั้นเสมอโดยเส้นที่ต่างกัน เมื่อเป็นเช่นนี้ จำนวนเส้นที่ออกจากจุดแต่ละจุดต้องเป็นจำนวนคู่ จากแผนภาพจะพบว่าไม่มีจุดใดเลยที่มีจำนวนเส้นออกจากจุดเป็นจำนวนคู่ แผนภาพที่ประกอบด้วยจุดและเส้นนี้เรียกว่า “กราฟ” ปัญหานี้ได้รับการยกย่องว่าเป็นปัญหาเริ่มต้นของการเกิดทฤษฎีกราฟ และจากผลงานการพิสูจน์ของ ออยเลอร์ จึงทำให้เขาได้รับการยกย่องว่าเป็น ผู้ให้กำเนิด “ทฤษฎีกราฟ”

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