9. Effective verifier

Loading [MathJax]/extensions/Safe.js

9. Effective verifier

The task this week is to write a Python program that implements an effective verifier algorithm deciding on a given graph that a given sequence of numbers represents a Hamiltonian cycle in the graph. (This task is preparing for a later topic in Algorithm theory where you will learn that the language HAM of graphs containing Hamiltonian cycles is in NP.)
It is easy to decide for a graph and a sequence of numbers that the sequence forms a Hamiltonian cycle in the graph – one just have to check that each vertex occurs exactly once and there are edges between each pair of consecutive vertices, and between the first and last vertex.
The file to be uploaded should be called hamilton.py. The program receives the input in the form of command line arguments in the next form:
```
    
    python3 hamilton.py graf.text witness.text
```
The first input (in the example graf.text) is a non directed simple graph that we enter in a text (.text) file
1. There are two natural numbers separated by spaces in the first line \(N\) and \(M\) where
  - the simple graph \(G = (V, E)\) has \(N\) vertices, namely \(V = \{0, 1, 2, \ldots, N-1\}\),
  - and has \(M\) edges, that is \(\left| E \right| = M\).
2. The next \(M\) lines of the file contains pairs of numbers \(U_i, V_i\). One such pair corresponds to a (non directed) edge \((U_i, V_i)\). Every edge is listed only once in the file.
3. To process the input we recommend modifying the code of the appropriate part of the 3rd task. Note that the first line of the file here does not contain the vertices \(S\) and \(T\). Since the edges of the graph are not directed, you may want to add edges to the edge list of both endpoints!
The second input of the program is a sequence of integers. The task of the program is to decide whether the sequence of numbers represents a Hamiltonian cycle in the graph (verify whether the sequence is a witness of the existence of a Hamiltonian cycle).
If it is a Hamiltonian cycle (a witness) print the text
```
Hamiltonian cycle
```
otherwise print
```
Not a Hamiltonian cycle
```

Try the program with the file graf.text and with the next input files:

Filename	Expected output
t1.text	Hamiltonian cycle
t2.text	Not a Hamiltonian cycle
t3.text	Not a Hamiltonian cycle
t4.text	Not a Hamiltonian cycle
t5.text	Hamiltonian cycle
t6.text	Not a Hamiltonian cycle
t7.text	Not a Hamiltonian cycle