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(yellow∨3blue) holds.
(2). Design an algorithm that decides where there is an ω-path on which 23(yellow∨3blue) 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
