2 Connectivity and Spanning Trees Graphs are often used to model various interconnecting networks, such as transport, pipe, or computer networks. In such models, one usually needs or wants to get from any place to any other place..., which naturally leads to the study of their "connectivity". Brief outline of this lecture • Exploring a graph, basic search algorithms - BFS and DFS. • Connectivity - the definition, walks and connected components. • The MST problem, another search algorithm (Jarník/Prim). • Higher levels of connectivity, Menger's theorem, 2-connected graphs. • Connectivity in directed graphs, strong components. Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees 2.0 Exploring a Graph How can one read a graph? • Being humans, we look at a picture... • Being a computer, then what? Algorithms need to employ local-search routines on huge input graphs. □ • We are going to present a general scheme of searching through a graph. Petr Hliněný. Fl MU Brno. 2014 2.1 Exploring a Graph: a general Graph Search Scheme This meta-algorithm works with the following data states and structures: □ • A vertex: having one of the states ... - initial - assigned at the beginning, - discovered - after being found along an edge (stored for further processing), - finished - after checking and/or processing all the incident edges. - (Can also be "post-processed", after finishing all of its descendants.) □ • An edge: having one of the states ... - initial - assigned at the beginning, - processed - after it has been processed at one of its endvertices. □ • Stack (depository): is a supplementary data structure (a set) which - keeps all the discovered vertices, until they have been finished, and - stores an access edge for every discovery of a vertex (can be multiple). □ Graph search has many variants mostly given by the way vertices are picked from the depository. For greater generality, the scheme records vertices together with their access edges. Spec, programming tasks can be performed at each vertex or edge of G while processing them. Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees Algorithm 2.1. Searching through a connected graph G. This algorithm visits and processes every vertex and edge of a connected graph G. state [ all vertices and edges ofGI «— initial; stack U «— {(0,vo)}, for any starting vertex vo of G; search tree T «— 0; while (U ^ 0) { choose (e,v) e U; U ^U\{(e,v)>; if (e^0) PROCESS (e; v) ; if (state [v] ^ finished) { foreach (edge f incident with v) { w «— i7?e opposite vertex of "f — vw"; if (state [w] ^ finished) { state [w] ^discovered; U U{(f,w)>; > > PRQCESS(v;e); state [v] «— finished; T U{e,v>; G /S finistlGCl' *íProcfiázenísouvishjmgrafem * 3 state = stau, stackjdepositoni = úscHovna Petr Hlinený, Fl MU Brno, 2014 4/33 Fl: MA010: Connectivity and Spanning trees Correctness of the search scheme Theorem 2.2. Let G be a connected graph and t>o G V(G) an arbitrary vertex. Then Algorithm 2.1 on G, when started from vq, processes all the vertices and edges of G.u Proof. 1. Every element of G (vertex or edge) that gets into U will event, be processed: choose (e,v) e U; if (e/ 0) PROCESS (e); if (state [v] / finished) { .. PROCESS(v); ...} □ 2. If an edge / — vw G E(G) gets into U, then both ends v, w will be processed: if (state[w] ^finished) { ... U U{(f,w)}; } Hence v already is processed at this moment and w will be processed by 1. □ 3. Assume an edge / e E(G) that never gets into U. By connectivity of G, one may choose / closest possible to vq, and so some h G E(G) sharing a vertex v with / gets in; (h,v) G U. However, then foreach (edge f incident with v) { ... U ^—U U{(f,w)}; } a contradiction to the assumption that / never gets into U. ^ Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees Correctness of the search scheme, II Various applications of the graph search scheme, moreover, use the outcome T and refer to it as to the search tree of G. To be math, precise, we have to justify this fact: Proposition 2.3. The subgraph T C G computed by Algorithm 2.1 is a tree spanning all the vertices of G. (See also further Def. 2.8.) □ Proof. Using induction on the number of iterations of the main cycle while (U/0){ ...... T^T U{e,v}; } } we prove that T is a tree spanning the set of already processed ("finished") vertices.□ • After the first iteration, T — {0,t>o} which represents a single-node tree vq. c • Let, after iteration i, the induction claim hold. Iteration i + 1 chooses (e,v) e U, and iff is finished, then nothing new happens. if (state [v] / finished) { ... T U{e,v}; } □ Hence v is not finished yet, and TU {e, v} means we are adding to T a new vertex v with an edge e to some existing vertex of T. Then T U {e,t>} is again connected and acyclic, hence a tree, too. Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees Variants and Applications of the graph search scheme: (*) while (U nonempty) { choose (e,v) e U; The many variants of graph search mostly differ by the way (*) vertices are chosen (picked up) from the depository... □ • BFS breadth-first search - the depository U is a "fifo" queue - perhaps the simplest variant, and trivially implementable. □ • DFS depth-first search - the depository U is a "lifo" stack - quite important that vertices stored to U multiple times —>• last one "wins".n • Searching a disconnected graph (in any way) - simply repeat Alg. 2.1 with arb. starting vertices in the components... □ • Searching a directed graph - in Alg. 2.1, instead of foreach (edge f incident with v), just use foreach (arc f starting in v) ... disconnected graph = nesouvislý graf TlfS = profit do íifouúhj, 'BfS = profit do šířku Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees Variants and Applications..., II • Some (slightly) more involved variants: — testing bipartite graphs - one simply runs BFS such that it "switches sides" with each PRQCESS(e), until none or some conflict is found. (Lecture 7) □ — Jarnik's minimum spanning tree algorithm - the depository U always picks the vertex closest to any processed vertex. (Section 2.3) — Dijkstra s shortest path algorithm - the depository U always picks the vertex closest to the starting position vq. (Lecture 3) Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees DFS and BFS search trees Every run of the graph seach Algorithm 2.1 implicitly defines the search tree T: choose (e,v) e U; if (state [v] / finished) { ... state[v] ^finished; T U{e,v}; } □ Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees 2.2 Connectivity and Components Recall: connected graphs are those graphs G such that, for any two vertices u,v € V(G), there is a path in G between the ends u and v. □ Definition: A walk W of length n in a graph G is a sequence of alternating vertices and edges W = (v0,e1,v1,e2,v2,... ,en,vn), □ such that every its edge has the ends Vi-i,Vi, for i — 1,..., n. We speak about a wa//c from u — vq to vn — v, even if the graph G is undirected. Such a sequence really is a "walk' through the graph, see for instance how an IP packet is routed through the internet - it often repeats vertices. Petr Hliněný, Fl MU Brno, 2014 atternatinß = střídající Fl: MAOIO: Connectivity and Spanning trees Components of a graph Lemma 2.4. Let ~ be a binary relation on the vertex set V(G) of a graph G, such that u ^ v if, and only if, there exists a walk in G starting in u and ending in v. Then ~ is an equivalence relation. □ Proof. The relation ~ is • reflexive since every vertex itself forms a walk of length 0, • symmetric since any undirected walk can be easily "reversed", and • transitive since two walks can be concatenated at the common endvertex. Definition 2.5. The connected components of a graph G are formed by the equivalence classes of the above relation ~ (Lemma 2.4) on V(G).o More generally, by connected components we also mean the subgraphs induced on these vertex set classes of ~ . □ Z Connected graphs revisited Fact: By the definition, a path in a graph is a walk without repetition of vertices. Lemma 2.6. If there exists a walk between vertices u and v in a graph G, then there also exists a path from u to v in this G. □ Proof. Among all the walks between u and v in G, we choose the (one of) shortest walk as W C G. It is then clear that if the same vertex is repeated on W, then W could be shortened further, a contradiction. Hence W is a path in G. Corollary 2.7. A graph G is connected if, and only if, G consists of at most one connected component. Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees 2.3 Minimum Spanning Tree problem Recall (Section 1.3): trees are "minimal connected graphs". Definition 2.8. A spanning tree of a connected graph G is a subgraph T C G such that T is a tree and V(T) = V(G). * • R (edge lengths in this case). A positively weighted graph (G, w) is such that w(e) > 0 for all edges e. □ Looking for a minimal interconnection in a graph (wrt. weights w) hence reads: Problem 2.9. The minimum spanning tree (MST) problem Given a weighted connected graph (G, w) with (positive) edge weights w; the problem is to find a spanning tree T in G that minimizes the total weight. uFormally 14 2 14 2 Petr Hliněný, Fl MU Brno, 2014 weightedgraph = vážený či ohodnocený graf Fl: MAOIO: Connectivity and Spanning trees A bit of history - it all started in Brno! • Long time ago, in the past century, the task was to connect town and villages in South Moravia by electric power lines of minimum total length... • Does it sound familiar? Yes—we have to find a minimum spanning tree in the graph of all possible connections between these settlements. □ • Did it really happen? Yes, again, and an algorithmic solution was found in 1926 by Otakar Borůvka, a Brno mathematician. □ A simpler and precise algorithm of Vojtěch Jarník then followed in 1930. □ • Unfortunately, both there works were published only in Czech language, and so most of the world knows only the work of Kruskal, giving another algorithm in 1956, and of Prim, who later rediscovered Jarnik's algorithm. Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees Jarník's MST Algorithm 3 4 3 3 4 3 14 2 14 Algorithm 2.10. Jarnfk's (later known as Prim's) algorithm for MST. Given is a weighted graph (G, w) with edge weights w (which are commonly assumed positive, but this is not necessary). □ • Run Algorithm 2.1 with an implementation of the step choose (e,v) G U; such that (e, v) e U minimizes w(e). □ • U is thus implemented as a min-heap with the key w(e) for (e,v) e U. □ • The resulting search tree T is a minimum spanning tree of G. min-heap = HaCda s minimdCnim {Cicem Petr Hlinený, Fl MU Brno, 2014 16/33 Fl: MA010: Connectivity and Spanning trees Jarnik's MST algorithm, proof Algorithm 2.10: • Run Algorithm 2.1 with an implementation of the step choose (e,v) G U; such that (e,v) G U minimizes w(e). • U is thus implemented as a min-heap with the key w(e) for (e,v) G U. • The resulting search tree T is a minimum spanning tree of G. Proof of Algorithm 2.10. We have the following setup; • let T be the spanning tree (Proposition 2.3) computed by the algorithm, □ • Ti — {vo},T2,..., Tn — T be the seq. of part, solutions after each iter., and • Topt ^ T be some optimal MST solution, maximizing index k s.t. Tk C Topt.n Then k < n. Let {e} — E(Tk+i) \ E(Tk) be the first "wrong" edge chosen by the alg. By Corollary 1.12, Topt + e (by adding the edge e to Topt) contains exactly one cycle C C Topt + e. Then C has at least two edges leaving V(Tk); e and some /. □ Now Talt — (Topt + e) \ / is a spanning tree again, and since w(f) > w(e) (by the algorithm, w(e) was minimized when choosing (e,t>) G U), also Talt is an optimal MST solution. This contradicts our choice of max. k. C Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees 2.4 Higher Levels of Connectivity Various netw. applications demand not only that a graph is connected, but that it stays connected even after failure of a small number of nodes (vertices) or links (edges). This can be studied in theory as "higher levels" of graph connectivity. □ Definition: A graph G is edge-k-connected, k > 1, if G stays connected even after removal of any subset of < k — 1 edges. □ Definition: A graph G is vertex-k-connected, k > 1, if G stays connected even after removal of any subset of < k — 1 vertices. Specially, the complete graph Kn is defined to be vertex-(n— l)-connected, and K\ is vertex-1-connected. □ Graphs that are "vertex/edge- 1-connected" are just connected. Sometimes we speak about a ^-connected graph, and then we usually mean it to be vertex-fc-connected. High vertex connectivity is a (much) stronger requirement than edge connectivity... Menger's theorem and related Theorem 2.11. A graph G is edge-k-connected if, and only if, there exist (at least) k edge-disjoint paths between any pair of vertices (the paths may share vertices). A graph G is vertex-k-connected if, and only if, there exist (at least) k internally disjoint paths between any pair of vertices (the paths may share only their ends). A few notes: • For k — 1 the statement is trivial. □ • For k — 2 the theorem (second part) reads: A graph G is vertex-2-conn. iff every two vertices of G lie on a common cycle. • The full proof, for any k, will be given in Lecture 4. Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees Menger's theorem, II Recall: A graph G is vertex-^-connected if, and only if, there exist (at least) k internally disjoint paths between any pair of vertices (the paths may share only their ends). A straightforward reformulation of Theorem 2.11 is: □ Theorem 2.12. Assume G is a k-connectedgraph, k>2. Then, for every two disjoint sets U\,U2 C V(G), \Ui\ — IC/2I — k, there exist k pairwise disjoint paths from the terminals ofU\ to U?- add two new vertices x\,x2, each adjacent to one of Ui, U2, and take the k internally disjoint paths from Theorem 2.11 between x\ and Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees More on 2-connected graphs To better illustrate the interesting properties of highly connected graphs, we give the following alternative characterizations of 2-connected ones. (A similar one exists for 3-conn. graphs.) Theorem 2.13. A simple graph is 2-connected if, and only if, it can be constructed from a cycle by "adding ears"; i.e. by iterating the operation which adds a new path (of arbitrary length, even an edge, but not a parallel edge) between two existing vertices of a graph. □ A sketch: find the first cycle, and "grow it" to the largest possible subgraph G' by adding ears. A closest vertex of the graph "outside" of G' has two connections to G'—one a direct edge and another via a path—making together a new ear. □ Theorem 2.14. G is a 2-connected graph if, and only if, every two edges ofG belong to a common cycle. □ Proof. For two edges — UiVi, i — 1,2, apply Theorem 2.12 to Ui — {ui,Vi}. C Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees 2.5 Connectivity in Directed Graphs For start, we proceed analogously to the undirected case... Definition: A directed walk W of length n in a digraph D is a sequence of alternating vertices and directed edges W = (v0,ei,vi,e2,v2,... ,en,vn). such that every edge (arc) in W is of the form — (t>i_i,t>i). Lemma 2.15. If there exists a directed walk from u to v in a digraph D, then there also exists a directed path from u to v in this D. □ 0 1 2 n 1 n Views of directed connectivity • The weak connectivity view does not care about directions of arcs. Not so usable or interesting... □ • The reachability view is as follows: Definition: A digraph D is out-connected if there exists a vertex v e V(D) such that for every x G V(D) there is a directed walk from v to x (all vertices reachable from v). No, this graph is not out-connected - see the right-most vertex... □ • The strong (bidirectional) view builds on the following: zomk,coiincctiviUj = sCa6& souznsCost reaclialpiCitii = dosaziteCtiost Petr Hlinený, Fl MU Brno, 2014 23/33 Fl: MA010: Connectivity and Spanning trees Strong connectivity Lemma 2.16. Let « be a binary relation on the vertex set V(D) of a directed graph D such that w « v if, and only if, there exist two directed walks in D - one starting in u and ending in v and the other starting in v and ending in u. Then « is an equivalence relation. □ Definition 2.17. The strong components of a digraph D are formed by the equivalence classes of the above relation « (Lemma 2.16) on V(D).u A digraph is strongly connected if it has at most one strong component. See the four strong components in this illustration picture: strong components = siínc komponenty strongly connecte£= silne soumslý Petr Hlinený, Fl MU Brno, 2014 24/33 Fl: MAOIO: Connectivity and Spanning trees Condensation of a digraph Definition: A digraph Z whose vertices are the strong components of D, and the arcs of Z exist exactly between those pairs of distinct components of D such that D contains an arc between them, is called a condensation of D. □ Definition: A digraph is acyclic (a "DAG") if it does not contain a directed cycle.□ Proposition 2.18. The condensation of any digraph is an acyclic digraph. Petr Hliněný, Fl MU Brno, 2014 aciidic = aciMicfoi, condensation = kondenzace Fl: MAOIO: Connectivity and Spanning trees 2.6 Appendix: DFS and BFS examples Following on Algorithm 2.1... Example 2.15. An example of a breadth-first search run from the vertex a. 9 f; h A;--... \ / / I I a®- Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees Petr Hliněný, Fl MU Brno, 2014 Fl: MA010: Connectivity and Spanning trees Example 2.16. An example of a depth-first search run from the vertex a. Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees 2.7 Appendix: Eulerian Trails Perhaps the oldest recorded result of graph theory comes from famous Leonhard Euler— it is the "7 bridges of Königsberg" (Královec, now Kaliningrad) problem. tjHlSiC.i.'H «CA So what was the problem? The city majors that time wanted to walk through the city while crossing each of the 7 bridges exactly once... Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees This problem led Euler to introduce the following: Definition: A trail in a (multi)graph is a walk which does not repeat edges. A closed trail (tour) is such a trail that ends in the same vertex it started with. The opposite is an open trail. And the oldest graph theory result by Euler reads: □ Theorem 2.17. A (multi)graph G consists of one closed trail if, and only if, G is connected and all the vertex degrees in G are even. □ Corollary 2.18. A (multi)graph G consists of one open trail if, and only if, G is connected and all the vertex degrees in G but two are even. Analogous results hold true also for digraphs (the proofs are the same)... Petr Hliněný, Fl MU Brno, 2014 Fl: MAOIO: Connectivity and Spanning trees