Spectral Graph Theory
|
- บทนำและทบทวนพีชคณิตเชิงเส้น (ณัฐวุฒิ)
- คุณสมบัติของ Eigenvalue ต่อกราฟ (ธานี,ณัฐวุฒิ)
- คุณสมบัติของ Eigenvalue ต่อกราฟ[2] (ภัทร)
- คุณสมบัติของ Eigenvalue ลำดับที่สองบนกราฟต่างๆ (ธานี)
- Cheeger Inequality (ศุภชวาล)
- การทดลอง Cheeger Inequality และ Effective Resistance (ธานี)
- Random Walks และ Psuedo Random Generator (ศุภชวาล)
- Psuedo Random Generator[2] (ภัทร)
- Coding Theory และ Expander code (ธานี)
- Expander graph from Linear coding (ภัทร)
- Chebyshev polynomial (ศุภชวาล)
- Preconditioning (ธานี)
|
แก้ไขกล่องนี้ • แก้ไขสารบัญ
|
บันทึกคำบรรยายวิชา Spectral graph theory นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง
(not yet finished)
สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Cheeger Inequality ซึ่งสามารถใช้ในหา upper bound ของ cut ได้ด้วยคุณสมบัติของ eigenvalue ลำดับที่ 2 () ของ normalized laplacian matrix ของ graph
Conductance
จาก lecture 3 ได้กล่าวถึง isoperimetric inequality ว่าด้วย lower bound ของ cut ไปแล้ว [1] นั้น
สำหรับ unweighted undirected graph และ และ cut
นิยาม "conductance ของ subgraph" () และ "conductance ของ graph" () ดังต่อไปนี้