ผลต่างระหว่างรุ่นของ "Sgt/lecture5"
ไปยังการนำทาง
ไปยังการค้นหา
Supachawal (คุย | มีส่วนร่วม) |
Supachawal (คุย | มีส่วนร่วม) |
||
| แถว 10: | แถว 10: | ||
นิยาม "conductance ของ subgraph" (<math>\phi(S)</math>) และ "conductance ของ graph" (<math>\phi(G)</math>) ดังต่อไปนี้ | นิยาม "conductance ของ subgraph" (<math>\phi(S)</math>) และ "conductance ของ graph" (<math>\phi(G)</math>) ดังต่อไปนี้ | ||
| − | |||
| − | |||
:<math> | :<math> | ||
\begin{align} | \begin{align} | ||
| − | \phi(S) &= \frac{|\partial(S)|}{min(d(S), d(V-S))} | + | \phi(S) &= \frac{|\partial(S)|}{min(d(S), d(V-S))} \\ |
\phi(G) &= \min_{S \subset V}\phi(S) \\ | \phi(G) &= \min_{S \subset V}\phi(S) \\ | ||
&\leq 2\gamma_2 | &\leq 2\gamma_2 | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
รุ่นแก้ไขเมื่อ 01:20, 21 พฤษภาคม 2558
บันทึกคำบรรยายวิชา Spectral graph theory นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง
(not yet finished)
สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Cheeger Inequality ซึ่งสามารถใช้ใน bound คุณสมบัติของกราฟเกี่ยวกับ cut ได้ด้วยคุณสมบัติของ eigenvalue ลำดับที่ 2 ของ normalized laplacian matrix ()
Conductance
จาก lecture 3 ได้กล่าวถึง cut และ isoperimetric ratio ไปแล้ว [1] สำหรับ unweighted undirected graph และ และ cut
นิยาม "conductance ของ subgraph" () และ "conductance ของ graph" () ดังต่อไปนี้
