cpts350 hw7
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.
1
