Exercise 23 | RACSO

Exercise _‹23_›:

DIRECTED HAMILTONIAN CIRCUIT

\leq

UNDIRECTED HAMILTONIAN CIRCUIT

Reduce the DIRECTED HAMILTONIAN CIRCUIT problem to the UNDIRECTED HAMILTONIAN CIRCUIT problem. These problems are defined as follows:

DIRECTED HAMILTONIAN CIRCUIT: given a directed graph $G$ , is there a directed cycle that visits each node of $G$ exactly once? In other words, is it possible to order the nodes of $G$ such that there is an edge from each node to the following node in the list and an edge from the last node to the first node?
More formally, this problem can be defined as the following set:
$\{ G=\langle V,E\rangle \mid V=\{n_1,\ldots,n_k\}\;\wedge\;\forall i\in\{1,\ldots,k\}: \langle n_i,n_{(i\text{ mod }k)+1}\rangle\in E \}$
UNDIRECTED HAMILTONIAN CIRCUIT: given an undirected graph $G$ , is there a cycle that visits each node of $G$ exactly once? In other words, is it possible to order the nodes of $G$ such that there is an edge between each $2$ contiguous nodes and an edge between the last and the first nodes?
More formally, this problem can be defined as the following set:
$\{ G=\langle V,E\rangle \mid V=\{n_1,\ldots,n_k\}\;\wedge\;\forall i\in\{1,\ldots,k\}: \{n_i,n_{(i\text{ mod }k)+1}\}\in E \}$

The input and output of the reduction conform to the following data types:

```
in: struct {
      numnodes: int
      edges: array of array [2] of int
      adjacencymatrix: array of array of int
    }
```
The input is a directed graph. The graph is given by means of three different kinds of information: the number of nodes in.numnodes, the list of directed edges in.edges, and the adjacency matrix in.adjacencymatrix. The nodes are integers between $1$ and in.numnodes, and thus, the $0$ ’th row and column of in.adjacencymatrix do not contain useful data and should be ignored; for any other row $r$ and column $c$ , in.adjacencymatrix[r][c] is $0$ when there is no edge from the node $r$ to the node $c$ , and $1$ otherwise. An edge of in.edges is an ordered pair of nodes, directed from the first node to the second node.

Note: The input graph has at least $2$ nodes, no repeated edges, nor self-loop edges.
```
out: struct {
       edges: array of array [2] of string
       nodes: array of string
     }
```
The output is an undirected graph, which is described with the list of edges out.edges and with the list of nodes out.nodes. An edge is a pair of nodes, and each node is represented by either an integer or a string. The list of nodes out.nodes is optional, and contains nodes of the graph, that may or may not appear in the list of edges. This list of nodes could be useful, for example, for including the nodes that are not connected to any other node, if this is considered necessary.

Note: If the output graph has no nodes, it is considered that it has a cycle. If it has self-loop edges, they are taken into account since, in the particular case of $1$ -node graphs, they make it possible to have a cycle. Repeated edges are ignored.

Authors: Carles Creus / Documentation:

Exercise ‹23›:

Exercise _‹23_›: