Hamilton yolu problemi

Hamilton yolu problemi, Hamilton yolunun çözümü ile ilgili problemdir.

İspat: Yönsüz graflarda Hamilton yolunun bulunması NP-tamdır (NP-complete)

Hamilton Yolu (Hamiltonian Path):
• Bir graftaki her düğümden (node) tam 1 kere geçilmelidir.
• Bir kere geçilen kenardan (edge) bir daha geçilmemelidir.

İspatta indirgeme (reduction) metodu kullanılacaktır.

Teorem : Yönlü graflarda Hamilton yolunun bulunması NP-tamdır. (İspatlanmış kabul ediliyor.)
Bu teoremdeki yönlü grafı şu şekilde tanımlayabiliriz:
HAMPATH = { <G,s,t> | G, s den t ye bir Hamilton yolu bulunan yönlü bir graftır.}
G grafını, düğümleri s’ ve t’ olan bir yönsüz G’ grafına indirgeyeceğiz.

İspatlanacak Teorem:
G, s den t ye Hamilton yolu bulunan bir graftır <=> G’, s’ den t’ ye Hamilton yolu bulunan bir graftır.
G’ yi şöyle tanımlayabiliriz:
• G deki her u düğümü (s ve t hariç), G’ de uⁱⁿ, u^mid ve u^out düğümleri ile yer değiştirilir.
• G' deki s ve t düğümleri, G’ de s^out ve tⁱⁿ düğümleri ile yer değiştirilir.
• G’ deki kenarlar 2 şekilde oluşturulur:
1. uⁱⁿ, u^mid ve u^out, sırayla birbiriyle bağlıdır.
2. Eğer G de bir kenar u dan v ye gidiyorsa, G’ de u^out ve vⁱⁿ birbiriyle bağlı gösterilir.

İspatlanacak Teorem şu şekilde değiştirilir:
G, s den t ye Hamilton yolu bulunan bir graftır <=> G’, s^out tan tⁱⁿ e Hamilton yolu bulunan bir graftır.

1. Kısım ispatı:
G, s den t ye Hamilton yolu bulunan bir graftır <= G’, s^out tan tⁱⁿ e Hamilton yolu bulunan bir graftır.

G grafının P Hamilton yolu bulunan düğümleri :
P : s, u₁, u₂, ..., u_k, t

G’ grafının P’ Hamilton yolu bulunan düğümleri :
P’ : s^out, u₁ⁱⁿ, u₁^mid, u₁^out, u₂ⁱⁿ, u₂^mid, u₂^out, ..., tⁱⁿ

2. Kısım ispatı:
G, s den t ye Hamilton yolu bulunan bir graftır => G’, s^out tan tⁱⁿ e Hamilton yolu bulunan bir graftır.
Sol tarafın doğru olduğunu kabul ediyoruz. Yani G’, s^out tan tⁱⁿ e üçlü düğümlerden üçlü düğümlere giden bir P’ Hamilton yolu bulunan bir graf olduğunu iddia ediyoruz. Yukarıda tanımladığımız gibi s^out başlangıç düğümünden başlayarak iddiamızı ispatlayabiliriz. s^out tan sonraki düğüm u_iⁱⁿ (herhangi bir i için) olmak zorunda. Tanım gereği sonraki düğümler sırasıyla u_i^mid ve u_i^out olmak zorundadır. Bir sonraki düğüm tanım gereği u_jⁱⁿ (herhangi bir j için)olmak zorundadır. Bu yol tⁱⁿ e ulaşana kadar aynı mantıkla devam edeceği için iddia ispatlanmış olur.