Graph diameter diam(G) = max d(u,v): the longest shortest-path distance. Measures how 'spread out' a graph is. diam(K_n)=1, diam(path P_n)=n-1, diam(cycle C_n)=⌊n/2⌋. For disconnected G: diam=∞.
How to Use
Select graph:
- Diameter: Max distance
- Pair: Diametral pair
- Compare: To radius
Bounds
rad(G) ≤ diam(G) ≤ 2·rad(G). For trees: diam = longest path. For regular graphs: diam ≤ ⌊log n / log(d-1)⌋ approximately. Small-world networks have diam ∝ log n.
Applications
Network design (worst-case communication delay), social networks (six degrees of separation = diameter ≈ 6), protein interaction networks, transportation (longest necessary trip). Small diameter = efficient network.
Step-by-Step Instructions
- 1Select graph.
- 2Compute diameter.
- 3Find diametral pair.
- 4Compare to radius.
- 5Check bounds.