ผลต่างระหว่างรุ่นของ "Sgt/lecture5"
ไปยังการนำทาง
ไปยังการค้นหา
Supachawal (คุย | มีส่วนร่วม) |
Supachawal (คุย | มีส่วนร่วม) |
||
| แถว 8: | แถว 8: | ||
จาก lecture 3 ได้กล่าวถึง cut และ isoperimetric ratio ไปแล้ว [http://theory.cpe.ku.ac.th/wiki/index.php/Sgt/lecture3#Terminology] ใน lecture นี้มีนิยามของ Conductance ดังนี้ | จาก lecture 3 ได้กล่าวถึง cut และ isoperimetric ratio ไปแล้ว [http://theory.cpe.ku.ac.th/wiki/index.php/Sgt/lecture3#Terminology] ใน lecture นี้มีนิยามของ Conductance ดังนี้ | ||
นิยาม สำหรับ unweighted undirected graph G = (V,E), <math>S \subseteq V</math> <math>\partial(S) = \{ (u,v) \in E, u \in S, v \notin S \}</math> | นิยาม สำหรับ unweighted undirected graph G = (V,E), <math>S \subseteq V</math> <math>\partial(S) = \{ (u,v) \in E, u \in S, v \notin S \}</math> | ||
| − | กำหนดให้ conductance <math>\phi(S) = \frac{|\partial(S)|}{min(d(S), d(V-S)} </math> | + | กำหนดให้ conductance <math>\phi(S) = \frac{|\partial(S)|}{min(d(S), d(V-S))} </math> |
รุ่นแก้ไขเมื่อ 00:46, 21 พฤษภาคม 2558
บันทึกคำบรรยายวิชา Spectral graph theory นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง
(not yet finished)
สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Cheeger Inequality ซึ่งสามารถใช้ใน bound คุณสมบัติของกราฟเกี่ยวกับ cut ได้ด้วยคุณสมบัติของ eigenvalue ลำดับที่ 2 ของ normalized laplacian matrix ()
Conductance
จาก lecture 3 ได้กล่าวถึง cut และ isoperimetric ratio ไปแล้ว [1] ใน lecture นี้มีนิยามของ Conductance ดังนี้ นิยาม สำหรับ unweighted undirected graph G = (V,E), กำหนดให้ conductance
