2 min read•july 24, 2024
Connectivity in graphs measures how well-connected a structure is. It's crucial for understanding network strength and weak points. Vertex and tell us the minimum elements needed to disconnect a graph.
Calculating connectivity involves algorithms like Ford-Fulkerson and max-flow min-cut. The relationship between connectivity types is expressed as κ(G) ≤ λ(G) ≤ δ(G), with providing key insights into graph structure and vulnerability.
(κ(G)) represents minimum vertices removed to disconnect graph measures vertex-disjoint paths between any two vertices (complete graphs κ(G) = n - 1, n = number of vertices)
Edge connectivity (λ(G)) represents minimum edges removed to disconnect graph measures edge-disjoint paths between any two vertices (complete graphs λ(G) = n - 1, n = number of vertices)
Connectivity relates to graph structure higher connectivity indicates robust well- lower connectivity suggests vulnerable points (bridges, cut-vertices)
Vertex connectivity calculation employs κ(G) equals minimum vertex-disjoint paths between non-adjacent vertices uses Ford-Fulkerson algorithm converting graph to finding maximum flow
Edge connectivity calculation utilizes finds minimum cut in graph applies global min-cut algorithms (Karger's, Stoer-Wagner)
Manual calculation steps
Inequality relationship where κ(G) vertex connectivity λ(G) edge connectivity δ(G) minimum degree of graph
Implications vertex connectivity always less than or equal to edge connectivity edge connectivity always less than or equal to minimum degree removing edges generally less disruptive than removing vertices
Special cases include trees κ(G) = λ(G) = δ(G) = 1 and complete graphs κ(G) = λ(G) = δ(G) = n - 1
Whitney's theorem states for any graph G with at least three vertices
Proof outline demonstrates removing λ(G) - 1 edges cannot disconnect graph shows removing λ(G) vertices always disconnects graph concludes κ(G) ≤ λ(G)
Key proof steps use contradiction to prove κ(G) ≤ λ(G) show removing δ(G) - 1 edges from vertex cannot isolate it conclude λ(G) ≤ δ(G)
Significance provides bounds for connectivity measures helps estimate graph vulnerability and robustness (network reliability, fault tolerance)