Sgt/lecture5

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

(not yet finished)

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

Conductance

จาก lecture 3 ได้กล่าวถึง isoperimetric inequality ว่าด้วย lower bound ของ cut ไปแล้ว [1] นั้น สำหรับ unweighted undirected graph และ และ cut

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 1023457183
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Tue, 13 Jan 2026 17:34:01 GMT


Sensitive client information

IP address: 158.108.32.49

$\partial (S)=\{(u,v)\in E,u\in S,v\notin S\}$

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