ผลต่างระหว่างรุ่นของ "Sgt/lecture5"
ไปยังการนำทาง
ไปยังการค้นหา
Supachawal (คุย | มีส่วนร่วม) |
Supachawal (คุย | มีส่วนร่วม) |
||
| แถว 14: | แถว 14: | ||
\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\sqrt{2\gamma_2} | + | &\leq\sqrt{2\gamma_2} &gamma_2 หมายถึง eigenvalue ลำดับที่ 2 ของ normalized laplacian matrix (จะอธิบายในส่วนถัดไป) |
\end{align} | \end{align} | ||
</math> | </math> | ||
| + | ==Normalized Laplacian (<math>N</math>) == | ||
รุ่นแก้ไขเมื่อ 01:45, 21 พฤษภาคม 2558
บันทึกคำบรรยายวิชา 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" () ดังต่อไปนี้
