8.4 Graph distance and diameter

Graph distances measure how far apart things are in networks. They help us understand connections, find central points, and see how spread out a network is. These concepts are crucial for analyzing everything from social media to transportation systems.

Calculating distances in graphs involves smart algorithms like Breadth-First Search and Dijkstra's. These methods help us find the shortest paths, central nodes, and overall network span. They're key to solving real-world problems in logistics, social networks, and urban planning.

Graph Distance Fundamentals

Concepts of graph metrics

• Graph distance measures shortest path between vertices counting edges traversed $d(u,v)$ (social networks, transportation routes)
• Eccentricity $e(v)$ determines maximum distance from vertex to any other vertex $e(v) = \max_{u \in V} d(v,u)$ (network diameter, worst-case scenarios)
• Radius $rad(G)$ identifies minimum eccentricity among all vertices $rad(G) = \min_{v \in V} e(v)$ (central nodes, optimal locations)
• Diameter $diam(G)$ represents maximum eccentricity across all vertices $diam(G) = \max_{v \in V} e(v)$ (network span, communication delays)

Calculation of vertex distances

• Breadth-First Search explores vertices in layers $O(V + E)$ time complexity (social network connections, web crawling)
• Dijkstra's algorithm uses priority queue for weighted graphs $O((V + E) \log V)$ time complexity (GPS navigation, network routing)
• Floyd-Warshall algorithm computes all-pairs shortest paths $O(V^3)$ time complexity (flight connections, supply chain optimization)

Advanced Graph Distance Concepts

Eccentricity and radius determination

• Eccentricity calculation runs shortest path algorithm from vertex to all others finding maximum distance (network extremities, resource distribution)
• Radius calculation computes eccentricity for all vertices identifying minimum value (central locations, emergency response centers)
• Center of graph comprises vertices with eccentricity equal to radius (optimal facility placement, distribution hubs)

Diameter computation and implications

• Diameter calculation methods:

  1. Brute force computes distances between all vertex pairs
  2. Efficient approach uses eccentricity of each vertex

• Diameter implications measure worst-case distance indicating overall connectivity (network performance, information dissemination)

• Diameter relationships:

  • Bounded by radius: Diameter ≤ 2 * radius
  • In trees equals longest path edge count (hierarchical structures, decision trees)

Applications of graph distances

• Network analysis identifies critical nodes optimizes resource distribution (supply chains, communication networks)
• Social network applications determine degrees of separation analyze information spread (viral marketing, influence propagation)
• Transportation planning optimizes routes minimizes travel times (urban planning, logistics optimization)
• Computer networks minimize data transmission latency design efficient topologies (internet infrastructure, distributed systems)
• Facility location problems determine optimal service placement minimize maximum distance (warehouse locations, public service accessibility)