Connectedness in undirected graphs

Paths

A path of length n from u to v, where n is a positive integer, in an undirected graph is a sequence of edges of the graph such that where and . When the graph is simple, we denote this path by its vertex sequence (since listing these vertices uniquely determines the path). The path is a circuit if it begins and ends at the same vertex, that is, if u = v. The path or circuit is said to pass through or traverse the vertices . A path or circuit is simple if it does not contain the same edge more than once.

Example.

In this simple graph a, d, c, f, e is a simple path of length 4, since { a, d }, { d, c }, { c, f } and { f, e } are all edges. However, d, e, c, a is not a path, since { e, c } is not an edge. Note that b, c, f, e, b is a circuit of length 4 since { b, c }, { c, f }, { f, e } and { e, b } are edges, and this path begins and ends at b. The path a, b, e, d, a, b, which is of length 5, is not simple since it contains the edge { a, b } twice.

A path from a to b in a directed graph G is a sequence of one or more edges , , , …, in G, where and , that is, a sequence of edges where the terminal vertex of an edge is the same as the initial vertex in the next edge in the path. This path is denoted by and has length n. A path that begins and ends at the same vertex is called a circuit or cycle.

A path of length n from u to v in a directed multigraph is a sequence of edges of the graph such that where and . When there are no multiple edges in the graph, this path is denoted by its vertex sequence . A path or circuit is called simple if it does not contain the same edge more than once.

An undirected graph is called connected if there is a path between every pair of distinct vertices of the graph.

Example.

The graph G is connected, since for every pair of distinct vertices there is a path between them. However, the graph H is not connected. For instance, there is no path in H between vertices a and d.

Theorem 1. There is a simple path between every pair of distinct vertices of a connected undirected graph.

Proof: Let u and v be two distinct vertices of a connected undirected graph G = (V, E). Since G is connected, there is at least one path between u and v. Let x ₀, x ₁, …, x_n, where x ₀ = u and x_n = v, be the vertex sequence of a path of least length. This path of least length is simple. To see this, suppose it is not simple. Then x_i = x_j for some i and j with . This means that there is a path from u to v of shorter length with vertex sequence x ₀, x ₁, …, x_{i –1}, x_j, …, x_n obtained by deleting the edges corresponding to the vertex sequence x_i, …, x_{j –1}.

A graph that is not connected is the union of two or more connected subgraphs, each pair of which has no vertex in common. These disjoint connected subgraphs are called the connected components of the graph.

Sometimes the removal of a vertex and all edges incident with it produces a subgraph with more connected components than in the original graph. Such vertices are called cut vertices (or articulation points). The removal of a cut vertex from a connected graph produces a subgraph that is not connected. Analogously, an edge whose removal produces a graph with more connected components than in the original graph is called a cut edge or bridge.

Example. Find the cut vertices and cut edges in the graph G.

Solution: The cut vertices of G are b, c and e. The removal of one of these vertices (and its adjacent edges) disconnects the graph. The cut edges are { a, b } and { c, e }. Removing either one of these edges disconnects G.

Дата добавления: 2014-12-23