ผลต่างระหว่างรุ่นของ "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} | ||
แถว 19: | แถว 20: | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
+ | } | ||
<math>\gamma_2</math> หมายถึง eigenvalue ลำดับที่ 2 ของ normalized laplacian matrix (จะอธิบายในส่วนถัดไป) | <math>\gamma_2</math> หมายถึง eigenvalue ลำดับที่ 2 ของ normalized laplacian matrix (จะอธิบายในส่วนถัดไป) | ||
==Normalized Laplacian (<math>N</math>) == | ==Normalized Laplacian (<math>N</math>) == |
รุ่นแก้ไขเมื่อ 01:52, 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 (จะอธิบายในส่วนถัดไป)