ผลต่างระหว่างรุ่นของ "Sgt/lecture5"
ไปยังการนำทาง
ไปยังการค้นหา
Supachawal (คุย | มีส่วนร่วม) |
Supachawal (คุย | มีส่วนร่วม) |
||
(ไม่แสดง 24 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
แถว 3: | แถว 3: | ||
(not yet finished) | (not yet finished) | ||
− | สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Cheeger Inequality | + | สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Cheeger Inequality ซึ่งสามารถใช้ในหา upper bound ของ cut ได้ด้วยคุณสมบัติของ eigenvalue ลำดับที่ 2 (<math>\gamma_2</math>) ของ normalized laplacian matrix ของ graph |
==Conductance== | ==Conductance== | ||
− | จาก lecture 3 ได้กล่าวถึง cut | + | จาก lecture 3 ได้กล่าวถึง isoperimetric inequality ว่าด้วย lower bound ของ cut ไปแล้ว [http://theory.cpe.ku.ac.th/wiki/index.php/Sgt/lecture3] นั้น |
− | + | สำหรับ 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" (<math>\phi(S)</math>) และ "conductance ของ graph" (<math>\phi(G)</math>) ดังต่อไปนี้ | ||
+ | :<math> | ||
+ | \begin{align} | ||
+ | \phi(S) &= \frac{|\partial(S)|}{min(d(S), d(V-S))} \\ | ||
+ | \phi(G) &= \min_{S \subset V}\phi(S) | ||
+ | \end{align} | ||
+ | </math> | ||
+ | |||
+ | {{กล่องทฤษฎีบท|<math>\phi(G) \leq \sqrt{2\gamma_2}</math>}} | ||
+ | |||
+ | <math>\gamma_2</math> หมายถึง eigenvalue ลำดับที่ 2 ของ normalized laplacian matrix (จะอธิบายในส่วนถัดไป) | ||
+ | |||
+ | ==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 (จะอธิบายในส่วนถัดไป)