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.
Datuak: Q901096
Multimedia: Route inspection problem / Q901096