2   Connectivity in Graphs
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 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.
V
Petr Hliněný,  Fl MU Brno
FI: MA010: 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
such that every its edge ej has the ends Vj_i, Vj.
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. □ □
Petr Hliněný,  Fl MU Brno_2_Fl: MAOIO: Graph Connectivity
edges
(vo, eí,ví,e2, V2, .. ., en,vn),
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 ~.
Petr Hliněný,  Fl MU Brno
Fl: MAOIO: 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 = vo, ei, vi,..., en, vn = v) be a walk of length n between u and v in G. We start building a new walk W from w0 = u which will actually be a path:
- Assume we have built a starting fragment (w0, e1, w1,..., wj) of W (inductively from i = 0, i.e. w0) where wj = vj for some j G {0,1,... ,n}. c
- Find maximum index k > j such that vk = vj = wj (repeated), and append W with (. . ., wj = vj = vfc, efc+i, wj+i = vfc+i, ...). c
- It remains to show, by means of a contradiction, that the new vertex wj+i = vk+i have not occured in W yet.
- The procedure stops whenever wj = v. 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 W is a path in G.
□
V
Petr Hliněný,  Fl MU Brno
Fl: 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?
Petr Hliněný,  Fl MU Brno
FI: MA010: Graph Connectivity
I
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ý,  FI MU Brno_6_FI: MA010: 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 v0 of G}; state(v0) = discovered; while (U nonempty) {
choose v G U;     U = U\{v};
PROCESS(v);
foreach (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_7_Fl: MA010: 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 v0
(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.
9
> d
c
a<§>-
■* b
Petr Hliněný,  Fl MU Brno
Fl: 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. 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 — 1)-connected. c
Graphs that are "vertex/edge-1-connected" are simply connected.
Sometimes we speak about a k-connected graph, and then we usually mean it to be vertex-k-connected. High vertex connectivity is a (much) stronger requirement than edge connectivity. . .
V
Petr Hiineny,  FI MU Brr
: MA010: 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.
'-«s
5->
•
i V
i-V
5
•
5
Petr Hlineny,  Fl MU Brr
l:MA010: Graph Connectivity
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 corollaries 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. c
Theorem 2.8. Assume G be a k-connected graph, k > 2. Then, for every two disjoint sets Ui, U2 C V(G), \U\\ = \U2\ = k, there exist k pairwise disjoint paths from the terminals of U\ to U2.
Ui
U2
Petr Hlin
FI MU Brn
:I:MA010: Graph Connectivity
t
t
t
t
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 G is a sequence of alternating vertices and directed edges
such that every edge ej in it is ej = (vj_i,vj). c
Theorem 2.9. If there exists a directed walk from u to v in a digraph G, then there also exists a directed path from u to v in this G. c
Definition: A digraph G is out-connected if there exists a vertex v G V(G) such that for every x G V(G) there is a directed walk from v to x.
(vo, ei,vi,e2, V2, .. ., en,vn),
V
Petr Hlineny,  FI MU Brr
I:MA010: Graph Connectivity
Lemma 2.10. Let « be a binary relation on the vertex set V(G) of a directed graph G such that u « v if, and only if, there exist two directed walks in G - 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: The equivalence classes of the above relation « (Lemma 2.10) on V(G) are called the strong components of the digraph G.
A digraph is strongly connected if it has at most one strong component.
Definition: A digraph is acyclic (a "DAG") if it does not contain a directed cycle.
Lemma 2.11. A digraph G without loops is acyclic if, and only if, all its strong components are single vertices.
V
Petr Hlineny,  Fl MU Brr
l:MA010: Graph Connectivity
2.5   Eulerian Trails
Perhaps the oldest recorded result of graph theory comes from famous Leonardo Euler — it is the "7 bridges of Königsberg' (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...
Petr Hliněný,  FI MU Brn.
:I:MA010: 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.12. 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.13. 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 Hlinený,  FI MU Brno_17_FI:MA010: Graph Connectivity