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 {"type":"https://mediawiki.org/wiki/HyperSwitch/errors/unknown_error","method":"get","detail":"upstream connect error or disconnect/reset before headers. reset reason: connection termination","uri":"/wikimedia.org/v1/media/math/render/mml/6bcc33cbe608e07163d84cb9def27bf304735dd1"}$\phi (G)=min\limits _{S\subset V}^{\ }(\phi (S))$