Sgt/lecture1

บันทึกคำบรรยายวิชา Spectral graph theory นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

สัปดาห์แรกของ Spectral Graph Theory เป็นการเกริ่นนำความรู้พื้นฐานที่จะใช้ในวิชานี้ ซึ่งประกอบไปด้วยการทำความรู้จักกับ eigenvector, eigenvalue และ spectral theory

Spectral Theory

ให้เมทริกซ์ M ที่มีมิติ $n\times n$ และ M = M^{\top} (นั่นคือ เป็น เมทริกซ์สมมาตร) แล้ว ได้ว่ามี eigenvalue จำนวน $n$ ตัวดังนี้ $\lambda _{1}\leq \lambda _{2}\leq \ldots \leq \lambda _{n}$ (นั่นคือ เรียงจากน้อยไปมาก) และมี eigenvector $\phi _{i}$ ที่สอดคล้องกับ eigenvalue $\lambda _{i}$ โดยที่ $\lambda _{i}\cdot \lambda _{j}=0$ สำหรับ $i\neq j$ (นั่นคือ eigenvector ทุกตัวตั้งฉากกัน)