Hamilton yolu problemi

[bullvar_katip]

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 ve u düğümleri ile yer değiştirilir. • G deki s ve t düğümleri, G’ de s ve t düğümleri ile yer değiştirilir. • G’ deki kenarlar 2 şekilde oluşturulur: 1. u, u ve u, sırayla birbiriyle bağlıdır. 2. Eğer G de bir kenar u dan v ye gidiyorsa, G’ de u 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 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 tan t e Hamilton yolu bulunan bir graftır. G grafının P Hamilton yolu bulunan düğümleri : P : s, u, u, ..., u, t G’ grafının P’ Hamilton yolu bulunan düğümleri : P’ : s, u, u, u, u, u, u, ..., t 2. Kısım ispatı: G, s den t ye Hamilton yolu bulunan bir graftır => G’, s tan t e Hamilton yolu bulunan bir graftır. Sol tarafın doğru olduğunu kabul ediyoruz. Yani G’, s 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 başlangıç düğümünden başlayarak iddiamızı ispatlayabiliriz. s tan sonraki düğüm u (herhangi bir i için) olmak zorunda. Tanım gereği sonraki düğümler sırasıyla u ve u olmak zorundadır. Bir sonraki düğüm tanım gereği u (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. Kategori:NP-tam problemleri