Question

Determine whether there is a path in the directed graph in Exercise 16 beginning at the first vertex given and ending at the second vertex given.

a)\(a,b\)

b)\(b,a\)

c)\(b,b\)

d)\(a,e\)

e)\(b,d\)

f)\(c,d\)

g)\(d,d\)

h)\(e,a\)

i)\(e,c\)

Short answer

(a) There is a path

(b) There is a path

(c) There is a path

(d) There is a path

(e) There is a path

(f) There is a path

(g) There is a path

(h) There is a path

(i) There is a path

Step-by-step solution

Given

The graph is,

Concept of Path in a directed graph

A path in a directed graph\(G\)is a sequence of edges in\(G\).

Find the Path for (a)

a)

There is a path from vertex \(a\) to vertex \(b\), because the directed graph contains \((a,b)\) (since there is an arrow from vertex \(a\) to vertex \(b\).

Find the Path for (b)

b)

\(b,e,a\) is a path from \(b\) to \(a\), because the directed graph contains \((b,e)\) and \((e,a)\).

Find the Path for (c)

c)

\(b,e,a,b\)is a path from\(b\)to\(b\), because the directed graph contains\((b,e),(e,a)\)and\((a,b)\).

\(b,c,b\) is also a path from \(b\) to \(b\).

Find the Path for (d)

d)

\(a,b,e\)is a path from\(a\)to\(e\), because the directed graph contains\((a,b)\)and\((b,e)\).

\(a,d,e\) is also a path from \(a\) to \(e\).

Find the Path for (e)

e)

\(b,e,d\)is a path from \(b\) to \(d\), because the directed graph contains \((b,e)\) and \((e,d)\).

Find the Path for (f)

f)

\(c,e,d\) is a path from \(c\) to \(d\), because the directed graph contains \((c,e)\) and \((e,d)\).

Find the Path for (g)

g)

\(d,e,a,d\) is a path from \(d\) to \(d\), because the directed graph contains \((d,e),(e,a)\) and \((a,d)\)

Find the Path for (h)

h)

There is a path from vertex \(e\) to vertex \(a\), because the directed graph contains \((e,a)\) (since there is an arrow from vertex \(e\) to vertex \(a\).

Find the Path for (i)

i)

\(e,a,b,c\) is a path from \(e\) to \(c\), because the directed graph contains \((e,a),(a,b)\) and \((b,c)\)