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 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง
เนื้อหาในสัปดาห์นี้ จะเป็นความเกี่ยงเนื่องของ eigen value ลำดับที่ 2 กับกราฟ และบทพิสูจน์
Intuitive of Rayleight Quotient term numerator
จาก
สังเกตว่า
ถ้าเรามองว่า คือการเปลี่ยนมิติ ของจุดจากกราฟมายังเส้นตรงแล้ว ราคาที่เพิ่มขึ้นจาก เส้นเชื่อมแต่ละเส้น จะเท่ากับระยะห่างของจุดปลายของเส้นเชื่อมนั้นบนเส้นตรงดังกล่าว
Terminology
สำหรับกราฟ และเซ็ตของปม
เราจะนิยาม
เป็นขนาดของคัท และ อัตราการขยายตัวของปริมาตรผ่านทางเส้นเชื่อม
Isoperimetric Inequality
Isoperimetric ratio of vertices set
Isoperimetric ratio of graph
ณ จุดนี้ เราจะพิจารณาขอบล่างของ เทียบกับ โดยจะพิจารณาขอบบน ซึ่งก็คือ Cheeger Inequality ใน lecture ครั้งถัดไป
"For every "
จาก Rayleight Quotient เรารู้ว่า
แสดงว่า ถ้าเราหยิบ vector ใด ๆ ซึ่งไม่ใช่ 0 ที่ตั้งฉากกับ vector 1 มา เราสามารถนำมาบอกขอบเขตของ ได้เสมอ
พิจารณา characteristic vector โดย
สังเกตว่า แต่ ไม่ตั้งฉากกับ vector
พิจารณา
สังเกตว่า
จากนั้นเราจะพิจารณาผลของ
โดย
และ
ดังนั้น
The Adjacency Matrix
กำหนดให้ A เป็น adjacency matrix ของกราฟ โดยถ้าเรานำ vector x ไปคูณ ผลลัพธ์ที่ได้คือ
พิจารณา regular graph G ที่มี degree d เราสามารถหาความสัมพันธ์ระหว่าง laplacian matrix กับ adjacency matrix ได้โดย
ถ้า และ เป็น eigen value และ eigen vector ที่สอดคล้องกันใน L แล้ว
ได้ว่า และ เป็น eigen value และ eigen vector ที่สอดคล้องกันใน A
สังเกตว่าถ้ากราฟเป็น regular แล้ว eigen vector ของ L กับ A จะเป็นชุดเดียวกัน แต่มี eigen value ต่างกัน
กำหนดให้ เป็น eigen value ของ A
เมื่อกราฟ G เป็น regular ได้ว่า