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

รุ่นแก้ไขเมื่อ 00:58, 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))$

รุ่นแก้ไขเมื่อ 00:57, 21 พฤษภาคม 2558 (ดูต้นฉบับ) Supachawal (คุย \| มีส่วนร่วม) ← การแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 00:58, 21 พฤษภาคม 2558 (ดูต้นฉบับ) Supachawal (คุย \| มีส่วนร่วม) การแก้ไขถัดไป →
แถว 11:		แถว 11:
	นิยาม conductance ของ subgraph <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>	+	นิยาม conductance ของ graph <math>\phi(G) = min\limits_{S \subset V}(\phi(S)) </math>

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

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

Conductance

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

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

เนมสเปซ

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

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ