Ir al contenido

Documat


Circuitos eulerianos óptimos en grafos dirígidos: el problema del cartero rural dirígido

  • Autores: Enrique Mota Vidal Árbol académico
  • Directores de la Tesis: Marco A. López Cerdá (dir. tes.) Árbol académico
  • Lectura: En la Universitat de València ( España ) en 1982
  • Idioma: español
  • Tribunal Calificador de la Tesis: Marco A. López Cerdá (presid.) Árbol académico, Miguel Sánchez García (secret.) Árbol académico, Segundo Gutiérrez Cabria (voc.) Árbol académico, Rafael Romero Villafranca (voc.) Árbol académico, Pedro Albertos Pérez (voc.) Árbol académico
  • Texto completo no disponible (Saber más ...)
  • Resumen
    • EL PROBLEMA DEL CARTERO RURAL DIRIGIDO (DRPP) ES UN CASO GENERAL DEL PROBLEMA DEL CARTERO CHINO DONDE SE REQUIERE QUE UN SUBCONJUNTO DEL CONJUNTO DE ARCOS DEL GRAFO DIRIGIDO DADO SEA ATRAVESADO CON COSTE TOTAL MINIMO, SI ESTE SUBCONJUNTO NO INDUCE UN GRAFO DEBILMENTE CONEXO SIMO UN CIERTO NUMERO DE COMPONENTES DISCONEAS EL PROBLEMA ES NP-COMPLETO Y UNA GENERALIZACION DEL PROBLEMA DEL AGENTE VIAJERO ASIMETRICO. SE PRESENTA UN ALGORITMO DE BRONCH AND BOIND PARA LA SOLUCION EXACTA DEL DRPP BASADO EN COTAS CALCULADAS A PARTIR DE LA RELAJACION LAGRANGIANA (CON SUBPROBLEMAS DE ARBORESCENCIAS GENERADORAS DE MINIMO PESO) Y EN LA SATURACION DE ALGUNOS DE LOS NUDOS DEL ARBOL MEDIANTE LA RESOLUCION DE PROBLEMAS DE FLUJO DE COSTE MINIMO. LOS RESULTADOS COMPUTACIONALES SE PRESENTAN PARA GRADOS DE HASTA 80 VERTICES 179 ARCOS Y 71 ARCOS REQUERIDOS.


Fundación Dialnet

Mi Documat

Opciones de tesis

Opciones de compartir

Opciones de entorno