Q17E Infinite paths.聽Let G=(V,E)聽 b... [FREE SOLUTION]

91影视

Algorithms

Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani

Computer Science

1st Edition 路 333 pages

ISBN: 9780073523408

Chapter 3: Q17E (page 109)

Infinite paths.Let $G = (V, E)$ be a directed graph with a designated 鈥渟tart vertex鈥� $s 鈭� V, a set V_{G} 鈯� V$ , a set of 鈥済ood鈥� vertices, and a set $V_{B} 鈯� V$ of 鈥渂ad鈥� vertices. An infinite trace of is an infinite sequence of vertices $v_{i} 鈭� V$ such that $(1) v_{0} = s$ , and (2) for all $i 鈮� 0$ , $(v_{i}, v_{i + 1}) 鈭� 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) 鈯� 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 鈮� 0$ , $i + 1$

if $v_{i}, v_{i + 1} 鈭� 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 鈮� 0, i + 1 if v_{i}, v_{i + 1} 鈭� E if v_{i + 1} 鈭� 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 鈮� 0, i + 1 if v_{i}, v_{i + 1} 鈭� E if v_{i}, v_{i + 1} 鈭� 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 鈮� 0, (v_{i}, v_{i + 1}) 鈭� 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 鈥渟tart vertex鈥� $s 鈭� V$ , a set localid="1659074912703" $V_{G} = 鈯� V$ of 鈥済ood鈥� vertices, and a set $V_{B} = 鈯� V$ of 鈥渂ad鈥� 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 鈥渟tart vertex鈥� $s 鈭� V$ , a set role="math" localid="1659075365201" $V_{G} = 鈯� V$ of 鈥済ood鈥� vertices, and a set $V_{B} = 鈯� V$ of 鈥渂ad鈥� 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 鈮� 0, i + 1 i f v_{i}, v_{i + 1} 鈭� 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 鈥渟tart vertex鈥� $s 鈭� V$ , a set $V_{G} = 鈯� V$ of 鈥済ood鈥� vertices, and a set role="math" localid="1659075463049" $V_{B} = 鈯� V$ of 鈥渂ad鈥� 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 鈮� 0, i + 1 i f v_{i}, v_{i + 1} 鈭� E i f v_{i + 1} 鈭� 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 鈥渟tart vertex鈥� $s 鈭� V$ , a set $V_{G} 鈯� V$ of 鈥済ood鈥� vertices, and a set $V_{B} 鈯� V$ of 鈥渂ad鈥� 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 鈮� 0, i + 1 if v_{1}, v_{i + 1} 鈭� E if v_{i + 1} 鈭� V_{G} if v_{i + 1} 鈭� 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.