Discrete Mathematics

------------------------------------------------------------RELATIONS

133

In the graph, a walk is something we can trace out by following arrows from vertex to vertex, without lifting

our pen. Note that a singleton vertex

is

not

a length 0 walk (this is just for convenience).

Definition A simple path is a walk with no repeated vertices.

Many people say path when they mean simple path, so we will use walk to allow for possibly non-simple

paths.

Walks give us the terminology for transitive closure.

=----

Lemma

The transitive closure

of

a relation R is that set

S

={(a,

b) I there is a walk from a

tobin

R}

I Proof I First let us

showS

is transitive. ...