Let G be a directed graph. Let s be a ‘start vertex’. An infinite path of G is an infinite sequence v0, v1, v2, ... of vertices such that v0 = s and for all i> 0, there is an edge from vi to vi+1. In other words, this is a path of infinite length. Because G has a finite number of vertices, some vertices in an infinite path are visited infinitely often.

1. If p is an infinite path, let Inf(p) be the set of vertices that occur infinitely many times in p. Prove that Inf(p) is a subset of a single strongly connected component of G.

2. Describe an algorithm to determine if G has an infinite path. Prove that it is correct.

Answer rating: 100% (QA)

1 Let us consider the following graph Let us consider an infinite path here P V 0 V 1 V 2 V 3 V 4 V 5 V 2 Here we can see that infp is the set as foll... View the full answer