ผลต่างระหว่างรุ่นของ "Sgt/lecture5"
ไปยังการนำทาง
ไปยังการค้นหา
Tanee (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย '<noinclude>{{Sgt/เนื้อหา}}</noinclude> {{หัวคำบรรยาย|Spectral graph theory}}') |
Supachawal (คุย | มีส่วนร่วม) |
||
| แถว 1: | แถว 1: | ||
<noinclude>{{Sgt/เนื้อหา}}</noinclude> | <noinclude>{{Sgt/เนื้อหา}}</noinclude> | ||
{{หัวคำบรรยาย|Spectral graph theory}} | {{หัวคำบรรยาย|Spectral graph theory}} | ||
| + | (not yet finished) | ||
| + | |||
| + | สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Cheeger Inequality ซึ่งสามารถใช้ใน bound คุณสมบัติของกราฟเกี่ยวกับ cut ได้ด้วยคุณสมบัติของ eigenvalue ลำดับที่ 2 ของ normalized laplacian matrix (<math>\gamma_2</math>) | ||
| + | |||
| + | ==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> | ||
| + | กำหนดให้ conductance <math>\phi(S) = \frac{|\partial(S)|}{min(d(S), d(V-S)} </math> | ||
รุ่นแก้ไขเมื่อ 00:45, 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
