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] สำหรับ unweighted undirected graph $G=(V,E)$ และ $S\subset V$ และ cut $\partial (S)=\{(u,v)\in E,u\in S,v\notin S\}$

นิยาม "conductance ของ subgraph" ($\phi (S)$) และ "conductance ของ graph" ($\phi (G)$) ดังต่อไปนี้

${\begin{aligned}\phi (S)&={\frac {|\partial (S)|}{min(d(S),d(V-S))}}\\\phi (G)&=\min _{S\subset V}\phi (S)\\&\leq 2\gamma _{2}\end{aligned}}$