A Hamiltonian Cycle is a simple path beginning and ending at the same vertex that visits...

 

Transcribed Image Text:

A Hamiltonian Cycle is a simple path beginning and ending at the same vertex that visits every node exactly once. Remember that in a simple path repeated edges are not allowed. DHC = {(D) | D is a directed graph that contains a Hamiltonian Cycle} HC = {(G) | G is a undirected graph that contains a Hamiltonian Cycle } Prove that DHC ≤ HC Hint, for every node, v₁, in the directed graph D replace it with three nodes, inį, midį, outį, in the new undirected graph, G. Add edges (in,, midi) and (midi, out;) to G. Now for every edge, (u, v), in D add and edge from (outu, inv) to G. A Hamiltonian Cycle is a simple path beginning and ending at the same vertex that visits every node exactly once. Remember that in a simple path repeated edges are not allowed. DHC = {(D) | D is a directed graph that contains a Hamiltonian Cycle} HC = {(G) | G is a undirected graph that contains a Hamiltonian Cycle } Prove that DHC ≤ HC Hint, for every node, v₁, in the directed graph D replace it with three nodes, inį, midį, outį, in the new undirected graph, G. Add edges (in,, midi) and (midi, out;) to G. Now for every edge, (u, v), in D add and edge from (outu, inv) to G.

Answer rating: 100% (QA)

Answer We will prove that DHC is a subset of HC by showing that for any given directed graph D in DHC a corresponding undirected graph G can be constr... View the full answer