Chapter 1 - CS Technion

Chapter 1
PATHS IN GRAPHS 1.1 INTRODUCTION TO GRAPH THEORY
A graph G(V, E) is a structure which consists of a set of vertices V =
{v1, v2, ...} and a set of edges E = {e1, e2, ...}; each edge e is incident
to the elements of an unordered pair of vertices {u, v} which are not
necessarily distinct. Unless otherwise stated, both V and E are assumed to be finite. In this
case we say that G is finite. For example, consider the graph represented in Figure 1.1. Here V = {v1,
v2, v3, v4, v5}, E = {e1, e2, e3, e4, e5}. The edge e2 is incident to v1
and v2, which are called its endpoints. The edges e4 and e5 have the same
endpoints and therefore are called parallel edges. Both endpoints of the
edge e1 are the same; such an edge is called a self-loop. The degree of a vertex v, d(v), is the number of times v is used as an
endpoint of the edges. Clearly, a self-loop uses its endpoint twice. Thus,
in our example d(v4) = 1, d(v2) = 3 and d(v1) = 4. Also, a vertex v whose
degree is zero is called isolated; in our example v3 is isolated since
d(v3) = 0. Lemma 1.1: The number of vertices of odd degree in a finite graph is
even. Proof: Let |V| and |E| be the number of vertices and edges, respectively.
Then, [pic] since each edge contributes two to the left hand side; one to the degree
of each of its two endpoints, if they are different, and two to the degree
of its endpoint if it is a self-loop. It follows that the number of odd
degrees must be even. Q.E.D. The notation u_e_v eans that the edge e has u and v as endpoints. In this
case we also say that e connects vertices u and v, and that u and v are
adjacent.
A path is a sequence of edges e1, e2, ... such that:
(1) ei and ei+1 have a common endpoint;
(2) if ei is not a self-loop and is not the first or last edge then it
shares one of its endpoints with ei-1 and the other with ei+1.
The exception specified in (2) is necessary to avoid the following
situation: Consider the graph represented in Figure 1.2.
We do not like to call the sequence e1, e2, e3 a path, and it is not,
since the only vertex, b, which is shared by e1 and e2 is also the only
vertex shared by e2 and e3. But we have no objection to calling e1, e4, e3
a path. Also, the sequence e1, e2, e2, e3 is a path since e1 and e2 share
b, e2 and e2 share d, e2 and e3 share b. It is convenient to describe a
path as follows: [pic]. Here the path is e1, e2, ..., el and the endpoints
shared are transparent; v0 is called the start and vl is called the end
vertex. The length of the path is l.
A circuit is a path whose start and end vertices are the same.
A path is called simple if no vertex appears on it more than once. A
circuit is called simple if no vertex, other than the start-end vertex,
appears more than once, and the start-end vertex does not appear elsewhere
in the circuit; however, [pic] is not considered a simple circuit.
If for every two vertices u and v there exists a path whose start vertex
is u and whose end vertex is v then the graph is called connected.
A digraph (or directed graph) is defined similarly to a graph except that
the pair of endpoints of an edge is now ordered; the first endpoint is
called the start-vertex of the edge and the second (which may be the same)
is called its end-vertex. The edge ([pic]) e is said to be directed from u
to v. Edges with the same start vertex and the same end vertex are called
parallel, and if u ( v, [pic] and [pic] then e1 and e2 are antiparallel. An
edge u ( u is called a self-loop.
The outdegree, dout(v), of a vertex v is the number of edges which have v
as their start-vertex; indegree, din(v), is defined similarly. Clearly, for
every graph
[pic]
A directed path is a sequence of edges e1, e2, ... such that the end
vertex of ei-1 is the start vertex of ei. A directed path is a directed
circuit if the start vertex of the path is the same as its end vertex. The
notion of a directed path or circuit being simple is defined similarly to
that in the undirected case. A digraph is said to be strongly connected if
for every vertex u and every vertex v there is a directed path from u to v;
namely, its start-vertex is u and its end-vertex is v. 1.2 COMPUTER REPRESENTATION OF GRAPHS
In order to understand the time and space complexities of graph
algorithms one needs to know how graphs are represented in the computer
memory. In this section two of the most common methods of graph
representation are briefly described.
Graphs and digraphs which have no parallel edges are called simple. In
cases of simple graphs, the specification of the two endpoints is
sufficient to specify the edge; in cases of digraph the specification of
the start-vertex and end-vertex is sufficient. Thus, we can represent a
graph or digraph of n vertices by an n ( n matrix C, where Cij= 1 if there
is an edge connecting vertex vi to vj and Cij= 0, if not. Clearly, in the
case of graphs Cij= 1 implies Ci = 1; or in other words, C is symmetric.
But in the case of digraphs, any n ( n matrix of zeros and ones is
possible. This matrix is called the adjacency matrix.
Given the adjacency matrix of a graph, one can compute d(vi) by counting
the number of ones in the ith row, except that a one on the main diagonal
contributes two to the count. For a digraph, the number of ones in the i
row is equal to dout(vi) and the number of ones in the i column is equal to
din(vi).
The adjacency matrix is not an efficient representation of the graph in
case the graph is sparse; namely, the number of edges is significantly
smaller than n2. In these cases the following representation, which also
allows parallel edges, is preferred.
For each of the vertices, the edges incident to it are listed. This
incidence list may simply be an array or may be a linked list. We may need
a table which tells us the location of the list for each vertex and a table
which tells us for each edge its two endpoints (or start-vertex and end-
vertex, in case of a digraph).
We can now trace a path starting from a vertex, by taking the first edge
on its incidence list, look up its other endpoint in the edge table,
finding the incidence list of this new vertex etc. This saves the time of
scanning the row of the matrix, looking for a one. However, the saving is
real only if n is large and the graph is sparse, for instead of using one
bit per edge, we now use edge names and auxiliary pointers necessary in our
data structure. Clearly, the space required is O(|E| + |V|), i.e., bounded
by a constant times |E| + |V|. Here we assume that the basic word length of
our computer is large enough to encode all edges and vertices. If this
assumption is false then the space required is O((|E| + |V|) log (|E| +
|V|))( .
In practice, most graphs are sparse. Namely, the ratio (|E| + |V|)/|V|2
tends to zero as the size of the graphs increases. Therefore, we shall
prefer the use of incidence lists to that of adjacency matrices.
The reader can find more about data structures and their uses in graph
theoretic algorithms in references 1 and 2.
1.3 EULER GRAPHS
An Euler path of a finite undirected graph G(V, E) is a path e1, e2,...,
el such that every edge appears on it exactly once; thus, l = |E|. An
undirected graph which has an Euler path is called an Euler graph.
Theorem 1.1: A finite (undirected) connected graph is an Euler graph if
and only if exactly two vertices are of odd degree or all vertices are of
even degree. In the latter case, every Euler path of the graph is a
circuit, and in the former case, none is.
As an immediate conclusion of Theorem 1.1 we observe that none of the
graphs in Figure 1.3 is an Euler graph, because both have four vertices of
odd degree. The graph shown in Figure 1.3(a) is the famous K(nigsberg
bridge problem solved by Euler in 1736. The graph shown in Figure 1.3(b) is
a common misleading puzzle of the type "draw without lifting your pen from
the paper".
Proof: It is clear that if a graph has an Euler path which is not a
circuit, then the start vertex and the end vertex of the path are of odd
degree, while all the other vertices are of even degree. Also, if a graph
has an Euler circuit, then all vertices are of even degree.
Assume now that G is a finite graph with exactly two vertices of odd
degree, a and b. We shall described now an algorithm for finding an Euler
path from a to b. Starting from a we choose any edge adjacent to it (an
edge of which a is an endpoint) and trace it (go to its other endpoint).
Upon entering a vertex we search for an unused incident edge. If the vertex
is neither a nor b, each time we pass through it we use up two of its
incident edges. The degree of the vertex is even. Thus, the number of
unused incident edges after leaving it is even. (Here again, a self-loop is
counted twice.) Therefore, upon entering it there is at least one unused
incident edge to leave by. Also, by a similar argument, whenever we reenter
a we have an unused edge to leave by. It follows that the only place this
process can stop is in b. So far we have found a path which starts in a,
ends in b, and the number of unused edges incident to any vertex is even.
Since the graph is connected, there must be at least one unused edge which
is incident to one of the vertices on the existing path from a to b.
Starting a trail from this vertex on unused edges, the only vertex in which
this process can end (because n