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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 17 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 3: แถว 3:
 
(not yet finished)
 
(not yet finished)
  
สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Cheeger Inequality ซึ่งสามารถใช้ใน bound คุณสมบัติของกราฟเกี่ยวกับ cut ได้ด้วยคุณสมบัติของ eigenvalue ลำดับที่ 2 ของ normalized laplacian matrix (<math>\gamma_2</math>)
+
สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Cheeger Inequality ซึ่งสามารถใช้ในหา upper bound ของ cut ได้ด้วยคุณสมบัติของ eigenvalue ลำดับที่ 2 (<math>\gamma_2</math>) ของ normalized laplacian matrix ของ graph
  
 
==Conductance==
 
==Conductance==
จาก lecture 3 ได้กล่าวถึง cut และ isoperimetric ratio ไปแล้ว [http://theory.cpe.ku.ac.th/wiki/index.php/Sgt/lecture3#Terminology] ใน lecture นี้มีนิยามของ Conductance ดังนี้
+
จาก lecture 3 ได้กล่าวถึง isoperimetric inequality ว่าด้วย lower bound ของ cut ไปแล้ว [http://theory.cpe.ku.ac.th/wiki/index.php/Sgt/lecture3] นั้น
สำหรับ unweighted undirected graph <math>G = (V,E)</math> และ <math>S \subset V</math> <math>\partial(S) = \{ (u,v) \in E, u \in S, v \notin S \}</math>  
+
สำหรับ unweighted undirected graph <math>G = (V,E)</math> และ <math>S \subset V</math> และ cut <math>\partial(S) = \{ (u,v) \in E, u \in S, v \notin S \}</math>  
  
นิยาม conductance ของ subgraph <math>\phi(S) = \frac{|\partial(S)|}{min(d(S), d(V-S))} </math>
+
นิยาม "conductance ของ subgraph" (<math>\phi(S)</math>) และ "conductance ของ graph" (<math>\phi(G)</math>) ดังต่อไปนี้
 +
:<math>
 +
\begin{align}
 +
\phi(S) &= \frac{|\partial(S)|}{min(d(S), d(V-S))} \\
 +
\phi(G) &= \min_{S \subset V}\phi(S)
 +
\end{align}
 +
</math>
  
นิยาม conductance ของ graph <math>\phi(G) = \min_{S \subset V}\phi(S) <= 2\gamma_2</math>
+
{{กล่องทฤษฎีบท|<math>\phi(G) \leq \sqrt{2\gamma_2}</math>}}
 +
 
 +
<math>\gamma_2</math> หมายถึง eigenvalue ลำดับที่ 2 ของ normalized laplacian matrix (จะอธิบายในส่วนถัดไป)
 +
 
 +
==Normalized Laplacian (<math>N</math>) ==

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

(not yet finished)

สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Cheeger Inequality ซึ่งสามารถใช้ในหา upper bound ของ cut ได้ด้วยคุณสมบัติของ eigenvalue ลำดับที่ 2 () ของ normalized laplacian matrix ของ graph

Conductance

จาก lecture 3 ได้กล่าวถึง isoperimetric inequality ว่าด้วย lower bound ของ cut ไปแล้ว [1] นั้น สำหรับ unweighted undirected graph และ และ cut

นิยาม "conductance ของ subgraph" () และ "conductance ของ graph" () ดังต่อไปนี้

หมายถึง eigenvalue ลำดับที่ 2 ของ normalized laplacian matrix (จะอธิบายในส่วนถัดไป)

Normalized Laplacian ()