Graph Theory/Traversals

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.

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

  Sample graph to see traversal examples

  Sample graph to see traversal examples

  • 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.

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.

Theorem

If a graph G contains a u-v walk of length $\ell$, then G contains a u-v path of length ≤$\ell$.
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 $P:u=u_0,u_1,\dots ,u_{\ell }=v$, where $\ell$ is the length of P.

And, we know that $u_i=u_j$ for some $0\le i<j\le \ell$.

Then, remove the repeated vertex(ices) to get $P^{\prime }:u=u_0,u_1,\dots ,u_i,u_{j+1},\dots ,u_{\ell }=v$. 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 $\ell$.

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

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).