Hamiltonian path problem

Angol

Főnév

Hamiltonian path problem (tsz. Hamiltonian path problems)

(informatika) A Hamilton-út probléma a gráfelmélet egyik legismertebb és legnehezebb problémái közé tartozik.

🧭 Mi az a Hamilton-út?

Egy Hamilton-út olyan út egy gráfban, amely minden csúcsot pontosan egyszer látogat meg. Ha ez az út kört alkot (azaz ugyanoda tér vissza, ahonnan indult), akkor Hamilton-körről beszélünk.

Formálisan:

Legyen ${\textstyle G=(V,E)}$ egy gráf:

Hamilton-út: egy ${\textstyle v_{1},v_{2},...,v_{n}}$ ${\textstyle v_{1},v_{2},...,v_{n}}$ csúcssorozat, ahol:
- Minden csúcs ${\textstyle V}$ halmazból származik.
- Minden csúcs egyszer szerepel.
- Minden szomszédos csúcspárhoz tartozik él: ${\textstyle (v_{i},v_{i+1})\in E}$
- Az összes csúcsot bejárja pontosan egyszer.

❓ Mi a Hamilton-út probléma?

Bemenet: Egy irányított vagy irányítatlan gráf Kérdés: Létezik-e benne Hamilton-út?

Ez egy döntési probléma: eldöntjük, hogy létezik-e ilyen út. Ha igen, ki is kereshető (bár nagyon sok időbe telhet).

🧠 Összehasonlítás Euler-úttal

Tulajdonság	Hamilton-út	Euler-út
Mit jár be?	Minden csúcsot egyszer	Minden élt egyszer
Bonyolultság	NP-teljes probléma	Megoldható polinomiális időben
Kritérium	Struktúrafüggő	Fokszám-feltételek alapján eldönthető

⏳ Számítási bonyolultság

A Hamilton-út probléma NP-teljes:

Nincs ismert hatékony algoritmus (polinomiális idejű), amely minden gráfra megoldja.
Akkor is nehéz, ha csak eldönteni kell, hogy létezik-e ilyen út.
Még planáris, vagy irányított gráfok esetén is nehéz marad.

Ez azt jelenti, hogy ha valaki találna rá gyors algoritmust, akkor az összes NP-probléma megoldódna (pl. RSA feltörhető lenne).

✅ Könnyebb esetek

Torna gráf (irányított, teljes gráf): mindig van Hamilton-út, hatékonyan megtalálható.
Teljes gráf: mindig van Hamilton-kör is.
Fokszámfeltétel: Ha minden csúcs fokszáma legalább ${\textstyle n/2}$ (Dirac-tétel), akkor van Hamilton-kör.

🔁 Brute Force algoritmus (visszalépéses keresés)

def hamilton_keres(graph, path, visited):
    if len(path) == len(graph):
        return True
    for v in range(len(graph)):
        if graph[path[-1]][v] == 1 and not visited[v]:
            visited[v] = True
            path.append(v)
            if hamilton_keres(graph, path, visited):
                return True
            visited[v] = False
            path.pop()
    return False

def van_hamilton_ut(graph):
    n = len(graph)
    for start in range(n):
        visited = [False] * n
        visited[start] = True
        if hamilton_keres(graph, [start], visited):
            return True
    return False

Ez a módszer nagyon lassú, mivel minden permutációt kipróbál – de kis gráfokhoz jó tanulási célra.

✍️ Példa

Gráf:

Csúcsok: A, B, C, D
Élek: A-B, B-C, C-D, D-A, B-D

Hamilton-út például lehet: A → B → D → C

⚙️ Alkalmazások

Genomszekvenálás
Útvonaltervezés
Kirakós játékok (pl. a lovas lépései a sakktáblán – Knight’s Tour)
Fordítóprogramok optimalizálása

🔁 Hamilton-kör és TSP

Hamilton-kör: körbejárja a csúcsokat pontosan egyszer.
TSP (Travelling Salesman Problem): olyan Hamilton-kört keres, amelynek összsúlya minimális.

📌 Kapcsolódó problémák

Hamilton-kör probléma – szintén NP-teljes
Euler-út probléma – egyszerűbb
TSP – NP-nehéz
Leghosszabb út probléma – NP-nehéz

További információk

Hamiltonian path problem - Szótár.net (en-hu)
Hamiltonian path problem - Sztaki (en-hu)
Hamiltonian path problem - Merriam–Webster
Hamiltonian path problem - Cambridge
Hamiltonian path problem - WordNet
Hamiltonian path problem - Яндекс (en-ru)
Hamiltonian path problem - Google (en-hu)
Hamiltonian path problem - Wikidata
Hamiltonian path problem - Wikipédia (angol)