Azərbaycanca
Deutsch
日本語
Lietuvos
සිංහල
Türkçe
Українська
United State
Bu madde, uygun değildir. (Ocak 2010) |
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 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, t
G’ grafının P’ Hamilton yolu bulunan düğümleri :
P’ : sout, u1in, u1mid, u1out, u2in, u2mid, u2out, ..., tin
2. 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 (herhangi bir j için)olmak zorundadır. Bu yol tin e ulaşana kadar aynı mantıkla devam edeceği için iddia ispatlanmış olur.
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Bu madde Vikipedi bicem el kitabina uygun degildir Maddeyi Vikipedi standartlarina uygun bicimde duzenleyerek Vikipedi ye katkida bulunabilirsiniz Gerekli duzenleme yapilmadan bu sablon kaldirilmamalidir Ocak 2010 Hamilton yolu problemi Hamilton yolunun cozumu ile ilgili problemdir Ispat Yonsuz graflarda Hamilton yolunun bulunmasi NP tamdir NP complete Hamilton Yolu Hamiltonian Path Bir graftaki her dugumden node tam 1 kere gecilmelidir Bir kere gecilen kenardan edge bir daha gecilmemelidir Ispatta indirgeme reduction metodu kullanilacaktir Teorem Yonlu graflarda Hamilton yolunun bulunmasi NP tamdir Ispatlanmis kabul ediliyor Bu teoremdeki yonlu grafi su sekilde tanimlayabiliriz HAMPATH lt G s t gt G s den t ye bir Hamilton yolu bulunan yonlu bir graftir G grafini dugumleri s ve t olan bir yonsuz G grafina indirgeyecegiz Ispatlanacak Teorem G s den t ye Hamilton yolu bulunan bir graftir lt gt G s den t ye Hamilton yolu bulunan bir graftir G yi soyle tanimlayabiliriz G deki her u dugumu s ve t haric G de uin umid ve uout dugumleri ile yer degistirilir G deki s ve t dugumleri G de sout ve tin dugumleri ile yer degistirilir G deki kenarlar 2 sekilde olusturulur 1 uin umid ve uout sirayla birbiriyle baglidir 2 Eger G de bir kenar u dan v ye gidiyorsa G de uout ve vin birbiriyle bagli gosterilir Ispatlanacak Teorem su sekilde degistirilir G s den t ye Hamilton yolu bulunan bir graftir lt gt G sout tan tin e Hamilton yolu bulunan bir graftir 1 Kisim ispati G s den t ye Hamilton yolu bulunan bir graftir lt G sout tan tin e Hamilton yolu bulunan bir graftir G grafinin P Hamilton yolu bulunan dugumleri P s u1 u2 uk t G grafinin P Hamilton yolu bulunan dugumleri P sout u1in u1mid u1out u2in u2mid u2out tin 2 Kisim ispati G s den t ye Hamilton yolu bulunan bir graftir gt G sout tan tin e Hamilton yolu bulunan bir graftir Sol tarafin dogru oldugunu kabul ediyoruz Yani G sout tan tin e uclu dugumlerden uclu dugumlere giden bir P Hamilton yolu bulunan bir graf oldugunu iddia ediyoruz Yukarida tanimladigimiz gibi sout baslangic dugumunden baslayarak iddiamizi ispatlayabiliriz sout tan sonraki dugum uiin herhangi bir i icin olmak zorunda Tanim geregi sonraki dugumler sirasiyla uimid ve uiout olmak zorundadir Bir sonraki dugum tanim geregi ujin herhangi bir j icin olmak zorundadir Bu yol tin e ulasana kadar ayni mantikla devam edecegi icin iddia ispatlanmis olur