ดูต้นฉบับสำหรับ Sgt/lecture5

<noinclude>{{Sgt/เนื้อหา}}</noinclude>
{{หัวคำบรรยาย|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 <math>G = (V,E)</math> และ <math>S \subset V</math> <math>\partial(S) = \{ (u,v) \in E, u \in S, v \notin S \}</math> 

นิยาม conductance ของ subgraph <math>\phi(S) = \frac{|\partial(S)|}{min(d(S), d(V-S))} </math>

นิยาม conductance ของ graph <math>\phi(G) = min_{S \subset V}\phi(S) </math>