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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 9: แถว 9:
 
สำหรับ 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> <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) = \frac{|\partial(S)|}{min(d(S), d(V-S))} </math>
  
นิยาม conductance ของ graph <math>\phi(G) = \min_{S \subset V}\phi(S) \lt_eq 2\gamma_2</math>
+
นิยาม conductance ของ graph  
 +
:<math>
 +
\begin{align}
 +
\phi(G) &= \min_{S \subset V}\phi(S) \\
 +
&\leq 2\gamma_2
 +
\end{align}
 +
</math>

รุ่นแก้ไขเมื่อ 01:12, 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 ซึ่งสามารถใช้ใน bound คุณสมบัติของกราฟเกี่ยวกับ cut ได้ด้วยคุณสมบัติของ eigenvalue ลำดับที่ 2 ของ normalized laplacian matrix ()

Conductance

จาก lecture 3 ได้กล่าวถึง cut และ isoperimetric ratio ไปแล้ว [1] ใน lecture นี้มีนิยามของ Conductance ดังนี้ สำหรับ unweighted undirected graph และ

นิยาม conductance ของ subgraph

นิยาม conductance ของ graph