Connectivity: Paths

Connectivity
Problem of determining whether a message can be sent between two

computers using intermediate links
Problems of efficiently planning routes for mail delivery, garbage pickup,
diagnostics in computer networks, and so on
Paths
A path is a sequence of edges that begins at a vertex of a graph and travels from
vertex to vertex along edges of the graph.
DEFINITION 1
Let n be a nonnegative integer and G an undirected graph. A path of length n from
u to v in G is a sequence of n edges e1,...,en of G for which there exists a sequence
x0 = u, x1,..., xn1, xn = v of vertices such that ei has, for i = 1,...,n, the end points
xi1 and xi . When the graph is simple, we denote this path by its vertex sequence
x0 , x1 , . . . , xn (because 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, and has
length greater than zero. The path or circuit is said to pass through the vertices x1,
x2, . . . , xn1 or traverse the edges e1, e2, . . . , en. A path or circuit is simple if it
does not contain the same edge more than once.
When it is not necessary to distinguish between multiple edges, we will
denote a path e1, e2,...,en, where ei is associated with {xi1, xi} for i = 1,
2,..., n by its vertex sequence x0, x1, . . . , xn.
The notation identifies a path only as far as which vertices it passes through
It does not specify a unique path when there is more than one path that
passes through this sequence of vertices, which will happen if and only if
there are multiple edges between some successive vertices in the list.
A path of length zero consists of a single vertex.
Remark: There is considerable variation of terminology concerning the concepts
defined in Definition 1. For instance, in some books, the term walk is used instead
of path, where a walk is defined to be an alternating sequence of vertices and
edges of a graph, v0, e1, v1, e2,...,vn1, en, vn, where vi1 and vi are the endpoints
of ei for i = 1, 2,..., n. When this terminology is used, closed walk is used instead
of circuit to indicate a walk that begins and ends at the same vertex, and trail is
used to denote a walk that has no repeated edge (replacing the term simple path).
When this terminology is used, the terminology path is often used for a trail with
no repeated vertices, conflicting with the terminology in Definition 1.
EXAMPLE
In the simple graph shown in Figure 1, a, d, c, f , e is a simple path of length 4,
because {a, d}, {d, c}, {c, f }, and {f, e} are all edges. However, d, e, c, a is not a
path, because {e, c} is not an edge. Note that b, c, f, e, b is a circuit of length 4
because {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 because it contains
the edge {a, b} twice.
Paths and circuits in directed graphs

DEFINITION 2
Let n be a nonnegative integer and G a directed graph. A path of length n from u
to v in G is a sequence of edges e1, e2, . . . , en of G such that e1 is associated with
(x0, x1), e2 is associated with (x1, x2), and so on, with en associated with (xn1, xn),
where x0 = u and xn = v. When there are no multiple edges in the directed graph,
this path is denoted by its vertex sequence x0, x1, x2, . . . , xn. A path of length
greater than zero that begins and ends at the same vertex is called a circuit or
cycle. A path or circuit is called simple if it does not contain the same edge more
than once.
Paths in graph models

Paths in Acquaintanceship Graphs In an acquaintanceship graph there is a path
between two people if there is a chain of people linking these people, where two
people adjacent in the chain know one another. For example, in acquaintanceship
graph given below, there is a chain of six people linking Kamini and Ching.
Paths in Collaboration Graphs

In a collaboration graph, two people a and b are connected by a path when there is
a sequence of people starting with a and ending with b such that the endpoints of
each edge in the path are people who have collaborated. The academic
collaboration graph of people who have written papers in mathematics, the Erdo s
number of a person m, is the length of the shortest path between m and the
extremely prolific mathematician Paul Erdo s (who died in 1996). That is, the
Erdo s number of a mathematician is the length of the shortest chain of
mathematicians that begins with Paul Erdo s and ends with this mathematician,
where each adjacent pair of mathematicians have written a joint paper. The
number of mathematicians with each Erdo s number as of early 2006, according to
the Erdo s Number Project, is shown in Table 1.
Connectedness in Undirected Graphs

DEFINITION 3
An undirected graph is called connected if there is a path between every pair of
distinct vertices of the graph. An undirected graph that is not connected is called
disconnected. We say that we disconnect a graph when we remove vertices or
edges, or both, to produce a disconnected subgraph.
EXAMPLE
The graph G1 in Figure is connected, because for every pair of distinct vertices
there is a path between them. However, the graph G2 in Figure is not connected.
For instance, there is no path in G2 between vertices a and d.
THEOREM
There is a simple path between every pair of distinct vertices of a connected
undirected graph.
(The proof is left as an exercise for the students)
CONNECTED COMPONENTS A connected component of a graph G is a

connected subgraph of G that is not a proper subgraph of another connected
subgraph of G. That is, a connected component of a graph G is a maximal
connected subgraph of G. A graph G that is not connected has two or more
connected components that are disjoint and have G as their union.
EXAMPLE
The graph H is the union of three disjoint connected subgraphs H1, H2, and H3,
shown in Figure. These three subgraphs are the connected components of H.
Questions:
Q1) Does each of these lists of vertices form a path in the following graph? Which paths
are simple? Which are circuits? What are the lengths of those that are paths?
a) a, e ,b, c, b
c) e, b, a, d, b, e
b) a, e, a, d, b, c, a
d) c, b, d, a, e, c
Q2) Does each of these lists of vertices form a path in the following graph? Which paths
are simple? Which are circuits? What are the lengths of those that are paths?
a) a, b, e, c, b
c) a, d, b, e, a
b) a, d, a, d, a
d) a, b, e, c, b, d, a
Q3) Determine whether the given graph is connected. If not, how many connected
components does the graph have? Find each of its connected components.
Q4) What do the connected components of acquaintanceship graph represent?

Connectivity: Paths

Uploaded by

Copyright:

Available Formats

Connectivity: Paths

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Connectivity: Paths

Uploaded by

Copyright:

Available Formats

Connectivity

Problem of determining whether a message can be sent between two

no repeated vertices, conflicting with the terminology in Definition 1.

Paths and circuits in directed graphs

Paths in graph models

Paths in Collaboration Graphs

Connectedness in Undirected Graphs

CONNECTED COMPONENTS A connected component of a graph G is a

Q4) What do the connected components of acquaintanceship graph represent?

You might also like