Graphs and Matrices

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

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

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

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

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

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

หมวดวิชา

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

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

01 มกราคม 2541

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

จำนวนทางเดิน (Walk) ในกราฟนั้น เราสามารถหาได้ด้วยวิธีต่างๆมากมาย และมีวิธีหนึ่งที่น่าสนใจคือการแปลงกราฟให้อยู่ในรูปของ เมทริกซ์ประชิด (adjacency matrix) และใช้วิธีการยกกำลัง k เมทริกซ์ เพื่อหาจำนวนทางเดินที่มีความยาว k ในการเดินจากจุดหนึ่งไปยังอีกจุดหนึ่ง แต่วิธีดังกล่าวหากเราต้องการทราบจำนวนทางเดินที่มีความยาวมากๆ การยกกำลัง matrix หลายๆครั้งจะทำให้เกิดความยุ่งยาก ผมจึงได้พยายามแก้ปัญหานี้โดยใช้ความรู้ เรื่อง Adjacency matrix และ recurrence relation รวมถึงหลักการนับเบื้องต้นในการหาสมการความสัมพันธ์ดังกล่าวในกราฟเชิงเดียวแบบต่างๆดังนี้ 1. complete graph 2. cycle graph 3. path graph โดยให้อยู่ในรูปสมการความสัมพันธ์ระหว่าง จำนวนเส้นทางเดินกับ ความยาวและจุดเริ่มต้นกับจุดสิ้นสุด และนำความสัมพันธ์ระหว่างจำนวนทางเดินกับจำนวน endomorphism’s ไปประยุกต์ในการแก้ปัญหาการนับ endomorphism’s ในกราฟเหล่านี้ในบางกรณีด้วย