5. Hatékony tanúsítvány

Határidő: 2022-03-22 24:00

Az algoritmuselmélet tárgyban fognak vele találkozni/találkoztak vele, de a Turing gépek jegyzetben is szerepel, hogy a Hamilton-körrel rendelkező gráfok nyelvére \(\textrm{HAM} \in \textrm{NP}\) teljesül. A bizonyítást a tanú-tétel segítségével végezhetjük el úgy, hogy egy – a Hamilton-kör létezését mutató – hatékony tanúsítványt megadunk. Ennek alapötlete, hogy egy adott gráfhoz megadunk egy számsorozatot, ami a feltételezett Hamilton-kör csúcsait jelöli egy körnek megfelelő sorrendben. Ha a számsorozatban minden csúcs pontosan egyszer fordul elő, valamint a számsorozatban egymásutáni csúcsok, illetve az első és az utolsó csúcs szomszédosak a gráfban, akkor a tanúsítvány bizonyítja a Hamilton-kör létezését.
A feladat egy olyan Python program írása, mely a fenti (és a jegyzetben is vázolt) hatékony tanúsítvány algoritmusát valósítja meg: eldönti egy adott (gráf, számsorozat) párról, hogy az adott számsorozat egy Hamilton-kört reprezentál-e a gráfban.
A program a bemenetet parancssori argumentumok formájában kapja meg a következő módon:
```
python3 5KovacsJutka.py graf.text tanu.text
```
Az első bemenet (a példában graf.text) egy irányítatlan egyszerű gráf, amit a következő módon adunk meg egy szöveges (.text) fájlban:
1. A fájl első sorában az \(N\), \(M\) természetes számok találhatóak szóközökkel elválasztva, ahol
  - a \(G = (V, E)\) egyszerű gráf csúcsainak halmaza \(V = \{0, 1, 2, \ldots, N-1\}\),
  - az élek száma \(\left| E \right| = M\).
2. A fájl további \(M\) sora rendre \(U_i\), \(V_i\) számpárokat tartalmaz. Egy ilyen számpár megfelel egy \(\{U_i, V_i\} \in E\) irányítatlan élnek. Egy él csak egyszer szerepel a fájlban.
3. A bemenet feldolgozására javasoljuk a 3. feladat gráf beolvasó függvényének módosítását. Figyeljünk arra, hogy most a fájl első sorában nem szerepelnek az \(S\) és \(T\) csúcsok. Mivel a gráf élei nincsenek irányítva, érdemes lehet az éleket mindkét végpontjuk éllistájába felvenni.
A program második bemenete egy egész számokból álló számsor. A program feladata eldönteni, hogy a számsor tanú-e arra, hogy a gráfban található Hamilton-kör.
Amennyiben a tanú megfelelő, a
```
Tanú
```
amennyiben nem, akkor a
```
Nem tanú
```
szöveget írjuk ki.

Próbáljuk ki a programot a graf.text gráffal és az alábbi (tanújelölt) bemenetekkel:

Fájlnév	Elvárt kimenet
t1.text	Tanú
t2.text	Nem tanú
t3.text	Nem tanú
t4.text	Nem tanú
t5.text	Tanú
t6.text	Nem tanú
t7.text	Nem tanú