Colorear caminos

Concepto en la teoría de grafos

En teoría de grafos , la coloración de rutas generalmente se refiere a uno de dos problemas:

• El problema de colorear un (multi)conjunto de caminos en el grafo , de tal manera que dos caminos cualesquiera de los cuales comparten una arista en reciban colores diferentes. El conjunto y el grafo se proporcionan en la entrada. Esta formulación es equivalente a colorear los vértices del grafo de conflicto del conjunto , es decir, un grafo con un conjunto de vértices y aristas que conectan todos los pares de caminos de los cuales no son disjuntos en aristas con respecto a . ${\displaystyle R}$ ${\displaystyle G}$ ${\displaystyle R}$ ${\displaystyle G}$ ${\displaystyle R}$ ${\displaystyle G}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle G}$
• El problema de colorear (de acuerdo con la definición anterior) cualquier conjunto (multi) de rutas elegido en , de modo que el conjunto de pares de vértices finales de las rutas desde sea igual a algún conjunto o multiconjunto , llamado conjunto de solicitudes . El conjunto y el gráfico se proporcionan en la entrada. Este problema es un caso especial de una clase más general de problemas de enrutamiento de gráficos, conocida como programación de llamadas. ${\displaystyle R}$ ${\displaystyle G}$ ${\displaystyle R}$ ${\displaystyle I}$ ${\displaystyle I}$ ${\displaystyle G}$

En ambos problemas, el objetivo suele ser minimizar la cantidad de colores utilizados en la coloración. En diferentes variantes de coloración de rutas, puede tratarse de un gráfico simple , un dígrafo o un multigrafo . ${\displaystyle G}$

Referencias

• La complejidad de la coloración de rutas y la programación de llamadas por Thomas Erlebach y Klaus Jansen
• Un compendio de problemas de optimización NP de Viggo Kann (problema: Coloración de ruta mínima)