The VERTEX COVER problem is the following. You are given an undirected graph G and a...

Transcribed Image Text:

The VERTEX COVER problem is the following. You are given an undirected graph G and a number K. The task is to find a set of vertices S of size K such that every edge in the graph has at least one vertex in S. For instance, in the graph below, (B, D, E, F, G, I) is a vertex cover of size 6. A VERTEX COVER problem can be translated into propositional calculus as follows: Use atoms of the form vi meaning that v is the ith element in some listing of the set. For instance for the above example, there would be 60 atoms A1, A2, ... A6, B1 ... 6. One valuation corresponding to the ordering (E, D, G, B, I, F) would have E1, D2, G3, B4, 15, F6 assigned TRUE, and the other 54 atoms assigned FALSE. F E H I J Describe the categories of propositions needed to encode a VERTEX COVER problem as problem in propositional calculus. Illustrate each category with a particular proposition for the above example. Please note: For each category there are two separate things. First, there is a description of the category. That should be applicable to the VERTEX COVER problem on any graph, not just to the one above. It should not make reference to any features that are specific to the example above. Second, there is an example of one rule from this category as it would apply to the above example. The rules in programming assignment 2 are a good example of the kind of answer I am looking for here. The VERTEX COVER problem is the following. You are given an undirected graph G and a number K. The task is to find a set of vertices S of size K such that every edge in the graph has at least one vertex in S. For instance, in the graph below, (B, D, E, F, G, I) is a vertex cover of size 6. A VERTEX COVER problem can be translated into propositional calculus as follows: Use atoms of the form vi meaning that v is the ith element in some listing of the set. For instance for the above example, there would be 60 atoms A1, A2, ... A6, B1 ... 6. One valuation corresponding to the ordering (E, D, G, B, I, F) would have E1, D2, G3, B4, 15, F6 assigned TRUE, and the other 54 atoms assigned FALSE. F E H I J Describe the categories of propositions needed to encode a VERTEX COVER problem as problem in propositional calculus. Illustrate each category with a particular proposition for the above example. Please note: For each category there are two separate things. First, there is a description of the category. That should be applicable to the VERTEX COVER problem on any graph, not just to the one above. It should not make reference to any features that are specific to the example above. Second, there is an example of one rule from this category as it would apply to the above example. The rules in programming assignment 2 are a good example of the kind of answer I am looking for here.