Infinite paths. Let G = (V, E) be a directed graph with a designated start vertex s V

QUESTION:

Infinite paths. Let G = (V, E) be a directed graph with a designated start vertex s V , a setVG V of good vertices, and a set VB V of bad vertices. An infinite trace p of G is an infinitesequence v0v1v2 of vertices vi V such that (1) v0 = s, and (2) for all i 0, (vi, vi+1) E. Thatis, p is an infinite path in G starting at vertex s. Since the set V of vertices is finite, every infinitetrace of G must visit some vertices infinitely often.(a) If p is an infinite trace, let Inf(p) V be the set of vertices that occur infinitely often in p.Show that Inf(p) is a subset of a strongly connected component of G.(b) Describe an algorithm that determines if G has an infinite trace.(c) Describe an algorithm that determines if G has an infinite trace that visits some good vertexin VG infinitely often.(d) Describe an algorithm that determines if G has an infinite trace that visits some good vertexin VG infinitely often, but visits no bad vertex in VB infinitely often.