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.

Grafoak maila bakoitiko 2 puntu ditu: A eta D. Beraz, ertz guztiak distantzia txikienez zeharkatzeko zirkuituan AD ertzetik 2 aldiz igaro beharko da, maila guztiak bikoitiak eta ondorioz zirkuitu eulertarra izan dadin. Distantzia txikieneko ibilbidea beraz, ADCBAEDA 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