2 Graph Searching and Connectivity Brief outline of this lecture • Generic graph search scheme, the BFS and DFS searches. • Connectivity, components, Menger's theorem, 2-connected graphs. • Minimum spanning tree problem (Jarnik / Prim). • Connectivity in directed graphs, strong components. Petr Hliněný, Fl MU Brno, 2015 1/31 Fl: MAOIO: Searching and Connectivity 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, 2015 2/31 Fl: MAOIO: Searching and Connectivity ^2.1 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 stack. 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, 2015 3/31 Fl: MAOIO: Searching and Connectivity 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 of G~\ <— initial', stack U <— {(0, v0)}, for any starting vertex vq of G; search tree T ^— 0; while (U / i) { choose (e,v) G U; U ^U\{(e,v)>; if (e^0) PROCESS (e; v) ; if (state [v] ^ finished) { f or each (edge f incident with v) { w <— the opposite vertex of "f = vw"; if (state [w] ^ finished) { s t at e [w] <— disco vered; U ^UU{(f,w)>; state [v] ^finished; } G T MU{e,v}; > is finished; * (Procházení souvislým grafem * state = stav, stackjdepository = úschovna • Algorithm 2.1 is only a general scheme, and not a complete implementation. □ • In particular, implementing the stack U and the procedures PROCESS() would likely require additional ("hidden") variables and/or data structures. □ • Algorithm 2.1 altogether performs 0(\E(G)\) (linearly many) elementary operations, calls to 'PROCESS ()' and updates of the stack U. □ • Given a particular implementation of U and PROCESS (), the general scheme can often be simplified (such as, by avoiding duplicates in U). □ • There are no mupliple calls to 'PROCESS(a)' for any vertex or edge a of G. - True for vertices a = v by 'state [v] <— finished1, - and for edges a = / since one end v of f gets finished together with adding of / into U, and then we have: if (state [w] / finished) { ... U MJU{(f,w)}; } Petr Hliněný, Fl MU Brno, 2015 5/31 Fl: MAOIO: Searching and Connectivity Theorem 2.2. Let G be a connected graph and vq 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) G 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 MJU{(f,w)}; } Hence v already is processed at this moment and w will be processed by 1. □ 3. Assume an edge / G E(G) that never gets into U. By connectivity of G, one may choose / closest possible to ^o. 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 ^— UU {(f ,w)}; } a contradiction to the assumption that / never gets into U. Petr Hliněný, Fl MU Brno, 2015 6/31 Fl: MAOIO: Searching and Connectivity ^"correctness!"^ 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.12.) □ Proof. Using induction on the number of iterations of the main cycle while (U/0){ ...... T MU{e,v}; } } we prove that T is a tree spanning the set of already processed ("finished") vertices.□ • After the first iteration, T = {0, ^o} which represents a single-node tree vq. d • Let, after iteration i, the induction claim hold. Iteration i + 1 chooses (e,v) G U, and if v is finished, then nothing new happens. if (state [v] / finished) { ... T MU{e,v}; } □ Hence v is not finished yet, and T ^— 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, v} is again connected and acyclic, hence a tree, too. □ Petr Hliněný, Fl MU Brno, 2015 7/31 Fl: MAOIO: Searching and Connectivity Variants and Applications of the graph search scheme: (*) while (U nonempty) { choose (e,v) £ U; The many variants of graph search mostly differ by the way (*) vertices are chosen (picked up) from the stack... □ • BFS breadth-first search - the stack U is a "fifo" queue - perhaps the simplest variant, and trivially implementable. □ • DFS depth-first search - the stack U is a "lifo" stack - very important to store the vertices to U multiple times —> last one "wins".n • Searching a disconnected graph (in any way) - simply repeat Alg. 2.1 with arbitrary starting vertices in the parts... □ • Searching a directed graph - in Alg. 2.1, instead of foreach (edge f incident with v), just use for each (arc f starting in v) . . . disconnected graph = nesouvislý graf 'DJ-S = profit, do fitoubky, 'BfS = profit, do šířky Petr Hliněný, Fl MU Brno, 2015 8/31 Fl: MAOIO: Searching and Connectivity DFS and BFS search trees Recalling the concept of a search tree T from Proposition 2.3, the following are particularly recognized variants of it: T of BFS ("fifo") T of DFS ("life") Petr Hliněný, Fl MU Brno, 2015 9/31 'fifo" = fronta, "lifo" = zásobníky Fl: MAOIO: Searching and Connectivity Variants and Applications..., II • Some slightly more involved variants (using additional implicit variables): - testing bipartite graphs - one simply runs BFS such that it "switches sides" with each PROCESS(e), until none or some conflict is found. (Lecture 6) Jarník's minimum spanning tree algorithm - the stack U always offers the vertex closest to any processed vertex. (Section 2.3) □ Dijkstra's shortest path algorithm - the stack U always offers the vertex closest to the starting position vq. (Lecture 3) Petr Hliněný, Fl MU Brno, 2015 10/31 Fl: MAOIO: Searching and Connectivity ^2.2 Connectivity and Components Recall: connected graphs are those graphs G such that, for any two vertices u,v G 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 such that every its edge e« has the ends Vi-i,Vi, for i = 1,...,n. We speak about a i/i/a//c from = 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. zua[(^= -procházka v grafu, alternating = střídající Petr Hliněný, Fl MU Brno, 2015 11/31 Fl: MA010: Searching and Connectivity 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).n More generally, by connected components we also mean the subgraphs induced on these vertex set classes of ~ . □ □ connected component = souvislá komponenta Petr Hliněný, Fl MU Brno, 2015 12/31 Fl: MA010: Searching and Connectivity ^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, 2015 13/31 Fl: MAOIO: Searching and Connectivity 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 has more than k vertices and 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 but not n-connected for n > 1, and K\ is vertex-l-connected. □ Graphs that are "vertex/edge-l-connected" are just connected. Sometimes we speak about a fc-connected graph, and then we usually mean it to be vertex-fc-connected. High vertex connectivity is a (much) stronger requirement than edge connectivity... * Vyšší stupni souvislosti * verte?c- / edge-k -connected= vrcholoví / hranoví k -souvislý Petr Hliněný, Fl MU Brno, 2015 14/31 Fl: MA010: Searching and Connectivity Theorem 2.8. A graph G is edge-k-connected if, and only if, G has (at least) k edge-disjoint paths between any pair of vertices (the paths may share vertices). (Menger) A graph G is vertex-k-connected if, and only if, G has (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 (note that this holds also for K\). □ • 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. edge-disjoint paths = hranově disjunktní cesty internally-disjoint paths = vnitřně disjunktní (tj. bez konců) cesty Petr Hlinený, Fl MU Brno, 2015 15/31 Fl: MAOlO: Searching and Connectivity Menger's theorem, II Recall: A graph G is vertex-A:-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.8 is: □ Theorem 2.9. Assume G is a k-connected graph, k > 2. Then, for every two disjoint sets UUU2 C V(G), terminals ofU\ to Ü2- f/21 = k, there exist k pairwise disjoint paths from the A sketch x2 add two new vertices x\,X2, each adjacent to one of Ui, U2, and take the k internally-disjoint paths from Theorem 2.8 between x\ and x%. Petr Hliněný, Fl MU Brno, 2015 16/31 Fl: MAOIO: Searching and Connectivity 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.10. 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.11. G is a 2-connected graph if, and only if, every two edges of G belong to a common cycle. □ Proof. For two edges ei = UiVi, i = 1,2, apply Theorem 2.9 to Ui = {ui^vi}. □ Petr Hliněný, Fl MU Brno, 2015 17/31 Fl: MAOIO: Searching and Connectivity 2.3 Minimum Spanning Tree problem Recall (Section 1.3); trees are "minimal connected graphs" on a given vertex set... Definition 2.12. 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). Petr Hliněný, Fl MU Brno, 2015 18/31 * Trobíím minimální kostry * spanning tree = kostra grafu Fl: MA010: Searching and Connectivity ^"The^MS^!^ Definition: A weighted graph is a pair of a graph G together with a weighting w of the edges by real numbers w : E(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.13. 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. Formally Petr Hliněný, Fl MU Brno, 2015 19/31 weighted graph = vážený či ohodnocený graf Fl: MAOIO: Searching and Connectivity A bit of history - it all started in Brno! • Long time ago, in the past century, the task was to connect towns 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, indeed, 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, 2015 20/31 Fl: MAOIO: Searching and Connectivity arnik's MST Algorithm 3 4 3 \ 3 1 \ /\2 V A \/ ®-A o-.............i K 7 7 co 1 A-^ Algorithm 2.14. Jarnik'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) G U minimizes w(e). □ • U is thus implemented as a min-heap with the keyw(e) for (e,v) G U. □ • The resulting search tree T is a minimum spanning tree of G. min-heap = halda s minimdlnim kticem Petr Hliněný, Fl MU Brno, 2015 21 /31 Fl: MAOIO: Searching and Connectivity Algorithm 2.14: • Run Algorithm 2.1 with an implementation of the step choose (e,v) £ U; such that (e,v) £ U minimizes w(e). • U is thus implemented as a min-heap with the keyw(e) for (e,v) £ U. • The resulting search tree T is a minimum spanning tree of G. Proof of Algorithm 2.14. 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. C Topt. 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(Xfc); 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,v) £ U), also Tait is an optimal MST solution. This contradicts our choice of max. k. □ Petr Hliněný, Fl MU Brno, 2015 22/31 Fl: MAOIO: Searching and Connectivity ^2.4 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 oriented edges W = Oo,ei, vi,e2,v2, • • • ,en,vn), such that every edge (arc) ei in W is of the form ei = 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. directed walk^ = orientovaná procfiázkji Petr Hlinený, Fl MU Brno, 2015 23/31 Fl: MAOIO: Searching and Connectivity 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 G 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: weak^connectivity = síabá souvistost reachability = dosažitelnost Petr Hlinený, Fl MU Brno, 2015 24/31 Fl: MAOlO: Searching and Connectivity ■r Strong connectivity Lemma 2.16. Let ~ be a binary relation on the vertex set V(D) of a directed graph D such that u ~ 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).n A digraph is strongly connected if it has at most one strong component. See the four strong components in this illustration picture: strong components = silní komponenty strongly connected = silné souvislý Petr Hliněný, Fl MU Brno, 2015 25/31 Fl: MA010: Searching and Connectivity ^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, 2015 26/31 acycßc = acyklický, condensation = kondenzace Fl: MAOIO: Searching and Connectivity 2.5 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:. 7-/ / ■4 i \ \ \ \ \ \ * d / / h 4-^. \ \ \ \ / \ / i / \ ^^-^ c \ / ... ii Petr Hliněný, Fl MU Brno, 2015 27/31 Fl: MAOIO: Searching and Connectivity Petr Hliněný, Fl MU Brno, 2015 28/31 Fl: MA010: Searching and Connectivity Example 2.16. An example of a depth-first search run from the vertex a. Petr Hliněný, Fl MU Brno, 2015 29/31 Fl: MAOIO: Searching and Connectivity ^2.6 Appendix: Eulerian Trail Perhaps the oldest recorded result of graph theory comes from famous Leonhard Euler— it is the "7 bridges of Königsberg1 (Královec, now Kaliningrad) problem. 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... * 'Eukrovsky tah ("fgesknijednim tahem") Petr Hlinený, Fl MU Brno, 2015 30/31 Fl: MAOlO: Searching and Connectivity 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 (perhaps) oldest graph theory result by Euler reads: □ Theorem 2.17. (Euler) 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)... trait = tah (uzavřený/otevřený) Petr Hlinený, Fl MU Brno, 2015 31/31 Fl: MAOlO: Searching and Connectivity