The notion of a path in a graph is clear and is shown below
• Suppose G (V,E) is a graph with vertices v¬0, v1,v2,……,vk. and edges are e1,e2,……..,ek in which edge ei={vi-1,vi} for i= 1,…,k.
• The alternating sequence that I get of vertices and edges , starting from the vertice v0 to vk is a path from v0 to vk of length k. The length is the number of edges and it is not the number of vertices.
• The length of the path is 1,2, 3 and 4 so here is a 4 length path. And the path is made up of edges e1,e2,e3,e4 and it had vertices va, vb, vc .So the path from the start to goal for the given graph is s, e1,va, e2,vb,e3,vc,e4, g.
Directed graph(Digraph)
A directed graph or a Digraph in short consists of a set V of vertices and asset E of directed edges.
•A directed edge is an ordered pair of elements of V .put another way the pair G(V,E) with E is a sub set of VxV is a digraph
•Digraphs allow for loops of the form (a, a), it is also possible to have two edges (a, b) and (b, a) between the vertices a and b
•We take the ordering of pairs in E to give each edge a direction: namely the edge (a, b) goes from a to b.
•If we draw a digraph ,we draw the edge (a, b) as an arrow from a to b.
Example:
V= {a, b, c, d}
E= {(a ,b),(a, c),(b, a),(c, c),(d, c)}