Sgt/lecture5

บันทึกคำบรรยายวิชา Spectral graph theory นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

(not yet finished)

สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Cheeger Inequality ซึ่งสามารถใช้ใน bound คุณสมบัติของกราฟเกี่ยวกับ cut ได้ด้วยคุณสมบัติของ eigenvalue ลำดับที่ 2 ของ normalized laplacian matrix ($\gamma _{2}$)

Conductance

จาก lecture 3 ได้กล่าวถึง cut และ isoperimetric ratio ไปแล้ว [1] ใน lecture นี้มีนิยามของ Conductance ดังนี้ สำหรับ unweighted undirected graph $G=(V,E)$ และ $S\subset V$ $\partial (S)=\{(u,v)\in E,u\in S,v\notin S\}$

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

นิยาม conductance ของ graph

${\begin{aligned}\phi (G)&=\min _{S\subset V}\phi (S)\\&\leq 2\gamma _{2}\end{aligned}}$