Sunday, August 4, 2024

# Notion of path in a graph

### Create QR Code for Pages & Post using Plugin in WordPress

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

Previous article