Postari txinatarraren ebazkizun

Grafo-teorian, postari txinatarraren ebazkizuna edo bide ikuskapen ebazkizuna noranzkorik gabeko grafo haztatu batean ertz edo lokarri guztiak zeharkatzen dituen ibilbide itxi edo zirkuitu laburrena bilatzeko ebazkizuna da.

 Ebazpena 

Grafoak Euler-en zirkuitua duenean, zirkuitu hori bera izango da soluzio hobezina.

Grafoak maila bakoitiko erpinak baditu, erpin hauek bisitatu edo lotu behar dira, binaka, beraien artean distantzia txikienez, guztira zeharkatutako distantzia txikiena izan dadin.

Zuhaitz erako grafo batean, soluzio hobezinerako ertz bakoitza bi aldiz zeharkatu behar da.

 Ikus, gainera 

 Saltzaile ibiltariaren ebazkizun

 Kanpo estekak 
 Bide ikuskatzearen problema, Gizapedian.

Kategoria:Grafo teoria