ผลต่างระหว่างรุ่นของ "Sgt/lecture5"

รุ่นแก้ไขเมื่อ 00:57, 21 พฤษภาคม 2558

Spectral Graph Theory
บทนำและทบทวนพีชคณิตเชิงเส้น (ณัฐวุฒิ) เนื้อหา: Eigenvector, Eigenvalue คุณสมบัติของ Eigenvalue ต่อกราฟ (ธานี,ณัฐวุฒิ) เนื้อหา: ผลหาร Rayleigh, คุณสมบัติของเมตริกซ์ Laplacian ทดลอง: วาดกราฟจาก Eigenvector คุณสมบัติของ Eigenvalue ต่อกราฟ[2] (ภัทร) เนื้อหา: Eigen value properties คุณสมบัติของ Eigenvalue ลำดับที่สองบนกราฟต่างๆ (ธานี) เนื้อหา: Second eigen value Cheeger Inequality (ศุภชวาล) เนื้อหา: Cheeger Inequality การทดลอง Cheeger Inequality และ Effective Resistance (ธานี) เนื้อหา: Effective Resistance ทดลอง: หา cut ที่มีคุณสมบัติตรงกับ Cheeger Inequality Random Walks และ Psuedo Random Generator (ศุภชวาล) เนื้อหา: Random Walks Psuedo Random Generator[2] (ภัทร) เนื้อหา: Psuedo Random Generator Coding Theory และ Expander code (ธานี) เนื้อหา: Coding Theory Expander graph from Linear coding (ภัทร) เนื้อหา: Expander construction Chebyshev polynomial (ศุภชวาล) เนื้อหา: Chebyshev polynomial Preconditioning (ธานี) เนื้อหา: Preconditioning
แก้ไขกล่องนี้ • แก้ไขสารบัญ

บันทึกคำบรรยายวิชา 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 $\phi (G)=min\limits _{S\subset V}\phi (S)$

@@ แถว 7: / แถว 7: @@
 ==Conductance==
 จาก lecture 3 ได้กล่าวถึง cut และ isoperimetric ratio ไปแล้ว [http://theory.cpe.ku.ac.th/wiki/index.php/Sgt/lecture3#Terminology] ใน lecture นี้มีนิยามของ Conductance ดังนี้
-นิยาม สำหรับ unweighted undirected graph G = (V,E), <math>S \subseteq V</math> <math>\partial(S) = \{ (u,v) \in E, u \in S, v \notin S \}</math>
+สำหรับ unweighted undirected graph <math>G = (V,E)</math> และ <math>S \subset V</math> <math>\partial(S) = \{ (u,v) \in E, u \in S, v \notin S \}</math>
-กำหนดให้ conductance <math>\phi(S) = \frac{|\partial(S)|}{min(d(S), d(V-S))} </math>
+นิยาม conductance ของ subgraph <math>\phi(S) = \frac{|\partial(S)|}{min(d(S), d(V-S))} </math>
+นิยาม conductance ของ graph <math>\phi(G) = min\limits_{S \subset V}\phi(S) </math>

ผลต่างระหว่างรุ่นของ "Sgt/lecture5"

รุ่นแก้ไขเมื่อ 00:57, 21 พฤษภาคม 2558

Conductance

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ