Sgt/lecture6

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

สัปดาห์นี้ เราเรียนรู้ถึงการนำ linear algebra ไปใช้แก้ปัญหาทางฟิสิกส์

ให้ weighted undirected graph G = (V,E) ขนาด n nodes m edges แทนวงจรไฟฟ้า โดยให้ node แทนจุดต่างๆในวงจร
และ edge (u,v) แทนตัวต้านทาน โดยน้ำหนักของ edge เท่ากับ 1/ความต้านทาน

นิยาม Matrix 4 matrices ดังนี้

1. U เป็น m*n เมทริกซ์ โดยสำหรับทุก edge (x,y) , U(x,y) = 1 และ U(y,x) = -1

2. W เป็น m*m diagonal เมทริกซ์ โดย W(x,x) คือน้ำหนักของ edge ที่ x

3. ${\bar {v}}$ เป็น vector ขนาด n โดย ${\bar {v}}(x)$ คือศักย์ไฟฟ้า ณ node x

4. i เป็น vector ขนาด m โดย i(x) คือกระแสไฟฟ้าที่ไหลบน edge ที่ i

จะได้ว่า $i=WU{\bar {v}}$

จากกฎทางไฟฟ้าทำให้ได้ว่า ณ จุดใดๆของวงจร กระแสไฟฟ้าเข้าจะเท่ากับกระแสไฟฟ้าออก

และเพื่อให้เข้าใกล้การใช้งานจริงมากยิ่งขึ้น เราจะนิยามเวคเตอร์ $i_{ext}$ โดย ค่าของเวคเตอร์นี้ที่โหนดใดๆ หมายถึงค่าของกระแส ที่ไหลเข้า/ออก จากกราฟ โดยผ่านโหนดนั้นๆ

จะเห็นว่า $i_{ext}=U^{T}i=U^{T}WUv$ ซึ่ง laplacian ของ G นั้น มีค่าดังนี้

$L_{G}=U^{T}WU$ จึงสามารถเขียนได้ในรูป $i_{ext}=L_{G}v$

ถ้าให้ $L^{+}$ เป็น pseudo-inverse ของ L เราจะสามารถหา effective resistance ระหว่างจุด a,b ของกราฟ G ได้ด้วยสมการ

$i_{ext}L^{+}i_{ext}$ เมื่อกำหนดให้ $i_{ext}(a)=1,i_{ext}(b)=-1$ และเป็นศูนย์ที่จุดอื่น