Az algoritmuselmélet tárgyban fognak vele találkozni/találkoztak
vele, 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 hamilton.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:
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\).
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.
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: