Circuitos eulerianos óptimos en grafos no dirígidosel problema del cartero rural

Laburpena

EL PROBLEMA DEL CARTERO RURAL (RPP) ES UN CASO GENERAL DEL PROBLEMA DEL CARTERO CHINO DONDE SE REQUIERE QUE UN SUBCONJUNTO DEL CONJUNTO DE ARISTAS DE UN GRAFO NO DIRIGIDO DADO SEA ATRAVESADO CON EL MINIMO COSTE, SI ESTE SUBCONJUNTO NO FORMA UN GRAFO CONEXO SINO UN CIERTO NUMERO DE COMPONENETES DESCONECTADOS ENTRE SI EL PROBLEMA ES NP-COMPLETO Y ES TAMBIEN UNA GENERALIZACION DEL PROBLEMA DEL AGENTE VIAJERO (TSP). EN LA MEMORIA PRESENTAMOS EL ESTUDIO DE ESTE PROBLEMA Y PRESENTAMOS UN ALGORITMO DE BRANCH AND BROUND PARA LA SOLUCION EXACTA DEL RPP BASADO EN COTAS CALCULADAS A PARTIR DE LA RELAJACION LAGRANGIANA Y EN LA SATURACION DE ALGUNOS DE LOS NUDOS DEL ARBOL MEDIANTE LA RESOLUCION DE PROBLEMAS DE 1-MATCHING DE COSTE MINIMO. SE PROPORCIONAN RESULTADOS COMPUTACIONALES PARA GRAFOS DE HASTA 84 VERTICES 180 ARISTAS 74 ARISTAS REQUERIDAS.