Sgt/lecture3

เนื้อหาในสัปดาห์นี้ จะเป็นความเกี่ยงเนื่องของ eigen value ลำดับที่ 2 กับกราฟ และบทพิสูจน์

Intuitive of Rayleight Quotient term numerator

จาก

$R(M,x)={\frac {x^{T}Mx}{x^{T}x}}$

สังเกตว่า

$x^{T}Lx=\sum \limits _{(u,v)}(x(u)-x(v))^{2}$

ถ้าเรามองว่า $x(u)$ คือการเปลี่ยนมิติ ของจุดจากกราฟมายังเส้นตรงแล้ว ราคาที่เพิ่มขึ้นจาก เส้นเชื่อมแต่ละเส้น จะเท่ากับระยะห่างของจุดปลายของเส้นเชื่อมนั้นบนเส้นตรงดังกล่าว

Terminology

สำหรับกราฟ $G=(V,E)$ และเซ็ตของปม $S\subseteq V$ เราจะนิยาม $\partial (S)=\{(u,v)\in E,u\in S,v\in V-S\}$ เป็นขนาดของคัท และ อัตราการขยายตัวของปริมาตรผ่านทางเส้นเชื่อม

Isoperimetric Inequality

Isoperimetric ratio of vertices set $\theta (S)={\frac {|\partial (S)|}{|S|}}$

Isoperimetric ratio of graph $\theta (G)=min_{S,|S|<=n/2}\theta (S)$