ผลต่างระหว่างรุ่นของ "Sgt/lecture5"
ไปยังการนำทาง
ไปยังการค้นหา
Supachawal (คุย | มีส่วนร่วม) |
Supachawal (คุย | มีส่วนร่วม) |
||
| แถว 6: | แถว 6: | ||
==Conductance== | ==Conductance== | ||
| − | จาก lecture 3 ได้กล่าวถึง cut และ isoperimetric ratio ไปแล้ว [http://theory.cpe.ku.ac.th/wiki/index.php/Sgt/lecture3#Terminology] | + | จาก lecture 3 ได้กล่าวถึง cut และ isoperimetric ratio ไปแล้ว [http://theory.cpe.ku.ac.th/wiki/index.php/Sgt/lecture3#Terminology] |
| − | สำหรับ 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> และ cut <math>\partial(S) = \{ (u,v) \in E, u \in S, v \notin S \}</math> |
| − | นิยาม conductance ของ subgraph | + | นิยาม "conductance ของ subgraph" (<math>\phi(S)</math>) และ "conductance ของ graph" (<math>\phi(G)</math>) ดังต่อไปนี้ |
| − | <math>\phi(S) | + | <math></math> |
| − | + | :<math> | |
\begin{align} | \begin{align} | ||
| + | \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:19, 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" () ดังต่อไปนี้
