Sgt/lecture5

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

(not yet finished)

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

Conductance

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