2   Connectivity in Graphs
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
• Walks in a graph, the definition, connected components.
• Exploring a graph, search algorithms - BFS and DFS.
• Higher levels of connectivity, 2-connected graphs, Menger's theorem.
• Connectivity in directed graphs, strong components.
• Eulerian tours and trails, "Seven Bridges" and the even degree cond.
Petr Hliněný,   Fl MU Brno, 2011
1/19
Fl: MADID: 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
(vo,ei,vi,e2,v2, ■ ■ ■ ,en,vn), such that every its edge    has the ends Vi-i,Vi.
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.
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 undirected walk can be easily "reversed", and transitive since two walks can be concatenated at the common endvertex. C
Petr Hliněný,   Fl MU Brno, 2011
2/19
Fl: MADID: Graph Connectivity
Components of a graph
Definition: The equivalence classes of the above relation ~ (Lemma 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 ~.
Can you see all the three components in this picture?
Petr Hliněný,   Fl MU Brno, 2011
3/19
Fl: MADID: Graph Connectivity
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. c
Proof. Let (u — vq, e±, t>i,..., 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 (wo, e±, u>\,..., Wi) of W (inductively from i — 0, i.e. wo) where Wi — Vj for some j € {0,1,..., n}. c
- Find maximum index A; > j such that Vk — Vj — Wi (repeated), and append W with (...,Wi=Vj = vk, ek+i, wl+1 = Wfc+i,...).
- It remains to show, by means of a contradiction, that the new vertex Wi+i — vk+i have not occured in W yet.
- The procedure stops whenever Wi — v. c
C
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 repeated in W, then W could be shortened further, a contradiction. Hence     is a path in G. C
Petr Hliněný,   Fl MU Brno, 2011
4/ 19
Fl: MADID: 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.
Petr Hliněný,   Fl MU Brno, 2011
5/19
Fl: MAÜ1Ü: Graph Connectivity
2.2   Exploring (Searching) a Graph
For an illustration, we present a very general scheme of searching through a graph. 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 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.
Petr Hliněný,   Fl MU Brno, 2011
6/19
Fl: MADID: Graph Connectivity
Algorithm 2.4. Searching through a connected component G
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 vo of G}; state (fo) = 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;
}
POSTPROCESS(v); state (v) = finished;
}
G is finished;
Petr Hliněný,   Fl MU Brno, 2011
7/19
Fl: MADID: 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 v$
(similar, but more general, to BFS, see the next lecture), c Example 2.15. An example of a depth-first search run from a vertex a.
\
d
c
Petr Hliněný,   Fl MU Brno, 2011
8/19
Fl: MADID: Graph Connectivity
Petr Hliněný,   Fl MU Brno, 2011
9/19
FLMAOIO: Graph Connectivity
Example 2.16. An example of a breadth-first search run from a vertex a.
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.
Definition: A graph G is edge-k-connected, k > 1, if G stays connected even after removal of any subset of < k — 1 edges, c
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 Graphs that are "vertex/edge-l-connected" are simply 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.. .
Petr Hliněný,   Fl MU Brno, 2011
11/19
Fl: MAÜ1Ü: 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.
Theorem 2.6. Assume G be a 2-connected graph. Then every two edges in G lie on a common cycle.
Petr Hliněný,   Fl MU Brno, 2011
12/19
Fl: MADID: Graph Connectivity
Menger's theorem and related
Theorem 2.7. 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 corollaries of the theorem are the following:
Theorem 2.8. Assume G be 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 of U\ toll2-
Petr Hliněný,   Fl MU Brno, 2011
13/19
Fl: MADID: Graph Connectivity
2.4   Connectivity in Directed Graphs
At the beginning we proceed analogously to the undirected case.. .
Definition: A directed walk of length n in a graph D is a sequence of alternating vertices and directed edges
(v0,ei,v1,e2,v2, . . . ,en,vn), such that every edge    in it is    — (t>i_i,t>i). c
Theorem 2.9. 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.
Petr Hliněný,   Fl MU Brno, 2011
14/19
Fl: MADID: Graph Connectivity
Views of directed connectivity
• The weak connectivity does not care about directions of arcs. Not so usable or interesting...
• A reachability view, 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. . .
Petr Hliněný,   Fl MU Brno, 2011
15/19
Fl: MADID: Graph Connectivity
Lemma 2.10. 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, c
Definition 2.11. The strong components of a digraph D
are formed by the equivalence classes of the above relation « (Lemma 2.10) 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:
Petr Hliněný,   Fl MU Brno, 2011
16/19
FLMAOIO: Graph 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. c
Definition: A digraph is acyclic (a "DAG") if it does not contain a directed cycle.□
Proposition 2.12. The condensation of any digraph is an acyclic digraph.
Petr Hliněný,   Fl MU Brno, 2011
17/19
Fl: MADID: Graph Connectivity
2.5   Eulerian Trails
Perhaps the oldest recorded result of graph theory comes from famous Leonardo Eu-ler—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, 2011
18/19
Fl: MAÜ1Ü: 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: c
Theorem 2.13. 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.14. 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, 2011
19/19
FLMAOIO: Graph Connectivity