Please type your solution very clearly
- Theory Of Computation Please Type Your Solution Very Clearly 1 (164.24 KiB) Viewed 75 times
Theory of Computation. Please type your solution very clearly
-
answerhappygod
- Site Admin
- Posts: 899603
- Joined: Mon Aug 02, 2021 8:13 am
Theory of Computation. Please type your solution very clearly
Theory of Computation.
Please type your solution very clearly
(10 points) A graph G is said to be 2-colorable if we can assign every vertex one of two colors (say, red or green), with the constraint that two vertices that are connected by an edge must have opposite colors. The following image illustrates the problem. Notice how there is no edge connecting two vertices with the same color. All of the adjacent vertices have opposite colors. Thus, this graph is 2-colorable. D A F B H By contrast, a triangle graph is not 2-colorable ? Formally we will work with the following language 2-COLORING = {(G) G is a 2-colorable graph} Prove that 2-COLORING E P. (Hint: One approach is to use a greedy coloring algorithm. Another - elegant- is to convert the graph into a 2-SAT formula).
Please type your solution very clearly
(10 points) A graph G is said to be 2-colorable if we can assign every vertex one of two colors (say, red or green), with the constraint that two vertices that are connected by an edge must have opposite colors. The following image illustrates the problem. Notice how there is no edge connecting two vertices with the same color. All of the adjacent vertices have opposite colors. Thus, this graph is 2-colorable. D A F B H By contrast, a triangle graph is not 2-colorable ? Formally we will work with the following language 2-COLORING = {(G) G is a 2-colorable graph} Prove that 2-COLORING E P. (Hint: One approach is to use a greedy coloring algorithm. Another - elegant- is to convert the graph into a 2-SAT formula).