En teoria de grafs, lalgorisme de Christofides és un algorisme que serveix per resoldre el problema del viatjant de comerç, en el cas en què les distàncies formen un espai mètric (són simètriques i compleixen la desigualtat triangular). Es tracta d'un algorisme d'aproximació que garanteix que les seves solucions es trobaran en un factor màxim de 3/2 respecte a la distància total de la solució òptima. i rep el nom de Nicos Christofides, que el va publicar el 1976.Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976. A data de 2015, és el millor ratio d'aproximació que s'ha demostrat pel problema del viatjant de comerç en espais mètrics generals, tot i que es coneixen millors aproximacions per a alguns casos particulars.
Algorisme Sigui un exemple del problema del viatjant de comerç. Això vol dir que és un graf complet del conjunt de vèrtexs, i la funció assigna un pes real no negatiu a cada aresta de . Segons la desigualtat triangular, per a cada tres vèrtexs , , i , s'ha de complir que .
Llavors l'algorisme es pot escriure en pseudocodi com segueix: Crear un arbre generador mínim de . Sigui el conjunt de vèrtexs amb grau senar a . A través del lema de l'encaixada de mans, té un nombre parell de vèrtexs. Trobar un aparellament perfecte de pes mínim en el subgraf induït a partir dels vèrtexs de . Combinar les arestes de i per formar un multigraf connex en què cada vèrtex té un grau parell. Formar un camí eulerià a . Convertir el circuit trobat en el pas previ en un camí hamiltonià saltant vèrtexs repetits (fent dreceres).
Exemple La següent taula mostra un exemple d'ús de l'algorisme de Christofides:
200px Es parteix d'un graf complet amb arestes les distàncies de les quals compleixen la desigualtat triangular.200px Calcular l'arbre generador mínim 200px Trobar el conjunt de vèrtexs amb valència (nombre d'arestes que surten d'un vèrtex) senar a 200px Es forma el subgraf de usant només els vèrtexs de 200px Es realitza un aparellament perfecte (aquell que aparella els vèrtexs dos a dos) de mínim pes en el subgraf 200px S'uneix l'aparellament amb l'arbre generador per formar un multigraf eulerià200px Es calcula el camí eulerià200px Finalment es treuen els vèrtexs repetits. En unit C amb D en aquest cas, s'assegura una reducció de distància a partir de la desigualtat triangular.
Referències
Enllaços externs NIST Definició de l'algorisme de Christofides
Categoria:Algorismes de grafs