category of paths on a graph

A nice class of illustrative examples of some notions of category theoryMathworldPlanetmathPlanetmathPlanetmathPlanetmath is provided by categoriesMathworldPlanetmath of paths on a graph.

Let G be an undirected graph. Denote the set of vertices of G by “V” and denote the set of edges of G by “E”.

A path of the graph G is an ordered tuplet of vertices (x1,x2,xn) such that, for all i between 1 and n-1, there exists an edge connecting xi and xi+i. As a special case, we allow trivial paths which consist of a single vertex — soon we will see that these in fact play an important role as identity elementsMathworldPlanetmath in our category.

In our category, the vertices of the graph will be the objects and the morphismsMathworldPlanetmath will be paths; given two of these objects a and b, we set Hom(a,b) to be the set of all paths (x1,x2,xn) such that x1=a and xn=b. Given an object a, we set 1a=(a), the trivial path mentioned above.

To finish specifying our category, we need to specify the composition operation. This operationMathworldPlanetmath will be the concatenation of paths, which is defined as follows: Given a path (x1,x2,,xn)Hom(a,b) and a path (y1,y2,,ym)Hom(a,b), we set


(Remember that xn=y1=b.) To have a bona fide category, we need to check that this choice satisfies the defining properties (A1 - A3 in the entry This is rather easily verified.

A1: Given a morphism (x1,x2,xn), it can only belong to Hom(a,b) if x1=a and xn=b, hence Hom(a,b)Hom(c,d)= unless a=c and b=d.

A2: Suppose that we have four objects a,b,c,d and three morphisms, (x1,x2,xn)Hom(a,b), (y1,y2,ym)Hom(b,c), and (z1,z2,zk)Hom(c,d). Then, by the definition of the operation given above,

((x1,x2,,xn)( y1,y2,,ym))(z1,z2,,zk)
(x1,x2,,xn)( (y1,y2,,ym)(z1,z2,,zk))

Since these two quantities are equal, the operation is associative.

A3: It is easy enough to check that paths with a single vertex act as identity elements:

(x1)(x1,x2,,xn) =(x1,x2,,xn)
(x1,x2,,xn)(xn) =(x1,x2,,xn)

It is also possible to consider the equivalence classMathworldPlanetmathPlanetmath of paths modulo retracing. To introduce this category, we first define a binary relationMathworldPlanetmath on the class of paths as follows: Let A and B be any two paths such that the right endpointMathworldPlanetmath of A is the same as the left endpoint of B, i.e. AHom(a,b) and BHom(b,c) for some vertices a,b,c of our graph. Let d be any vertex which shares an edge with d. Then we set ABA(c,d,c)B.

Let be the smallest equivalence relations which contains . We will call this equivalence relation retracing.

As defined above, it may not intuitively obvious what this equivalence amounts to. To this end, we may consider a different description. Define the reversal of a path to be the path obtained by reversing the order of the vertices traversed:


Then we may show that two paths are equivalentMathworldPlanetmathPlanetmathPlanetmath under retracing if they may both be obtained from a third path by inserting terms of the form XX-1. In symbols, we claim that AB if there exists an integer n>0 and paths X1,Xn+1,Y1,Yn-1,Z1,Zn such that




This characterization explains the choice of the term “retracing” — we do not change the equivalence class of the path if we happen to wander off somewhere in the course of following the path but then backtrack and pick the path up again where we left off on our digression.

Rather than presenting a detailed formal proof, we will sketch how the two definitions may be shown to be equivalent.

Title category of paths on a graph
Canonical name CategoryOfPathsOnAGraph
Date of creation 2013-03-22 16:45:54
Last modified on 2013-03-22 16:45:54
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 18
Author rspuzio (6075)
Entry type Example
Classification msc 20L05
Classification msc 18B40
Related topic IndexOfCategories