Problem 2. Consider the CNF x1bar means complement of x1 etc. (x1 or x2bar or x3

Question

Problem 2.
Consider the CNF x1bar means complement of x1 etc.
(x1 or x2bar or x3) and (x1bar or x2 or x3) and (x1 or x3bar) and (x2 and x3bar or x4)
Convert this to the graph G=(V,E) so that this G will have a clique of size 4 if and only if CNF is satisfiable. Will G have a clique of size 4?
Change largest vertex cover to smallest vertex cover. - largest is easy!

Problem 3.
For the graph G=(V,E) above, construct Gbar., the complement graph.   What is the largest clique in G? what is the largest vertex cover in Gbar?

PLEASE ANSWER DIRECTLY

Explanation / Answer

Answer to problem 3 :

A maximum clique is a clique of the largest possible size in a given graph. The clique number (G) of a graph G is the number of vertices in the largest clique in G. An adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge. The complement GC of a graph G contains exactly those edges not in G
Conclusion: G has a clique of size k iff GC has a vertex cover of size |V| - k

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.