Connectivity.md (2227B)
1 +++ 2 title = 'Connectivity' 3 template = 'page-math.html' 4 +++ 5 # Connectivity 6 7 - vertices u,v are connected if there is a (u,v) path between them 8 - graph is connected if all pairs of vertices are connected 9 - graph is k-connected if κ(G) ≥ k 10 - graph is k-edge-connected if λ(G) ≥ k 11 - graph is optimally connected if λ(G) = κ(G) = min { δ(v) | v ∈ V(G) } 12 - a component of G is a connected subgraph that isn’t contained in another connected subgraph of G 13 14 Vertex & edge cuts 15 16 - V* ⊂ V(G) is vertex cut if removing vertices V* disconnects the graph 17 - E* ⊂ E(G) is edge cut if removing edges E* disconnects the graph 18 - κ(G) is size of minimal vertex cut for G — the amount of vertices needed to disconnect G 19 - λ(G) is size of minimal edge cut for G — the amount of edges needed to disconnect G 20 - $\kappa_{G} \leq \lambda (G) \leq \min_{v \in V(G)} {\delta (v)}$ 21 - in english, min vertex cut ≤ min edge cut ≤ smallest degree in graph 22 23 Menger’s theorem: 24 25 - Let G be a connected graph, with u and v two non-adjacent vertices. 26 - formal: “The minimum size of a vertex cut disconnecting nonadjacent vertices u ≠ v equals the maximum size of a vertex-independent set P(u,v). The minimum size of an edge cut disconnecting vertices u ≠ v equals the maximum size of an edge-independent set P(u,v)." 27 - in english: the min number of vertices you need to remove to split vertices u and v into different components of the graph == the max number of paths from u to v that don’t share vertices. same shit for edges. 28 - [This is a good video explanation.](https://www.youtube.com/watch?v=dUAeleBMRCQ) 29 30 Harary graphs: 31 32 - k-connected graphs, of the form Hk,n 33 - forming a harary graph Hk,n: 34 - place n vertices around a circle 35 - if k is even — make each vertex adjacent to k/2 neighbours in each direction around circle 36 - if k is odd and n is even — make each vertex adjacent to (k-1)/2 neighbours in each direction, and diametrically opposite vertex 37 - if k is odd and n is odd — make each vertex adjacent to (k-1)/2. then index nodes by integers mod n, and connect node to integer+(n-1)/2 for 0≤integer≤(n-1)/2 38 - yes, one node will have an even degree — the one labelled (n-1)/2