Connectivity.html (3675B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.1.1 (456663)"/><meta name="keywords" content="ng"/><meta name="altitude" content="-0.6527782082557678"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 10:01:04 +0000"/><meta name="latitude" content="52.33451044149249"/><meta name="longitude" content="4.866744062922999"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 18:21:52 +0000"/><title>Connectivity</title></head><body><div>Connectivity:</div><ul><li><div>vertices u,v are connected if there is a (u,v) path between them</div></li><li><div>graph is connected if all pairs of vertices are connected</div></li><li><div>graph is k-connected if κ(G) ≥ k</div></li><li><div>graph is k-edge-connected if λ(G) ≥ k</div></li><li><div>graph is optimally connected if λ(G) = κ(G) = min { δ(v) | v ∈ V(G) }</div></li><li><div>a component of G is a connected subgraph that isn’t contained in another connected subgraph of G</div></li></ul><div><br/></div><div>Vertex & edge cuts</div><ul><li><div>V* ⊂ V(G) is vertex cut if removing vertices V* disconnects the graph</div></li><li><div>E* ⊂ E(G) is edge cut if removing edges E* disconnects the graph</div></li><li><div>κ(G) is size of minimal vertex cut for G — the amount of vertices needed to disconnect G</div></li><li><div>λ(G) is size of minimal edge cut for G — the amount of edges needed to disconnect G</div></li><li><div><span style="font-size: 18px;" 4 /><img src="Connectivity.resources/665E9A03-7A1F-4FD2-8546-EC809CB11832.png" height="21" width="258"/></div></li><ul><li><div>in english, min vertex cut ≤ min edge cut ≤ smallest degree in graph</div></li></ul></ul><div><br/></div><div>Menger’s theorem:</div><ul><li><div>Let G be a connected graph, with u and v two non-adjacent vertices.</div></li><li><div>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)."</div></li><li><div>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.</div></li><li><div><a href="https://www.youtube.com/watch?v=dUAeleBMRCQ">This is a good video explanation.</a></div></li></ul><div><br/></div><div>Harary graphs:</div><ul><li><div>k-connected graphs, of the form H<span style="vertical-align: sub;">k,n</span></div></li><li><div>forming a harary graph H<span style="vertical-align: sub;">k,n</span>:</div></li><ul><li><div>place n vertices around a circle</div></li><li><div>if k is even — make each vertex adjacent to k/2 neighbours in each direction around circle</div></li><li><div>if k is odd and n is even — make each vertex adjacent to (k-1)/2 neighbours in each direction, and diametrically opposite vertex</div></li><li><div>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</div></li><ul><li><div>yes, one node will have an even degree — the one labelled (n-1)/2</div></li></ul></ul></ul><div><br/></div></body></html>