จำนวนทางเดิน (Walk) ในกราฟนั้น เราสามารถหาได้ด้วยวิธีต่างๆมากมาย และมีวิธีหนึ่งที่น่าสนใจคือการแปลงกราฟให้อยู่ในรูปของ เมทริกซ์ประชิด (adjacency matrix) และใช้วิธีการยกกำลัง k เมทริกซ์ เพื่อหาจำนวนทางเดินที่มีความยาว k ในการเดินจากจุดหนึ่งไปยังอีกจุดหนึ่ง แต่วิธีดังกล่าวหากเราต้องการทราบจำนวนทางเดินที่มีความยาวมากๆ การยกกำลัง matrix หลายๆครั้งจะทำให้เกิดความยุ่งยาก ผมจึงได้พยายามแก้ปัญหานี้โดยใช้ความรู้ เรื่อง Adjacency matrix และ recurrence relation รวมถึงหลักการนับเบื้องต้นในการหาสมการความสัมพันธ์ดังกล่าวในกราฟเชิงเดียวแบบต่างๆดังนี้ 1. complete graph 2. cycle graph 3. path graph โดยให้อยู่ในรูปสมการความสัมพันธ์ระหว่าง จำนวนเส้นทางเดินกับ ความยาวและจุดเริ่มต้นกับจุดสิ้นสุด และนำความสัมพันธ์ระหว่างจำนวนทางเดินกับจำนวน endomorphism’s ไปประยุกต์ในการแก้ปัญหาการนับ endomorphism’s ในกราฟเหล่านี้ในบางกรณีด้วย
สถาบันส่งเสริมการสอนวิทยาศาสตร์และเทคโนโลยี (สสวท.) กระทรวงศึกษาธิการ เป็นหน่วยงานของรัฐที่ไม่แสวงหากำไร ได้จัดทำเว็บไซต์คลังความรู้ SciMath เพื่อส่งเสริมการสอนวิทยาศาสตร์ คณิตศาสตร์และเทคโนโลยีทุกระดับการศึกษา โดยเน้นการศึกษาขั้นพื้นฐานเป็นหลัก หากท่านพบว่ามีข้อมูลหรือเนื้อหาใด ๆ ที่ละเมิดทรัพย์สินทางปัญญาปรากฏอยู่ในเว็บไซต์ โปรดแจ้งให้ทราบเพื่อดำเนินการแก้ปัญหาดังกล่าวโดยเร็วที่สุด
The Institute for the Promotion of Teaching Science and Technology (IPST), Ministry of Education, a non-profit organization under the Thai government, developed SciMath as a website that provides educational resources in Science, Mathematics and Technology. IPST invites visitors to use its online resources for personal, educational and other non-commercial purpose. If there are any problems, please contact us immediately.
Copyright © 2018 SCIMATH :: คลังความรู้ SciMath. Terms and Conditions. Privacy. , All Rights Reserved.
อีเมล: This email address is being protected from spambots. You need JavaScript enabled to view it. (ให้บริการในวันและเวลาราชการเท่านั้น)