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