miniatura|Un exemple pràctic d'un problema de carter xinès no dirigit: En teoria de grafs i optimització combinatòria, el problema de la ruta de Guan, el problema del carter xinès, el recorregut del carter o el problema d'inspecció de rutes consisteix en trobar el camí o circuit tancat més curt que visiti cada aresta d'un graf no dirigit (connectat) almenys una vegada. Quan el graf té un circuit eulerià (un circuit tancat que cobreix cada aresta una vegada), aquest circuit és una solució òptima. En cas contrari, el problema d'optimització consisteix en trobar el nombre més petit d'arestes del graf per duplicar (o el subconjunt d'arestes amb el pes total mínim possible) de manera que el multigraf resultant tingui un circuit eulerià. Es pot resoldre en temps polinòmic, a diferència del problema del viatger, que és NP-difícil . És diferent del problema del viatger degut a què el viatger no pot repetir els nodes visitats i no ha de visitar cada aresta.

El problema va ser estudiat originalment pel matemàtic xinès Meigu Guan el 1960, el treball del qual en xinès va ser traduït a l'anglès el 1962.. Translated in Chinese Mathematics 1: 273–277, 1962. El nom original "problema del carter xinès" va ser posat en honor seu; diferents fonts atribueixen el bateig a Alan J. Goldman o Jack Edmonds, tots dos treballant a l'Oficina Nacional d'Estàndards dels Estats Units en aquell moment..

Solució no dirigida i unions en T El problema d'inspecció de rutes no dirigides es pot resoldre en temps polinòmic mitjançant un algoritme basat en el concepte de unió T. Sigui T un conjunt de vèrtexs en un graf. Un conjunt d'arestes J s'anomena unió T si la col·lecció de vèrtexs que tenen un nombre senar d'arestes incidents a J és exactament el conjunt T. Una unió T existeix sempre que cada component connectat del graf conté un nombre parell de vèrtexs a T. El problema de la unió T és trobar una unió T amb el nombre mínim possible d'arestes o el pes total mínim possible.

Per a qualsevol T, una unió T més petita (quan existeix) consisteix necessàriament en camins que uneixen els vèrtexs de T per parelles. Els camins seran tals que la longitud total o el pes total de tots ells sigui el més petit possible. En una solució òptima, cap d'aquests camins compartirà cap aresta, però poden tenir vèrtexs compartits. Es pot obtenir una unió T mínima construint un gràfic complet sobre els vèrtexs de T, amb arestes que representen els camins més curts del gràfic d'entrada donat, i després trobant una coincidència perfecta de pes mínim en aquest gràfic complet. Les arestes d'aquesta coincidència representen camins del gràfic original, la unió del qual forma la unió T desitjada. Tant la construcció del gràfic complet com la cerca d'una coincidència en aquest es poden fer en O( n3) passos computacionals.

Per resoldre el problema d'inspecció de rutes, cal seleccionar el conjunt T format per tots els vèrtexs del graf que tenen grau senar. D'acord amb les condicions del problema, el graf és connectat (en cas contrari, no seria possible cap recorregut), i segons el lema de la connexió, el nombre de vèrtexs senars és sempre parell. Això garanteix l'existència d'una unió T.

Si dupliquem les arestes que formen aquesta unió T, el graf es transforma en un multigraf eulerià, és a dir, un graf connectat on tots els vèrtexs tenen grau parell. Aquest tipus de graf admet un recorregut d'Euler, que recorre cada aresta exactament una vegada. Aquest recorregut constitueix una solució òptima per al problema d'inspecció de rutes.

Solució dirigida En un graf dirigit, s'apliquen les mateixes idees generals, però s'han d'utilitzar tècniques diferents. Si el graf dirigit és eulerià, només cal trobar un cicle d'Euler. Si no ho és, cal trobar unions T, que en aquest cas implica trobar camins des dels vèrtexs amb un grau d'entrada més gran que el seu grau exterior fins a aquells amb un grau exterior més gran que el seu grau d'entrada de manera que facin que el grau d'entrada de cada vèrtex sigui igual al seu grau exterior. Això es pot resoldre com un exemple del problema de flux de cost mínim en què hi ha una unitat d'oferta per cada unitat d'excés de grau d'entrada i una unitat de demanda per cada unitat d'excés de grau exterior. Com a tal, és resoluble en temps O(| V | 2 | E |). Existeix una solució si i només si el graf donat està fortament connectat .

Aplicacions Diversos problemes combinatoris s'han reduït al problema del carter xinès, com ara trobar un tall màxim en un graf planar i un circuit de longitud mitjana mínima en un graf no dirigit.

Variants S'han estudiat algunes variants del problema del carter xinès i s'ha demostrat que són NP-completes .

El problema del carter ventós és una variant del problema d'inspecció de rutes en què l'entrada és un graf no dirigit, però on cada aresta pot tenir un cost diferent per recórrer-lo en una direcció que per recórrer-lo en l'altra direcció. A diferència de les solucions per a grafs dirigits i no dirigits, és NP-complet .. El problema mixt del carter xinès : per a aquest problema, algunes de les arestes poden estar dirigides i, per tant, només es poden visitar des d'una direcció. Quan el problema requereix un recorregut mínim d'un dígraf (o multidígraf), es coneix com el "problema de l'escombrador de carrers de Nova York". El problema del carter xinès k : trobar k cicles que comencin tots en una ubicació designada de manera que cada aresta sigui recorreguda per almenys un cicle. L'objectiu és minimitzar el cost del cicle més car. El "problema del carter rural": resoldre el problema amb algunes arestes no necessàries.

Referències

Categoria:Teoria de grafs