Graph Theory/Traversals

From Wikibooks, the open-content textbooks collection

This book has been created on 19 June 2009, and still is under heavy construction. Content that is added is likely to be moved/deleted/edited significantly in a short amount of time. All wikibookians with knowledge in this subject are welcome to help out. You can remove this tag when the book has become more mature.

When examining a graph, quite often we will need to know the various ways to get from one vertex to another, and the different types of traversals this can take.

Contents 1 Moving around in a graph 2 Distance in a Graph 2.1 Theorem 3 Geodesics 4 More Graph Parameters

[edit] Moving around in a graph

• A u-v walk is defined as a sequence of vertices starting at u and ending at v, where consecutive vertices in the sequence are adjacent vertices in the graph
  
  • A closed walk is a walk in which the first and last vertices are the same
• A u-v trail a u-v walk, where no edge is repeated (each edge is used at most once)
  • A circuit or closed trail is a trail in which the first and last vertices are the same
• A u-v path is a u-v walk, where no vertex is repeated (each vertex is used at most once)
  • A cycle is a closed path in which the first and last vertices are the same

For example, in the image to the right, ABCBEF is a walk. ABCDEFA, BCDEB, and BCDB are cycles.

[edit] Distance in a Graph

Now, we need to define a concept of distance in a graph; this helps us encode more data in the graph.

Length of a walk 

the number of edges used in a particular walk.

If an edge is used more than once, then it is counted more than once.
A trivial walk is one where the length is 0.

[edit] Theorem

If a graph G contains a u-v walk of length , then G contains a u-v path of length ≤.
Proof:

Let P be a u-v walk of shortest length. We claim that P is a path (since being the shortest, it eliminates repeated vertices).

Suppose not. Suppose that P is not a path. Then, at least one vertex is repeated (used twice). Then, set , where is the length of P.

And, we know that u_i = u_j for some .

Then, remove the repeated vertex(ices) to get . But, then we get that the length of P' is smaller than the length of P, which contradicts our assumption that P was the walk of shortest length.

So, P must be a path, and it is shorter than any other walk that has vertices in P.

Thus, there is a u-v path of length at most .

[edit] Geodesics

For any two vertices u and v in a graph G, the distance between u and v is defined to be the length of the shortest path between u and v, denoted d(u,v).

A path of length d(u,v) is called a geodesic.

Properties of d(u,v):
For a geodesic P:u=u₁u₂...u_k=v and some 0≤i,j≤k:

1. d(u₀u_k) = k
2. d(u_iu_i) = 0 (not travelling anywhere)
3. d(u₀u_i) = i
4. d(u_iu_j) = |j-i|

[edit] More Graph Parameters

Using d(u,v), we can find other parameters of the graph G:

• Diameter: the diameter diam(G) is the largest distance d(u,v) between any two vertices of a connected graph; i.e. diameter is the max{d(u,v)} for all sets of u,v in V(G).