- Katılım
- 7 Eyl 2009
- Konular
- 6,986
- Mesajlar
- 38,038
- Çözüm
- 1
- Online süresi
- 7d 22h
- Reaksiyon Skoru
- 1,833
- Altın Konu
- 0
- Başarım Puanı
- 494
- MmoLira
- 6,600
- DevLira
- 0
HERAKLES Otomatik Avlı kalıcı sunucu. 19 Haziran'da açılıyor. Atius & Wizard güvencesiyle hemen kayıt ol, ön kayıt ödülleri aktif. HEMEN TIKLA!
Çokterimli zamanda indirgeme, bir problemi çokterimli (polinomsal) zamanda başka bir probleme dönüştürme işlemidir. Bu durumda, ikinci problemi çokterimli zamanda çözebilirsek ilk problemi de çokterimli zamanda çözebiliriz.
Örnek
Hamilton Çemberi Problemi, Gezgin Satıcı Problemi'ne aşağıdaki şekilde indirgenebilir.
G(V, E) verilmiş bir çizge olsun. Çözmeye çalıştığımız Hamilton Çemberi Problemi, bu çizge üzerinde bütün uçlardan sadece bir kez geçip en sonunda başladığı uca ulaşan bir yol olup olmadığını sorar. G çizgesini kullanarak kenarları ağırlıklı G^(V^, E^, w) çizgesini şu şekilde elde edebiliriz: V^=V, E'deki her kenar için E^ kümesine ağırlığı 1 olan bir kenar, E'de bulunmayan her kenar içinse ağırlığı sonsuz olan bir kenar ekleriz. Bu durumda, eğer G^ çizgesinde toplam ağırlığı en fazla n=|V| olan ve bütün uçlarda geçen bir yol, ancak ve ancak G çizgesinde bir Hamilton Çemberi varsa bulunabilir. Ağırlıklı G^ çizgesinde bütün uçlardan geçen ve ağırlığı en fazla n olan yol bulma problemi de Gezgin Satıcı Problemi'nin ta kendisidir.
Örnek
Hamilton Çemberi Problemi, Gezgin Satıcı Problemi'ne aşağıdaki şekilde indirgenebilir.
G(V, E) verilmiş bir çizge olsun. Çözmeye çalıştığımız Hamilton Çemberi Problemi, bu çizge üzerinde bütün uçlardan sadece bir kez geçip en sonunda başladığı uca ulaşan bir yol olup olmadığını sorar. G çizgesini kullanarak kenarları ağırlıklı G^(V^, E^, w) çizgesini şu şekilde elde edebiliriz: V^=V, E'deki her kenar için E^ kümesine ağırlığı 1 olan bir kenar, E'de bulunmayan her kenar içinse ağırlığı sonsuz olan bir kenar ekleriz. Bu durumda, eğer G^ çizgesinde toplam ağırlığı en fazla n=|V| olan ve bütün uçlarda geçen bir yol, ancak ve ancak G çizgesinde bir Hamilton Çemberi varsa bulunabilir. Ağırlıklı G^ çizgesinde bütün uçlardan geçen ve ağırlığı en fazla n olan yol bulma problemi de Gezgin Satıcı Problemi'nin ta kendisidir.
