ผลต่างระหว่างรุ่นของ "Sgt/lecture2"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 1 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 190: แถว 190:
 
ให้กราฟที่มีจำนวน <math>n</math> component ค่า eigenvalue ของ Laplacian matrix ลำดับที่หนึ่งจนถึงลำดับที่ <math>n</math> จะมีค่าเป็น 0
 
ให้กราฟที่มีจำนวน <math>n</math> component ค่า eigenvalue ของ Laplacian matrix ลำดับที่หนึ่งจนถึงลำดับที่ <math>n</math> จะมีค่าเป็น 0
  
 +
{{เริ่มบทพิสูจน์}}
 +
 +
ให้กราฟมี <math>n</math> ส่วน ให้ eigenvalue จำนวน <math>n</math> ตัวแรกมีค่าเป็น <math>0</math> และมี eigenvector ที่สอดคล้องกันคือ
 +
 +
:<math>
 +
\phi_i = \begin{cases}
 +
1 & \text{if node is in component } i \text{th} \\
 +
0 & \text{otherwise}
 +
\end{cases}
 +
</math>
 +
 +
จะเห็นว่า <math>0 \phi_i = L \phi_i</math>
 +
{{จบบทพิสูจน์}}
  
 
=== Eigenvalue ของกราฟบริบูรณ์ ===
 
=== Eigenvalue ของกราฟบริบูรณ์ ===

รุ่นแก้ไขปัจจุบันเมื่อ 11:09, 10 กุมภาพันธ์ 2558

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 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Rayleigh quotient และคุณสมบัติของ eigenvector, eigenvalue ลำดับที่ 2

Rayleigh quotient

นิยาม Rayleigh quotient สำหรับ vector x และ symmetric matrix M คือ โดยสังเกตว่าถ้า x เป็น eigenvector ของ M ที่สอดคล้องกับ eigenvalue จะได้ว่า เนื่องจาก

และเราจะพิสูจน์ทฤษฎีบทว่า

"ให้ เป็น symmetric matrix ถ้า เป็น non-zero vector ที่ทำให้ มีค่ามากที่สุด แล้ว จะเป็น eigenvector ของ ที่สอดคล้องกับ eigenvalue ที่มากที่สุด"


เราจะพิสูจน์โดยการใช้ Spectral theory (เนื้อหาครั้งที่ 1) ให้ M มี dimension ขนาด n (symmetric) ได้ว่า M มี eigenvalue และ eigenvector ที่สอดคล้องกับ เพื่อความสะดวก เราให้ว่า ||x|| = 1 และ |||| = 1 สำหรับทุก i และเราสามารถเขียน x ในรูป จากนั้นจึงคำนวณหาค่า Rayleigh quotient

จะเห็นได้ว่า Rayleigh quotient มีค่ามากที่สุดเป็น eigenvalue ที่ใหญ่ที่สุด และ vector x ที่ทำให้มีค่าดังกล่าวได้แก่ eigenvalue ของ M (พิจารณาที่ )

Littlebox.png

คุณสมบัติของ Eigenvalue กับกราฟ

ให้กราฟ ขนาด โหนดและ เป็น adjacency matrix ของ ถ้าสำหรับโหนดที่ ใดๆ เขียนแทนดีกรีด้วย นิยาม diagonal matrix () ดังนี้

และนิยาม Laplacian matrix () ว่า

ต่อไปนี้จะสนใจ eigenvalue จาก Laplacian matrix ของกราฟ

Eigenvalue ตัวแรกของกราฟใดๆ

"สำหรับกราฟ ใดๆ Laplacian matrix () จะมี eigenvalue (น้อยไปมาก) ลำดับที่หนึ่งเป็นศูนย์เสมอ"


สมมติให้ เป็นกราฟที่มีมีเส้นเชื่อมเพียงหนึ่งเส้น เราจะได้

สำหรับ vector ใดๆ คำนวณค่า ได้ดังนี้

ต่อมา พิจรณากราฟ ใดๆ ที่มีจำนวนเส้นเชื่อม เส้น โดยเราสามารถเขียน ได้ในรูป

โดยที่ สำหรับ แทน Laplacian matrix ของกราฟ ซึ่งเป็นกราฟย่อยจาก ที่มีเส้นเชื่อมเส้นที่ เพียงเส้นเดียว ดังนั้น

ให้ สำหรับทุกค่า จะได้ว่า

จากสมการ ในหัวข้อ Rayleigh quotient จะได้ว่า Rayleigh quotient มีค่าน้อยที่สุดเมื่อ โดยมี เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว

ดังนั้น สำหรับ Laplacian matrix ของกราฟ G ใดๆ

Littlebox.png

Eigenvalue ของกราฟต่อเนื่อง

"สำหรับกราฟ ใดๆ Laplacian matrix จะมี eigenvalue ลำดับที่สองไม่เท่ากับศูนย์ ก็ต่อเมื่อ G เป็นกราฟต่อเนื่อง"


Littlebox.png

Eigenvalue ของกราฟที่มี ส่วน

ให้กราฟที่มีจำนวน component ค่า eigenvalue ของ Laplacian matrix ลำดับที่หนึ่งจนถึงลำดับที่ จะมีค่าเป็น 0



ให้กราฟมี ส่วน ให้ eigenvalue จำนวน ตัวแรกมีค่าเป็น และมี eigenvector ที่สอดคล้องกันคือ

จะเห็นว่า

Littlebox.png

Eigenvalue ของกราฟบริบูรณ์

ให้กราฟริบูรณ์ (complete graph) จำนวน โหนด () ค่า eigenvalue ของ Laplacian matrix ลำดับที่สองจนถึงลำดับสุดท้าย จะมีค่าเป็น


พิสูจน์โดยให้

เลือก ที่ และเลือก ที่สอดคล้องกันดังนี้

จะเห็นว่า

ดังนั้น eigenvalue ลำดับที่สองเป็นต้นไปของกราฟบริบูรณ์จำนวน โหนดมีค่าเป็น

หมายเหตุ eigenvector ที่นำมาประกอบการพิสูจน์ ไม่จำเป็นต้องตั้งฉากกัน เพียงแค่แสดงให้เห็นว่ามี eigenvector ที่สอดคล้องกับ eigenvalue ได้ก็พอ

Littlebox.png