2 Graph Connectivity Graphs are often used to model various interconnecting networks, such as transport, pipe, or computer networks. In such models, one often needs or wants to get from a place to any other place. .. Graphs with this nice property of "accessibility" are connected, and we shall study them now. Brief outline of this lecture • Connections in a graph, definition, components • Searching through a graph, search algorithms BFS and DFS • Higher levels of connectivity, 2-connected graphs, Menger's theorem • Eulerian tours and trails, "seven bridges" and the even degree cond. ' Hlinený. Fl Mt AOIO: Graph Connectivity 2.1 Graph Connectivity and Components Definition: A walk of length n in a graph G is a sequence of alternating vertices and edges v0,e1,v1,e2,v2, .. .,en,vn. such that every its edge ej has the ends ví-i,ví. This really is a "walk" through the graph, see for instance how an IP packet is routed through the internet (as it often repeats vertices), d Lemma 2.1. 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. It is also symmetric since any walk can be easily "reversed", and transitive since two walks can be concatenated at the common endvertex. D Definition: The equivalence classes of the above relation ~ (Lema 2.1) on V(G) are called the connected components of the graph G. More generally, by connected components we also mean the subgraphs induced on these vertex set classes of ~. • Hlinený. Fl Ml IA010: Graph Connectivity r Recall a path in a graph— it is a walk without repetition of vertices. Theorem 2.2. 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. Let u = vq, ei, «1, • • •, en, vn = v be a walk of length n between u and v in G. We start building a new walk W from wq = u which will actually be a path: - Assume we have built a starting fragment wq, ei, »i,..., Wi of W (inductively from i = 0, i.e. wq) where Wi = Vj for some j G {0,1,..., n}, c - Find maximum index k > j such that vj. = Vj = Wi (repeated), and append W with ...,Wi=Vj= vk, ek+1, wi+1 = vk+1, .... c - It remains to show, by means of a contradiction, that the new vertex Wj+i = vk+\ does not occur in W yet. - The procedure stops whenever Wi = v. c D Proof; a shorter, but nonconstructive alternative. Among all the walks between u and v in G, we choose the (one of) shortest one as W. It is clear that if the same vertex were repeated in W, then W could be shortened further, a contradiction. Hence W is a path in G. U ________;tr Hliněný, Fl MU Brru MAOIO: Graph Connectivity Definition 2.3. Graph G is connected if G consists of at most one connected component. By Theorem 2.2, this means if every two vertices of G are connected by a path. How many components do you see in this picture? etr Hliněný, Fl MU Br : MAOIO: Graph Connectivity We present a very general scheme of searching through a graph. This meta-algorithm works with the following datastates and structures: • A vertex: having one of the states .. . - initial - assigned at the beginning, - discovered - after we have find it along an edge, - finished - assigned after processing all incident edges. • An edge: having one of the states ... - initial - assigned at the beginning, - processed - whenever it has been processed at one of its endvertices. c • Stack (depository): is a supplementary data structure (a set) which - keeps all the discovered vertices until they have been finished. Remark: Graph search has several variants mostly defined by the way vertices are picked from the depository. Specific programming tasks can be (are) performed at each vertex or edge of G while processing them. ■ Hlinený. Fl Ml A010: Graph Connectivity Algorithm 2.4. Searching through a connected component This algorithm visits and processes every vertex and edge of a connected graph G. input < graph G; state (all vertices and edges of G) < initial; stack U = {any vertex vq of G}; state («o) = discovered; while (U nonempty) { choose v G U; U = U\{v}; PROCESS(v); f oreach ( e incident with v) { if (state(e)==initial) PROCESS(e); w = the opposite vertex of e = vw; if (state(w)== initial) { state (w) = discovered; U = UU{w}; } state (e) = processed; } state (v) = finished; } G is finished; etr Hliněný, Fl M____________________________________________________MAOIO: Graph Connectivity Implementation variants of graph searching • DFS depth-first search - the depository U is a "LIFO" stack, c • BFS breadth-first search - the depository U is a "FIFO" queue, c • Dijkstra's shortest path algorithm - the depository U always picks the vertex closest to the starting position vq (similar, but more general, to BFS, see the next lecture), c Example 2.11. An example of a depth-first search run from a vertex a. /* = g *; 'If d --------H e i — 4 3 h * —_ Í''l_----* c \ ~--r— \ / a®- etr Hliněný, Fl MU Br : MA010: Graph Connectivity f ,*~:—*se Detr Hliněný, Fl MU Br : MAOIO: Graph Connectivity Example 2.12. An example of a breadth-first search run from a vertex a. f ,*~:—*se etr Hliněný, Fl MU Br : MAOIO: Graph Connectivity 2.3 Higher Degrees of Connectivity Various networking applications are often demanding not only that a graph is connected, but that it will stay connected even after failure of some small number of nodes (vertices) or links (edges). This can be studied in theory as "higher levels" of graph connectivity, c 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 vertex-(n — l)-connected. c 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.. . etr Hliněný, Fl MU Bri : MAOIO: Graph Connectivity About 2-connected graphs Theorem 2.5. 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. etr Hliněný, Fl MU Bri :MA010: Gra phCo Menger's theorem and related Theorem 2.6. 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). Some direct corrolaries of the theorem are the following: Theorem 2.7. Assume G be a 2-connected graph. Then every two edges in G lie on a common cycle, z Theorem 2.8. Assume G be a k-connected graph, k > 2. Then, for every two disjoint sets Ui,U2 C V(G), \Ui\ = \U2\ = k, there exist k pairwise disjoint paths from the terminals ofU\ to U2- Ui u2 etr Hlinený, Fl MU Bri : MAOIO: Graph Connectivity 2.4 Eulerian Trails Perhaps the oldest recorded result of graph theory comes from famous Leonarda Euler— it is the "7 bridges of Königsberg" (Královec, now Kaliningrad) problem. kJNJMo-'tmCA :r£E: 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... etr Hliněný, Fl MU Bri : MAOIO: Graph Connectivity This problem led Euler to introduce the following: Definition: A trail in a 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.9. 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, c Corollary 2.10. 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 exist also for digraphs. : MA010: Graph Connectivity