Algebraic connectivity a(G) = λ₂: second-smallest Laplacian eigenvalue. Fiedler (1973). Connected ⟺ λ₂ > 0. Larger λ₂ = harder to disconnect. Cheeger inequality: λ₂/2 ≤ h ≤ √(2λ₂). The Fiedler vector partitions the graph spectrally.
How to Use
Select graph:
- λ₂: Alg. conn.
- >0?: Connected
- Fiedler: Vector
Fiedler Vector
Eigenvector of λ₂: signs partition vertices into two groups. Optimal spectral cut! Used in spectral clustering, graph drawing, mesh partitioning. The most practical eigenvector in graph theory.
Bounds
0 ≤ λ₂ ≤ κ(G) ≤ δ(G). K_n: λ₂ = n. Path P_n: λ₂ = 2(1-cos(π/n)) ≈ 2π²/n². Cycle: λ₂ = 2(1-cos(2π/n)). Complete bipartite K_{a,b}: λ₂ = min(a,b).
Step-by-Step Instructions
- 1Select graph.
- 2Build Laplacian.
- 3Find λ₂.
- 4Check connectivity.
- 5Apply Cheeger.