数据结构代写 | 5CCS2FC2: Foundations of Computing II

这个作业是完成数据结构中图相关的算法
5CCS2FC2: Foundations of Computing II

The CLIQUE problem takes as input an undirected graph G = (V, E) and an integer k > 2,
and returns True if G contains a clique of size k, i.e a set of vertices C ⊆ V such that |C| = k
and (u, v) ∈ E for all u, v ∈ C.
1. Write a function clique_solver(G,k) that takes a graph G (described below) and integer
k as input and return a Boolean: True in that case that G contains a clique of size k and
False otherwise.
[7 marks]
2. Write a function sat_to_clique(F) that takes a formula F (described below) as input and
return a graph G and integer k as output such that:
F is satisfiable ⇐⇒ G has a clique of size k.
[10 marks]
3. Write a function sat_solver(F) that makes use of your previous two functions and takes
a formula F as input and returns a Boolean: True in the case where F is satisfiable and
False otherwise. [3 marks]
Page 1 of 2
4. Describe in your own words, how your function sat_solver(F) works and why it is able to
successfully determine whether the input formula F is satisfiable. [5 marks]