Ö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.
