Please use the appropriate notations and please explain thoroughly,i really have
ID: 3665408 • Letter: P
Question
Please use the appropriate notations and please explain thoroughly,i really have a problem with understanding these(just dont answer if you dont want to explain)
also please make it readable
your help is very much appreciated
8.5. Give a simple reduction from 3D MATCHING to SAT, and another from RUDRATA CYCLE to SAT. (Hint: In the latter case you may use variables rij whose intuitive meaning is "vertex i is the jth vertex of the Hamilton cycle"; you then need to write clauses that express the constraints of the problem.)Explanation / Answer
Rudrata (s, t)-Path
Given: G = (V, E) and s, t V.
Find: A path from s to t in G passing through
each vertex once.
Rudrata Cycle Given: G = (V, E).
Find: A cycle in G passing through each vertex once.
Rudrata (s, t)-Path E Rudrata Cycle:
Given an instance of Rudrata (s, t)-Path: (G,s, t) construct G 0 by adding an new vertex x and new edges (x,s) and (x, t).
If P is a Rudrata-cyclc in G 0 , then leaving x, (x,s) and (x, t) out of P gives an (s, t)-Rudrata path in G.
If G has a (s, t)-Rudrata path P, then adding (x,s) and (x, t) to P yields a Rudrata cycle in G 0 .
If G 0 has no Rudrata cycle, then G has no (s, t)-Rudrata path. NP-Completeness