การหาจำนวนของ Hamiltonian Cycle ใน SimpleGraph

ชื่อผู้จัดทำโครงงานวิทยาศาสตร์
  • ประทีป รักษาสกุลวงศ์

อาจารย์ที่ปรึกษาโครงงานวิทยาศาสตร์
  • ณรงค์ ปั้นนิ่ม

สถาบันการศึกษาที่กำกับดูแลโครงงานวิทยาศาสตร์

โรงเรียนมหิดลวิทยานุสรณ์

ระดับการศึกษา

โครงงานในระดับการศึกษาประกาศนียบัตรวิชาชีพ

หมวดวิชา

โครงงานในสาขาวิชาคณิตศาสตร์

วันที่จัดทำโครงงานวิทยาศาสตร์

01 มกราคม 2541

บทคัดย่อโครงงานวิทยาศาสตร์

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