110 CHAPTER 2 Discrete Mathematics
Other definitions are as follows. An edge is called aloopif it joins
a vertex to itself (see the above figure). Letvi andvj be vertices in a
graph. We say thatvi andvj areadjacentif there is an edge joining
viandvj (that is if the costcij>0). Also,
Awalkin a graph is a sequence of linked edges.
Atrail in a graph is a sequence of linked edges such that no edge
appears more than one.
Apathin a graph is a walk with no repeated vertices.
Acircuitin a graph is a trail that begins and ends at the same vertex.
Acyclein a graph is a path which begins and ends at the same vertex.
If any two vertices of a graph can be joined by a path, then the
graph is calledconnected.
2.2.1 Eulerian trails and circuits
Suppose that a postman is charged with delivering mail to residences
in a given town. In order to accomplish this in an efficient manner he