Problema del carter chinenc

En teoria de grafos (una branca de la matemàtica), el problema del carter chinenc (PCC), o problema del circuit del carter, o problema de l'inspecció i selecció de rutes, consistix en trobar el camí més curt o circuit tancat, que visite cada aresta d'un grafo (conectat) no direccionar, o siga, que passe a lo manco una volta per cada aresta del grafo, tornant al punt (o nodo) de partida. Quan el grafo posseïx un circuit euleriano (una passejada tancada que alcance tota aresta solament una volta), eixe circuit és una solució òptima.

Problema del carter chinenc

Alan J. Goldman del Institut Nacional d'Estàndarts i Tecnologia (EE. UU.), va usar per primera volta la denominació 'problema del carter chinenc' per a este problema, ya que originalment va ser estudiat pel matemàtic chinenc Mei-Ko Kuan en 1962, qui precisament era carter.

Camins i circuits eulerianos

Per a que un grafo tinga un circuit euleriano, certament tindrà que estar conectat.

Supongam que tenim un grafo conexo G = (V, I); llavors, les següents declaracions són equivalents:

1. Tots els vèrtiços (nodos) de G tenen grau parell.
2. G consistix de les arestes d'una unió disjunta d'alguns cicles, i dels vèrtiços d'eixos cicles.
3. G té un circuit euleriano.

• 1 → 2 pot ser demostrat per indución sobre el número de cicles;
• 2 → 3 també pot ser demostrat per inducció sobre el número de cicles; i
• 3 → 1 és immediata.

Un camí euleriano (un camí que no és tancat, pero que utilisa totes les arestes de G a penes una volta i solament una volta) existix si i solament si G és conectat i té dos vèrtiços de valència impar.

Solució

Si un grafo té un circuit euleriano (o un camí euleriano), llavors un circuit euleriano (o camí) visita cada aresta, i aixina la solució resulta ser qualsevol circuit euleriano (o camí).

I si un grafo no és euleriano, deu contindre vèrtiços de grau impar, i per aplicació del lema de la premuda de mans, deu haver un número par d'eixos vèrtiços. Llavors, per a resoldre el problema del carter chinenc, primer devem trobar el menor enllace-T, i transformem el grafo original en un atre euleriano simplement duplicant l'enllaç-T. Resulta llavors que la solució al problema del carter chinenc en el grafo original, podrà ser obtinguda o generada, sobre la base de la determinació d'un circuit euleriano per al nou grafo.

Vore també

• Problema del viajante
• Cicle euleriano
• Algoritme de Dijkstra