# cpts350 hw7 solution

\$30.00

Original Work ?

## Description

5/5 - (1 vote)

1. Let G be a color graph where each node has a color and multiple nodes
can 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
✷(yellow ∨ ✸blue) holds.

(2). Design an algorithm that decides where there is an ω-path on which
✷✸(yellow ∨ ✸blue) holds.

2. Let G be a color graph where each node has a color and multiple nodes
can 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 nodes
can 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 nodes
can 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.