[Solved] cpts350 hw7

1. Let G be a color graph where each node has a color and multiple nodescan share the same color. In particular, there is a designated initial node. An -path is an infinite walk on G that starts from the initial.

(1). Design an algorithm that decides where there is an -path on which

2(yellow3blue) holds.

(2). Design an algorithm that decides where there is an -path on which 23(yellow3blue) holds.

2. Let G be a color graph where each node has a color and multiple nodescan share the same color. In particular, there is a designated initial node. An -path is an infinite walk on G that starts from the initial. Design an algoirthm to decide whether there is an -path on which it passes red nodes for infinitely many times and passes blue nodes for only finitely many times.
3. Let G be a color graph where each node has a color and multiple nodescan share the same color. In particular, there is a designated initial node. An -path is an infinite walk on G that starts from the initial. A good path is is one where there are infinitely many prefixes, each of which satisfies the following condition: the number of red nodes equals the number of blue nodes. Design an algoirthm to decide whether there is a good -path.
4. Let G be a color graph where each node has a color and multiple nodescan share the same color. In particular, there is a designated initial node. An -path is an infinite walk on G that starts from the initial. A bad -path is is one where there are infinitely many prefixes, each of which satisfies the following condition: the number of red nodes is a multiple of 5. Design an algoirthm to decide whether there is a bad -path.

1