Chapter 3: Q17E (page 109)

Infinite paths.Let $G = (V, E)$ be a directed graph with a designated “start vertex” $s \in V, a set V_{G} \subseteq V$ , a set of “good” vertices, and a set $V_{B} \subseteq V$ of “bad” vertices. An infinite trace of is an infinite sequence of vertices $v_{i} \in V$ such that $(1) v_{0} = s$ , and (2) for all $i \geq 0$ , $(v_{i}, v_{i + 1}) \in E$ . That is, $p$ is an infinite path in $G$ starting at vertex $s$ . Since the set $V$ of vertices is finite, every infinite trace of $G$ must visit some vertices infinitely often.
If $p$ is an infinite trace, let $I n f (p) \subseteq V$ be the set of vertices that occur infinitely often in $p$ . Show that $I n f (p)$ is a subset of a strongly connected component of $G$ .
Describe an algorithm that determines if role="math" $G$ has an infinite trace.
Describe an algorithm that determines if $G$ has an infinite trace that visits some good vertex in $V_{G}$ infinitely often.
Describe an algorithm that determines if role="math" localid="1659627728759" $G$ has an infinite trace that visits some good vertex in $V_{G}$ infinitely often, but visits no bad vertex in $V_{B}$ infinitely often.

Short Answer

Expert verified

a. All nodes in inf (p) are visited infinite times, thus inf (p) is a subset of a strongly connected component of G .

b. An algorithm:

Input: G = (V, E)

Procedure: inf (p)

p= V [i]

$v_{0} = s$

for i = 0, $i \geq 0$ , $i + 1$

if $v_{i}, v_{i + 1} \in E$

return $I n f (p)$

print G has an infinite trace.

c. Algorithm:

Input: G = (V, E)

Procedure: Inf (p)

$good_vertices = V_{G} [v] bad_vertices = V_{B} [v] p = v [i] v_{0} = s for i = 0, i \geq 0, i + 1 if v_{i}, v_{i + 1} \in E if v_{i + 1} \in V_{G} return Inf (p)$

print has an infinite trace that visits good vertices.

d. Algorithm:

Input: G = (V, E)

Procedure: Inf (p)

$good_vertices = V_{G} [v] bad_vertices = V_{B} [v] p = V [i] v_{0} = s for i = 0, i \geq 0, i + 1 if v_{i}, v_{i + 1} \in E if v_{i}, v_{i + 1} \notin V_{B} return Inf (p)$

print G has an infinite trace that visits good vertices has no bad vertices.

Step by step solution

Explain Infinite paths.

An infinite trace p of G is an infinite sequence $v_{0} v_{1} v_{2} K$ of vertices such that $v_{0} = s$ , and for all $i \geq 0, (v_{i}, v_{i + 1}) \in E$ , .

Show that lnf (p) is a subset of a strongly connected component of G .

(a)

Consider the directed graph G=(V,E) with a designated “start vertex” $s \in V$ , a set localid="1659074912703" $V_{G} = \subset V$ of “good” vertices, and a set $V_{B} = \subset V$ of “bad” vertices. That is, p is an infinite path in G starting at vertex s . Since the set Vof vertices is finite, every infinite trace of Gmust visit some vertices infinitely often.

All nodes in Inf ( p ) are visited infinite times, thus Inf ( p ) is a subset of a strongly connected component of G .

Therefore, It has been shown that Inf ( p ) is a subset of a strongly connected component of G .

Describe an algorithm that determines if G has an infinite trace.

(b)

Consider the directed graph $G = (V, E)$ with a designated “start vertex” $s \in V$ , a set role="math" localid="1659075365201" $V_{G} = \subset V$ of “good” vertices, and a set $V_{B} = \subset V$ of “bad” vertices.

An algorithm that determines if G has an infinite trace.

$I n p u t : (V, E) p r o c e d u r e : I n f (p) p = v [i] v_{0} = s f o r i = 0, i \geq 0, i + 1 i f v_{i}, v_{i + 1} \in E return I n f (p) print G has an infinite trace .$

The above algorithm determines if the given graph has an infinite trace by checking the edges and vertices of the graph.

Therefore, An algorithm has be describes to determine if G has an infinite trace.

Describe an algorithm that determines if G has an infinite trace that visit good vertices

(c)

Consider the directed graph G = ( V,E ) with a designated “start vertex” $s \in V$ , a set $V_{G} = \subset V$ of “good” vertices, and a set role="math" localid="1659075463049" $V_{B} = \subset V$ of “bad” vertices.

An algorithm that determines if G has an infinite trace.

$I n p u t : G = (V, E) P r o c e d u r e : I n f (p) g o o d_v e r t i c e s = V_{G} [v] b a d_v e r t i c e s = V_{B} [v] p = v [i] v_{0} = s f o r i = 0, i \geq 0, i + 1 i f v_{i}, v_{i + 1} \in E i f v_{i + 1} \in V_{G} r e t u r n i n f (p) p r i n t G h a s a n i n f i n i t e t r a c e t h a t v i s i t s g o o d v e r t i c e s .$

The above algorithm determines if the given graph has an infinite trace that visits good vertices often by checking the edges and good vertices of the graph.

Therefore, An algorithm has be describes to determine if G has an infinite trace that often visits good vertices.

Describe an algorithm that determines if G has an infinite trace that visit no bad vertices

(d)

Consider the directed graph G = (V,E) with a designated “start vertex” $s \in V$ , a set $V_{G} \subset V$ of “good” vertices, and a set $V_{B} \subset V$ of “bad” vertices.

An algorithm that determines if G has an infinite trace.

$I n p u t : G = (V, E) P r o c e d u r e : I n f (p) g o o d_v e r t i c e s = V_{G} [v] b a d_v e r t i c e s = V_{B} [v] p = v [i] v_{G} = s f o r i = 0, i \geq 0, i + 1 if v_{1}, v_{i + 1} \in E if v_{i + 1} \in V_{G} if v_{i + 1} \notin V_{B} r e t u r n I n f (p) p r i n t G h a s a n i n f i n i t e t r a c e t h a t v i s i t s g o o d v e r t i c e s h a s n o b a d v e r t i c e s .$

The above algorithm determines if the given graph has an infinite trace that visits good vertices often by checking the edges and bad vertices of the graph.

Therefore, An algorithm has be describes to determine if G has an infinite trace that often visits good vertices and no bad vertices.