Kısaca: İspat: Yönsüz graflarda Hamilton yolunun bulunması NP-tamdır (NP-complete) ...devamı ☟
İ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 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 uin, umid ve uout düğümleri ile yer değiştirilir. • G' deki s ve t düğümleri, G’ de sout ve tin düğümleri ile yer değiştirilir. • G’ deki kenarlar 2 şekilde oluşturulur: 1. uin, umid ve uout, sırayla birbiriyle bağlıdır. 2. Eğer G de bir kenar u dan v ye gidiyorsa, G’ de uout ve vin birbiriyle bağlı gösterilir. İspatlanacak Teorem şu şekilde değiştirilir: G, s den t ye Hamilton yolu bulunan bir graftır <=> G’, sout tan tin e Hamilton yolu bulunan bir graftır. 1. Kısım ispatı:G, s den t ye Hamilton yolu bulunan bir graftır <= G’, sout tan tin e Hamilton yolu bulunan bir graftır. G grafının P Hamilton yolu bulunan düğümleri : P : s, u1, u2, ... , uk,tG’ grafının P’ Hamilton yolu bulunan düğümleri : P’ : sout, u1in, u1mid, u1out, u2in, u2mid, u2out, ... , tin2. Kısım ispatı:G, s den t ye Hamilton yolu bulunan bir graftır => G’, sout tan tin e Hamilton yolu bulunan bir graftır. Sol tarafın doğru olduğunu kabul ediyoruz. Yani G’, sout tan tin 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 sout başlangıç düğümünden başlayarak iddiamızı ispatlayabiliriz. sout tan sonraki düğüm uiin (herhangi bir i için) olmak zorunda. Tanım gereği sonraki düğümler sırasıyla uimid ve uiout olmak zorundadır. Bir sonraki düğüm tanım gereği ujin (herhangibir j için)olmak zorundadır. Bu yol tin e ulaşana kadar aynı mantıkla devam edeceği için iddia ispatlanmış olur.
