Sgt/lecture6

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
ยุบ

Spectral Graph Theory

  1. บทนำและทบทวนพีชคณิตเชิงเส้น (ณัฐวุฒิ)
  2. คุณสมบัติของ Eigenvalue ต่อกราฟ (ธานี,ณัฐวุฒิ)
  3. คุณสมบัติของ Eigenvalue ต่อกราฟ[2] (ภัทร)
  4. คุณสมบัติของ Eigenvalue ลำดับที่สองบนกราฟต่างๆ (ธานี)
  5. Cheeger Inequality (ศุภชวาล)
  6. การทดลอง Cheeger Inequality และ Effective Resistance (ธานี)
  7. Random Walks และ Psuedo Random Generator (ศุภชวาล)
  8. Psuedo Random Generator[2] (ภัทร)
  9. Coding Theory และ Expander code (ธานี)
  10. Expander graph from Linear coding (ภัทร)
  11. Chebyshev polynomial (ศุภชวาล)
  12. Preconditioning (ธานี)

แก้ไขกล่องนี้แก้ไขสารบัญ

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

สัปดาห์นี้ เราเรียนรู้ถึงการนำ linear algebra ไปใช้แก้ปัญหาทางฟิสิกส์

ให้ weighted undirected graph G = (V,E) ขนาด n nodes m edges แทนวงจรไฟฟ้า โดยให้ node แทนจุดต่างๆในวงจร
และ edge (u,v) แทนตัวต้านทาน โดยน้ำหนักของ edge เท่ากับ 1/ความต้านทาน

นิยาม Matrix 4 matrices ดังนี้

1. U เป็น m*n เมทริกซ์ โดยสำหรับทุก edge (x,y) , U(x,y) = 1 และ U(y,x) = -1

2. W เป็น m*m diagonal เมทริกซ์ โดย W(x,x) คือน้ำหนักของ edge ที่ x

3. เป็น vector ขนาด n โดย คือศักย์ไฟฟ้า ณ node x

4. i เป็น vector ขนาด m โดย i(x) คือกระแสไฟฟ้าที่ไหลบน edge ที่ i

จะได้ว่า

จากกฎทางไฟฟ้าทำให้ได้ว่า ณ จุดใดๆของวงจร กระแสไฟฟ้าเข้าจะเท่ากับกระแสไฟฟ้าออก

และเพื่อให้เข้าใกล้การใช้งานจริงมากยิ่งขึ้น เราจะนิยามเวคเตอร์