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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 1 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 14: แถว 14:
 
\end{align}
 
\end{align}
 
</math>}}
 
</math>}}
 
{{เริ่มบทพิสูจน์}}
 
To be proved...
 
{{จบบทพิสูจน์}}
 
  
 
==Graphic Inequality==
 
==Graphic Inequality==
แถว 72: แถว 68:
 
คำนวณ <math>\frac{\sum\limits_{i=1}^{n}(x(i+1)-x(i))^2}{\sum\limits_{i=1}^{n}(x(i)^2}</math>  
 
คำนวณ <math>\frac{\sum\limits_{i=1}^{n}(x(i+1)-x(i))^2}{\sum\limits_{i=1}^{n}(x(i)^2}</math>  
  
จาก Courant–Fischer Theorem จะเห็นว่า <math>\lambda_2 = O(frac{1}{n^2})</math>
+
จาก Courant–Fischer Theorem จะเห็นว่า <math>\lambda_2 = O(\frac{1}{n^2})</math>
  
 
{{จบบทพิสูจน์}}
 
{{จบบทพิสูจน์}}
 
2.<math>\lambda_2(P_n) = \Omega(\frac{1}{n^2})</math>
 
2.<math>\lambda_2(P_n) = \Omega(\frac{1}{n^2})</math>
 
{{เริ่มบทพิสูจน์}}
 
{{เริ่มบทพิสูจน์}}
To be proved...
+
หาค่าคงที่ c ที่
 +
 
 +
<math>c \cdot P_n \succeq K_n </math> และเรารู้ว่า <math>K_n = \sum\limits_{i,j} G_{i,j}</math>
 +
 
 +
จึงได้ว่า
 +
:<math>
 +
\begin{align}
 +
\sum\limits_{i>j}(i-j)P_n &\succeq K_n \\
 +
\frac{n(n+1)(n-1)}{6}P_n &\succeq K_n \\
 +
\therefore \Omega(\frac{1}{n^2}) &\leq \lambda_2(P_2) \\
 +
\end{align}
 +
</math>
 +
 
 +
<math>\lambda_2(P_n) = \Omega(\frac{1}{n^2})</math>
 
{{จบบทพิสูจน์}}
 
{{จบบทพิสูจน์}}
  
แถว 85: แถว 94:
  
 
:<math>\Omega(\frac{1}{n\cdot log(n)} \leq \lambda_2(T_d) \leq \frac{2}{n-1})</math>
 
:<math>\Omega(\frac{1}{n\cdot log(n)} \leq \lambda_2(T_d) \leq \frac{2}{n-1})</math>
{{เริ่มบทพิสูจน์}}
+
โดยการใช้วิธีเดียวกับการพิสูจน์ด้านบน โดยสร้างเวคเตอร์ x ที่ x(root) = 0 และลูกฝั่งซ้ายทั้งหมดเป็น 1 ฝั่งขวาทั้งหมดเป็น -1
To be proved...
 
{{จบบทพิสูจน์}}
 

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

ในสัปดาห์นี้ เราได้พูดถึง Courant–Fischer Theorem

Courant–Fischer Theorem

ให้ A เป็น symmetric matrix ขนาด n ที่มี eigen value (สังเกตว่าเรียงสลับด้านกับ ในเลคเชอร์อื่นๆ)

เราจะได้ว่า

Graphic Inequality

เป็นการเปรียบเทียบกราฟโดยให้ sense ของการ "มากกว่า" "น้อยกว่า" เหมือนการเปรียบเทียบจำนวนจริง
ให้ A เป็น matrix ใดๆ เราเขียนแทนว่า A เป็น positive semi-definite ด้วย โดยนิยามดังนี้

และสำหรับ matrix A,B ใดๆ เราเขียน แทน โดยความสัมพันธ์นี้มีคุณสมบัติถ่ายทอด คือ

ทำนองเดียวกัน สำหรับกราฟ G,H ใดๆ เราเขียน แทน สังเกตว่า ถ้า H เป็น subgraph ของ G จะได้ว่า

และสำหรับจำนวนจริง c ใดๆเราเขียนแทน หมายถึง

จากนิยามข้างต้น เราจะได้คุณสมบัติว่า (ในเนื้อหาครั้งนี้ไม่มีการพิสูจน์ทฤษฎีบทนี้)

ถ้า G,H เป็นกราฟที่มีคุณสมบัติว่า จะได้ว่า เมื่อ หมายถึง eigen value ตัวที่ k ของกราฟ G

Path Inequality

ให้กราฟขนาด n โหนด แทนกราฟที่มีเส้นเชื่อมเดียว (1,n) และกราฟที่มีเส้นเชื่อม n-1 เส้น ตามลำดับ


พิจารณา vector x ขนาด n ใดๆ เราต้องการจะแสดงว่า

ให้ และนิยาม vector ขนาด n-1 เพิ่มดังนี้ และ

จากCauchy–Schwarz inequality ได้ว่า

ตามต้องการ

Littlebox.png

และเราจะแสดงให้เห็นว่า โดยประกอบด้วยสองขั้นตอน

1.


สร้างเวคเตอร์ x โดยให้ จะเห็นว่า x ตั้งฉากกับ

คำนวณ

จาก Courant–Fischer Theorem จะเห็นว่า

Littlebox.png

2.


หาค่าคงที่ c ที่

และเรารู้ว่า

จึงได้ว่า

Littlebox.png

จะมี ค่า d > 0 ที่ถ้า n มีขนาดมากพอ จะมี d-regular graph ที่

และสำหรับ Complete binary tree ที่มีความลึก d แทนด้วย เราจะได้ว่า

โดยการใช้วิธีเดียวกับการพิสูจน์ด้านบน โดยสร้างเวคเตอร์ x ที่ x(root) = 0 และลูกฝั่งซ้ายทั้งหมดเป็น 1 ฝั่งขวาทั้งหมดเป็น -1