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 ซึ่งสามารถใช้ใน bound คุณสมบัติของกราฟเกี่ยวกับ cut ได้ด้วยคุณสมบัติของ eigenvalue ลำดับที่ 2 ของ normalized laplacian matrix ()
Conductance
จาก lecture 3 ได้กล่าวถึง cut และ isoperimetric ratio ไปแล้ว [1] ใน lecture นี้มีนิยามของ Conductance ดังนี้
นิยาม สำหรับ unweighted undirected graph G = (V,E),
กำหนดให้ conductance