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 ในกราฟเหล่านี้ในบางกรณีด้วย