En la teoría de gráficos , un color de borde de un gráfico es una asignación de "colores" a los bordes del gráfico para que no haya dos bordes incidentes que tengan el mismo color. Por ejemplo, la figura de la derecha muestra una coloración de borde de un gráfico con los colores rojo, azul y verde. Los colores de los bordes son uno de varios tipos diferentes de colores de gráficos . El problema de la coloración de bordes pregunta si es posible colorear los bordes de un gráfico dado usando como máximo k colores diferentes, para un valor dado de k , o con la menor cantidad de colores posibles. El número mínimo requerido de colores para los bordes de un gráfico dado se llama índice cromáticode la gráfica. Por ejemplo, los bordes del gráfico en la ilustración se pueden colorear con tres colores, pero no se pueden colorear con dos colores, por lo que el gráfico que se muestra tiene un índice cromático tres.
Según el teorema de Vizing , el número de colores necesarios para colorear el color de un gráfico simple es su grado máximo Δ o Δ + 1 . Para algunos gráficos, como los gráficos bipartitos y los gráficos planos de alto grado , el número de colores siempre es Δ , y para los multigrafos , el número de colores puede ser tan grande como 3Δ / 2 . Existen algoritmos de tiempo polinomiales que construyen coloraciones óptimas de gráficos bipartitos, y coloraciones de gráficos simples no bipartitos que usan como máximo colores Δ + 1 ; sin embargo, el problema general de encontrar una coloración óptima del borde es NP-duroy los algoritmos más rápidos que se conocen requieren tiempo exponencial. Se han estudiado muchas variaciones del problema de coloración de bordes, en el que una asignación de colores a bordes debe satisfacer otras condiciones que no sean de adyacencia. Los colorantes de borde tienen aplicaciones en problemas de programación y en asignación de frecuencia para redes de fibra óptica .
Ejemplos [ editar ]
Un gráfico de ciclo puede tener sus bordes coloreados con dos colores si la duración del ciclo es uniforme: simplemente alterne los dos colores alrededor del ciclo. Sin embargo, si la longitud es impar, se necesitan tres colores. [1]
Un gráfico completo K n con n vértices se puede colorear con n - 1 colores cuando n es un número par; Este es un caso especial del teorema de Baranyai . Soifer (2008) proporciona la siguiente construcción geométrica de una coloración en este caso: coloque n puntos en los vértices y el centro de un polígono regular ( n - 1) de lados. Para cada clase de color, incluya un borde desde el centro a uno de los vértices poligonales, y todos los bordes perpendiculares que conectan pares de vértices poligonales. Sin embargo, cuando n es impar, nse necesitan colores: cada color solo se puede usar para ( n - 1) / 2 aristas, una fracción de 1 / n del total. [2]
Varios autores han estudiado los colores de los bordes de los gráficos impares , n- gráficos regulares en los que los vértices representan equipos de n - 1 jugadores seleccionados de un grupo de 2 n - 1 jugadores, y en los bordes representan posibles emparejamientos de estos equipos (con un jugador se fue como "hombre extraño" para arbitrar el juego). El caso de que n = 3 da el conocido gráfico de Petersen . Como Biggs (1972) explica el problema (para n = 6), los jugadores desean encontrar un cronograma para estos emparejamientos de manera que cada equipo juegue cada uno de sus seis juegos en diferentes días de la semana, con domingos libres para todos los equipos; es decir, formalizando el problema matemáticamente, desean encontrar una coloración de 6 bordes del gráfico impar de 6 O 6 . Cuando n es 3, 4 u 8, una coloración del borde de O n requiere n + 1 colores, pero cuando es 5, 6 o 7, solo se necesitan n colores. [3]
Definiciones [ editar ]
Al igual que con su contraparte de vértice , una coloración de borde de un gráfico, cuando se menciona sin ninguna calificación, siempre se supone que es una coloración adecuada de los bordes, lo que significa que no se asignan dos bordes adyacentes del mismo color. Aquí, dos bordes distintos se consideran adyacentes cuando comparten un vértice común. Un borde coloración de un gráfico de G también puede ser pensado como equivalente a un vértice coloración de la gráfica de línea L ( G ) , el gráfico que tiene un vértice para cada borde de G y un borde para cada par de bordes adyacentes en G .
Un borde adecuado para colorear con k colores diferentes se llama un (correcto) k -Edge-colorante. Se dice que un gráfico al que se le puede asignar una coloración k -edge (adecuada) es k -edge-colorable. El número más pequeño de colores necesarios en una coloración de borde (adecuada) de un gráfico G es el índice cromático , o número cromático de borde, χ ′ ( G ) . El índice cromático también se escribe a veces usando la notación χ 1 ( G ) ; en esta notación, el subíndice uno indica que los bordes son objetos unidimensionales. Un gráfico es k -edge-chromatic si su índice cromático es exactamentek . El índice cromático no se debe confundir con el cromática número χ ( G ) o χ 0 ( G ) , el número mínimo de colores necesarios en un vértice adecuada coloración de G .
A menos que se indique lo contrario, se supone que todos los gráficos son simples, en contraste con los gráficos múltiples en los que dos o más bordes pueden estar conectando el mismo par de puntos finales y en los que puede haber bucles automáticos. Para muchos problemas en el coloreado de bordes, los gráficos simples se comportan de manera diferente a los multigrafos, y se necesita cuidado adicional para extender los teoremas sobre los colores de los bordes de los gráficos simples al caso multigrafo.
Relación con la coincidencia [ editar ]
Una coincidencia en un gráfico G es un conjunto de aristas, de las cuales no hay dos adyacentes; una coincidencia perfecta es una coincidencia que incluye bordes que tocan todos los vértices del gráfico, y una coincidencia máxima es una coincidencia que incluye tantos bordes como sea posible. En una coloración de bordes, el conjunto de bordes con cualquier color debe ser no adyacente entre sí, por lo que forman una coincidencia. Es decir, un color de borde adecuado es lo mismo que una partición del gráfico en emparejamientos disjuntos.
Si el tamaño de una coincidencia máxima en un gráfico dado es pequeño, entonces se necesitarán muchas coincidencias para cubrir todos los bordes del gráfico. Expresado más formalmente, este razonamiento implica que si un gráfico tiene m bordes en total, y si a lo sumo los bordes β pueden pertenecer a una coincidencia máxima, entonces cada color de borde del gráfico debe usar al menos m / β colores diferentes. [4] Por ejemplo, el gráfico plano de 16 vértices que se muestra en la ilustración tiene m = 24bordes En este gráfico, no puede haber una coincidencia perfecta; porque, si el vértice central coincide, los vértices no coincidentes restantes se pueden agrupar en tres componentes conectados diferentes con cuatro, cinco y cinco vértices, y los componentes con un número impar de vértices no pueden coincidir perfectamente. Sin embargo, el gráfico tiene coincidencias máximas con siete aristas, por lo que β = 7 . Por lo tanto, la cantidad de colores necesarios para colorear el borde del gráfico es al menos 24/7, y dado que la cantidad de colores debe ser un número entero, es al menos cuatro.
Para un gráfico regular de grado k que no tiene una coincidencia perfecta, este límite inferior se puede usar para mostrar que se necesitan al menos k + 1 colores. [4] En particular, esto es cierto para un gráfico regular con un número impar de vértices (como los gráficos completos impares); para tales gráficos, por el lema del apretón de manos , k debe ser par. Sin embargo, la desigualdad χ ′ ≥ m / β no explica completamente el índice cromático de cada gráfico regular, porque hay gráficos regulares que tienen emparejamientos perfectos pero que no son k -edge-colorable. Por ejemplo, el gráfico de Petersenes regular, con m = 15 y con β = 5 aristas en sus combinaciones perfectas, pero no tiene una coloración de 3 aristas.
Relación con el grado [ editar ]
Teorema de Vizing [ editar ]
El número cromática borde de una gráfica G está muy estrechamente relacionado con el grado máximo Δ ( G ) , el mayor número de aristas incidentes a cualquier solo vértice de G . Claramente, χ ′ ( G ) ≥ Δ ( G ) , ya que si Δ diferentes bordes se encuentran en el mismo vértice v , entonces a todos estos bordes se les debe asignar diferentes colores entre sí, y eso solo puede ser posible si hay al menos Δ colores disponibles para ser asignados. Teorema de Vizing (llamado así por Vadim G. Vizingquien lo publicó en 1964) afirma que este límite es casi estricto: para cualquier gráfico, el número cromático de borde es Δ ( G ) o Δ ( G ) + 1 . Cuando χ ′ ( G ) = Δ ( G ) , se dice que G es de clase 1; de lo contrario, se dice que es de clase 2.
Cada gráfico bipartito es de clase 1, [5] y casi todos los gráficos aleatorios son de clase 1. [6] Sin embargo, es NP completo para determinar si un gráfico arbitrario es de clase 1. [7]
Vizing (1965) demostró que las gráficas planas de grado máximo de al menos ocho son de clase uno y conjeturó que lo mismo es cierto para las gráficas planas de grado máximo de siete o seis. Por otro lado, existen gráficos planos de grado máximo que van de dos a cinco que son de clase dos. Desde entonces, la conjetura ha sido probada para gráficos de grado máximo siete. [8] Los gráficos cúbicos planos sin puente son todos de clase 1; Esta es una forma equivalente del teorema de los cuatro colores . [9]
Gráficos regulares [ editar ]
A 1-factorización de un k - grafo regular , una partición de los bordes de la gráfica en matchings perfectos , es el mismo que un k -Edge de coloración de la gráfica. Es decir, un gráfico regular tiene una factorización 1 si y solo si es de la clase 1. Como un caso especial de esto, un color de 3 bordes de un gráfico cúbico (3-regular) a veces se llama un color Tait .
No todos los gráficos regulares tienen una factorización de 1; por ejemplo, el gráfico de Petersen no. En términos más generales, los snarks se definen como los gráficos que, como el gráfico de Petersen, no tienen puente, 3-regulares y de clase 2.
Según el teorema de Kőnig (1916) , cada gráfica regular bipartita tiene una factorización de 1. El teorema se estableció anteriormente en términos de configuraciones proyectivas y fue probado por Ernst Steinitz .
Multigraphs [ editar ]
Para los multigrafos , en los que múltiples bordes paralelos pueden conectar los mismos dos vértices, se conocen resultados similares pero más débiles que el teorema de Vizing que relacionan el número cromático del borde χ ′ ( G ) , el grado máximo Δ ( G ) y la multiplicidad μ ( G ) , el número máximo de bordes en cualquier paquete de bordes paralelos. Como un ejemplo simple que muestra que el teorema de Vizing no se generaliza a los multigrafos, considere un multigrafo de Shannon , un multigrafo con tres vértices y tres haces de bordes paralelos μ ( G ) que conectan cada uno de los tres pares de vértices. En este ejemplo, Δ (G ) = 2μ ( G ) (cada vértice incide solo en dos de los tres haces debordes paralelos μ ( G ) ) pero el número cromático del borde es 3μ ( G ) (hay 3μ ( G ) en total, y cada dos aristas son adyacentes, por lo que a todas las aristas se les deben asignar diferentes colores entre sí). En un resultado que inspiró a Vizing, [10] Shannon (1949) demostró que este es el peor de los casos: χ ′ ( G ) ≤ (3/2) Δ ( G ) para cualquier G multigráfica. Además, para cualquier multigrafo G , χ ′ ( G) ≤ Δ ( G ) + μ ( G ) , una desigualdad que se reduce al teorema de Vizing en el caso de gráficos simples (para los cuales μ ( G ) = 1 ).
Algoritmos [ editar ]
Debido a que el problema de probar si un gráfico es de clase 1 es NP-completo , no existe un algoritmo de tiempo polinómico conocido para colorear los bordes de cada gráfico con un número óptimo de colores. Sin embargo, se han desarrollado varios algoritmos que relajan uno o más de estos criterios: solo funcionan en un subconjunto de gráficos, o no siempre usan una cantidad óptima de colores, o no siempre se ejecutan en tiempo polinómico.
Colorear óptimamente clases especiales de gráficos [ editar ]
En el caso de gráficos bipartitos o multigrafos con un grado máximo Δ , el número óptimo de colores es exactamente Δ . Cole, Ost y Schirra (2001) demostraron que se puede encontrar una coloración de borde óptima de estos gráficos en el límite de tiempo casi lineal O ( m log Δ) , donde m es el número de bordes en el gráfico; Cole & Hopcroft (1982) y Alon (2003) describen algoritmos más simples, pero algo más lentos . El algoritmo de Alon (2003)comienza haciendo que el gráfico de entrada sea regular, sin aumentar su grado o aumentar significativamente su tamaño, fusionando pares de vértices que pertenecen al mismo lado de la bipartición y luego agregando un pequeño número de vértices y bordes adicionales. Luego, si el grado es impar, Alon encuentra una coincidencia perfecta en un tiempo casi lineal, le asigna un color y lo elimina del gráfico, lo que hace que el grado se iguale. Finalmente, Alon aplica una observación de Gabow (1976) , que al seleccionar subconjuntos alternos de bordes en un recorrido de Euler por el gráfico lo divide en dos subgráficos regulares, para dividir el problema de coloreado de bordes en dos subproblemas más pequeños, y su algoritmo resuelve los dos subproblemas de forma recursiva . El tiempo total para su algoritmo es O (m log m ) .
Para gráficos planos con un grado máximo Δ ≥ 7 , el número óptimo de colores es nuevamente exactamente Δ . Con la suposición más fuerte de que Δ ≥ 9 , es posible encontrar una coloración de borde óptima en tiempo lineal ( Cole y Kowalik 2008 ).
Para los gráficos d-regulares que son pseudoaleatorios en el sentido de que su matriz de adyacencia tiene el segundo valor propio más grande (en valor absoluto) como máximo d 1-ε , d es el número óptimo de colores ( Ferber & Jain 2018 ).
Algoritmos que usan más que el número óptimo de colores [ editar ]
Misra y Gries (1992) y Gabow et al. (1985) describen algoritmos de tiempo polinomiales para colorear cualquier gráfico con Δ + 1 colores, cumpliendo el límite dado por el teorema de Vizing; vea el algoritmo de coloración de bordes de Misra & Gries .
Para los multigrafos, Karloff y Shmoys (1987) presentan el siguiente algoritmo, que atribuyen a Eli Upfal . Haga la entrada multigráfica G Eulerian agregando un nuevo vértice conectado por un borde a cada vértice de grados impares, encuentre un recorrido de Euler y elija una orientación para el recorrido. Forme un gráfico bipartito H en el que haya dos copias de cada vértice de G , una a cada lado de la bipartición, con un borde desde un vértice u en el lado izquierdo de la bipartición hasta un vértice v en el lado derecho de la bipartición siempre que el recorrido orientado tenga una ventaja de u a v en G. Aplicar un algoritmo del colorante de borde gráfico bipartito a H . Cada clase de color en H corresponde a un conjunto de bordes en G que forman una subgrafía con un grado máximo de dos; es decir, una unión de la desunión de las trayectorias y de los ciclos, por lo que para cada clase de color en H es posible formar tres clases de color en G . El tiempo para el algoritmo está limitado por el tiempo para colorear el borde de un gráfico bipartito, O ( m log Δ) utilizando el algoritmo de Cole, Ost y Schirra (2001) . La cantidad de colores que usa este algoritmo es como máximo, cerca pero no exactamente igual al límite de Shannon . También se puede convertir en un algoritmo paralelo.de manera directa. En el mismo artículo, Karloff y Shmoys también presentan un algoritmo de tiempo lineal para colorear multigrafos de grado máximo tres con cuatro colores (que coinciden con los límites de Shannon y Vizing) que funciona con principios similares: su algoritmo agrega un nuevo vértice para hacer el gráfico Euleriano, encuentra un recorrido de Euler y luego elige conjuntos alternos de bordes en el recorrido para dividir el gráfico en dos subgráficos de grado máximo dos. Las rutas e incluso los ciclos de cada subgrafo pueden colorearse con dos colores por subgrafo. Después de este paso, cada ciclo impar restante contiene al menos un borde que puede colorearse con uno de los dos colores que pertenecen al subgrafo opuesto. La eliminación de este borde del ciclo impar deja un camino, que puede colorearse usando los dos colores para su subgrafo.
Un algoritmo de coloración codicioso que considera los bordes de un gráfico o multigrafo uno por uno, asignando a cada borde el primer color disponible , a veces puede usar hasta 2Δ - 1 colores, que pueden ser casi el doble de colores que sea necesario. Sin embargo, tiene la ventaja de que puede usarse en la configuración del algoritmo en línea en el que el gráfico de entrada no se conoce de antemano; En este contexto, su relación competitiva es dos, y esto es óptimo: ningún otro algoritmo en línea puede lograr un mejor rendimiento. [11] Sin embargo, si los bordes llegan en un orden aleatorio, y el gráfico de entrada tiene un grado que es al menos logarítmico, entonces se pueden lograr proporciones competitivas más pequeñas. [12]
Varios autores han hecho conjeturas que implican que el índice cromático fraccional de cualquier multigrafo (un número que puede calcularse en tiempo polinómico usando programación lineal ) está dentro de uno de los índices cromáticos. [13] Si estas conjeturas son verdaderas, sería posible calcular un número que nunca está a más de uno del índice cromático en el caso multigráfico, haciendo coincidir lo que se conoce a través del teorema de Vizing para gráficos simples. Aunque no se ha comprobado en general, se sabe que estas conjeturas se mantienen cuando el índice cromático es al menos, como puede suceder con multigrafos con multiplicidad suficientemente grande. [14]
Algoritmos exactos [ editar ]
Es sencillo probar si un gráfico puede ser coloreado en el borde con uno o dos colores, por lo que el primer caso no trivial de coloración en el borde es probar si un gráfico tiene un color en 3 bordes. Como demostró Kowalik (2009) , es posible probar si un gráfico tiene una coloración de 3 bordes en el tiempo O (1.344 n ) , mientras se usa solo espacio polinómico. Aunque este límite de tiempo es exponencial, es significativamente más rápido que una búsqueda de fuerza bruta sobre todas las asignaciones posibles de colores a los bordes. Cada gráfico biconnectado de 3 regulares con n vértices tiene O (2 n / 2 ) coloraciones de 3 bordes; todo lo cual se puede enumerar en el tiempo O (2 n / 2 )(algo más lento que el tiempo para encontrar un solo color); Como observó Greg Kuperberg , la gráfica de un prisma sobre un polígono de n / 2 lados tiene coloraciones Ω (2 n / 2 ) (inferior en lugar de límite superior), lo que muestra que este límite es ajustado. [15]
Al aplicar algoritmos exactos para la coloración de vértices en el gráfico lineal del gráfico de entrada, es posible colorear de manera óptima cualquier gráfico con m bordes, independientemente del número de colores necesarios, en el tiempo 2 m m O (1) y el espacio exponencial , o en el tiempo O (2.2461 m ) y solo espacio polinomial ( Björklund, Husfeldt & Koivisto 2009 ).
Debido a que la coloración de los bordes es NP-completa incluso para tres colores, es poco probable que sea un parámetro fijo manejable cuando se parametriza por la cantidad de colores. Sin embargo, es manejable para otros parámetros. En particular, Zhou, Nakano y Nishizeki (1996) mostraron que para los gráficos de ancho de árbol w , se puede calcular una coloración de borde óptima en el tiempo O ( nw (6 w ) w ( w + 1) / 2 ) , un límite que depende superexponencialmente en w pero solo linealmente en el número n de vértices en el gráfico.
Nemhauser y Park (1991) formulan el problema de coloración de bordes como un programa de enteros y describen su experiencia usando un solucionador de programación de enteros para gráficos de colores de bordes. Sin embargo, no realizaron ningún análisis de complejidad de su algoritmo.
Propiedades adicionales [ editar ]
Un gráfico es únicamente k -edge-colorable si solo hay una forma de dividir los bordes en k clases de color, ¡ignorando el k ! posibles permutaciones de los colores. Para k ≠ 3 , los únicos gráficos únicos para k -edge-colorable son caminos, ciclos y estrellas , pero para k = 3 otros gráficos también pueden ser únicamente k -edge-colorable. Cada gráfico único de 3 bordes colorables tiene exactamente tres ciclos hamiltonianos (formados al eliminar una de las tres clases de color), pero existen gráficos de 3 regulares que tienen tres ciclos hamiltonianos y no son únicamente 3 colores, como elgráficos de Petersen generalizados G (6 n + 3, 2) para n ≥ 2 . El único gráfico no plano único de 3 colores conocido es el gráfico generalizado de Petersen G (9,2) , y se ha conjeturado que no existen otros. [dieciséis]
Folkman y Fulkerson (1969) investigaron las secuencias no crecientes de números m 1 , m 2 , m 3 , ... con la propiedad de que existe una coloración de borde adecuada de un gráfico G con m 1 bordes del primer color, m 2 bordes del segundo color, etc. Observaron que, si una secuencia P es factible en este sentido, y es mayor en orden lexicográfico que una secuencia Q con la misma suma, entonces Q también es factible. Para, si P > Qen orden lexicográfico, entonces P puede transformarse en Q mediante una secuencia de pasos, cada uno de los cuales reduce uno de los números m i en una unidad y aumenta otro número posterior m j con i < j en una unidad. En términos de colorantes de borde, a partir de una coloración que se da cuenta de P , cada uno de estos mismos pasos se pueden realizar mediante el canje de colores i y j en una cadena Kempe , un camino máxima de bordes que se alternan entre los dos colores. En particular, cualquier gráfico tiene una equitativa coloración de bordes, una coloración de bordes con un número óptimo de colores en el que cada dos clases de color difieren en tamaño como máximo en una unidad.
El teorema de De Bruijn-Erd puede usarse para transferir muchas propiedades de coloración de bordes de gráficos finitos a gráficos infinitos . Por ejemplo, los teoremas de Shannon y Vizing que relacionan el grado de un gráfico con su índice cromático se generalizan directamente a gráficos infinitos. [17]
Richter (2011) considera el problema de encontrar un dibujo gráfico de un gráfico cúbico dado con las propiedades de que todos los bordes del dibujo tienen una de tres pendientes diferentes y que no hay dos bordes en la misma línea entre sí. Si tal dibujo existe, entonces claramente las pendientes de los bordes se pueden usar como colores en un color de 3 bordes del gráfico. Por ejemplo, el dibujo del gráfico de utilidad K 3,3 como los bordes y diagonales largas de un hexágono regular representa una coloración de 3 bordes del gráfico de esta manera. Como muestra Richter, un gráfico bipartito simple de 3 regulares, con un color Tait dado, tiene un dibujo de este tipo que representa el color dado si y solo si el gráfico es3 bordes conectados . Para un gráfico no bipartito, la condición es un poco más complicada: un color dado puede representarse mediante un dibujo si la doble cubierta bipartita del gráfico está conectada por 3 bordes y si eliminar cualquier par de bordes monocromáticos conduce a un subgrafo que aun no es bipartito. Todas estas condiciones pueden ser probadas fácilmente en tiempo polinómico; sin embargo, el problema de probar si un gráfico de 4 bordes de 4 colores tiene un dibujo con bordes de cuatro pendientes, que representan los colores por pendientes, está completo para la teoría existencial de los reales , una clase de complejidad al menos tan difícil como siendo NP-completo.
Además de estar relacionado con el grado máximo y el número máximo de coincidencia de un gráfico, el índice cromático está estrechamente relacionado con la arboricidad lineal la ( G ) de un gráfico G , el número mínimo de bosques lineales (uniones disjuntas de caminos) en los que los bordes del gráfico pueden estar divididos. Una coincidencia es un tipo especial de bosque lineal, y en la otra dirección, cualquier bosque lineal puede tener 2 bordes, por lo que por cada G se deduce que la ( G ) ≤ χ ′ ( G ) ≤ 2 la ( G ) . La conjetura de Akiyama (llamada así por Jin Akiyama ) establece que, de lo cual se seguiría más fuertemente que 2 la ( G ) - 2 ≤ χ ′ ( G ) ≤ 2 la ( G ) . Para gráficos de grado máximo tres, la ( G ) siempre es exactamente dos, por lo que en este caso el límite χ ′ ( G ) ≤ 2 la ( G ) coincide con el límite dado por el teorema de Vizing. [18]
Otros tipos de coloración de bordes [ editar ]
El número Thue de un gráfico es el número de colores requeridos en una coloración de borde que cumple con el requisito más estricto de que, en cada ruta de longitud par, las mitades primera y segunda de la ruta forman diferentes secuencias de colores.
La arboricidad de un gráfico es el número mínimo de colores necesarios para que los bordes de cada color no tengan ciclos (en lugar de, en el problema de coloración de bordes estándar, no tener pares de bordes adyacentes). Es decir, es el número mínimo de bosques en los que se pueden dividir los bordes del gráfico. [19] A diferencia del índice cromático, la arboricidad de un gráfico puede calcularse en tiempo polinómico. [20]
El color de borde de lista es un problema en el que se le da un gráfico en el que cada borde está asociado con una lista de colores, y debe encontrar un color de borde adecuado en el que el color de cada borde se extraiga de esa lista. El índice cromático de la lista de un gráfico G es el número k más pequeño con la propiedad de que, sin importar cómo se elijan listas de colores para los bordes, siempre que cada borde tenga al menos k colores en su lista, se garantiza un color para ser posible. Por lo tanto, el índice cromático de la lista siempre es al menos tan grande como el índice cromático. La conjetura de Dinitz sobre la finalización de cuadrados latinos parciales puede reformularse como la afirmación de que el número cromático del borde de la lista degráfico bipartito completo K n, n es igual a su número cromático de borde, n . Galvin (1995) resolvió la conjetura demostrando, de manera más general, que en cada gráfico bipartito el índice cromático y el índice cromático de la lista son iguales. Se ha conjeturado que la igualdad entre el índice cromático y el índice cromático de la lista es válida, incluso de manera más general, para multigrafos arbitrarios sin bucles automáticos; Esta conjetura permanece abierta.
Muchas otras variaciones comúnmente estudiadas de coloración de vértices también se han extendido a los colores de los bordes. Por ejemplo, la coloración de borde completa es la variante de coloración de borde de coloración completa , una coloración de borde adecuada en la que cada par de colores debe estar representado por al menos un par de bordes adyacentes y en el que el objetivo es maximizar el número total de colores . [21] La coloración de borde fuerte es la variante de coloración de borde de coloración fuerte , una coloración de borde en la que cada dos bordes con puntos finales adyacentes deben tener colores diferentes. [22] La coloración del borde fuerte tiene aplicaciones en esquemas de asignación de canales para redes inalámbricas . [23]
La coloración de borde acíclico es la variante de coloración de borde de coloración acíclica , una coloración de borde para la cual cada dos clases de color forman una subgrafía acíclica (es decir, un bosque). [24] El índice cromático acíclico de un gráfico, denotado por , es el menor número de colores necesarios para tener un color de borde acíclico adecuado de . Se ha conjeturado que, dónde es el grado máximo de . [25] Actualmente, el límite más conocido es. [26] El problema se vuelve más fácil cuandoTiene gran circunferencia . Más específicamente, hay una constante tal que si la circunferencia de Por lo menos , luego . [27] Un resultado similar es que para todos existe un tal que si tiene circunferencia al menos , luego . [28]
Eppstein (2013) estudió los colores de 3 bordes de los gráficos cúbicos con la propiedad adicional de que no hay dos ciclos bicromáticos que compartan más de un borde. Mostró que la existencia de tal coloración es equivalente a la existencia de un dibujo del gráfico en una cuadrícula entera tridimensional, con bordes paralelos a los ejes de coordenadas y cada línea paralela al eje que contiene como máximo dos vértices. Sin embargo, al igual que el problema estándar de coloración de 3 bordes, encontrar un color de este tipo es NP-completo.
La coloración total es una forma de coloración que combina la coloración de vértices y bordes, al requerir que se coloreen tanto los vértices como los bordes. Cualquier par incidente de un vértice y una arista, o una arista y una arista, debe tener colores distintos, al igual que dos vértices adyacentes. Se ha conjeturado (combinando el teorema de Vizing y el teorema de Brooks ) que cualquier gráfico tiene una coloración total en la que el número de colores es como máximo el grado máximo más dos, pero esto no se ha comprobado.
Si un gráfico de 3 regulares en una superficie tiene 3 bordes de color, su gráfico dual forma una triangulaciónde la superficie que también está coloreada en los bordes (aunque no, en general, está adecuadamente coloreada en los bordes) de tal manera que cada triángulo tenga un borde de cada color. Se pueden usar otros colores y orientaciones de triangulaciones, con otras restricciones locales sobre cómo se organizan los colores en los vértices o caras de la triangulación, para codificar varios tipos de objetos geométricos. Por ejemplo, las subdivisiones rectangulares (particiones de una subdivisión rectangular en rectángulos más pequeños, con tres rectángulos reunidos en cada vértice) pueden describirse combinatoriamente mediante un "etiquetado regular", una doble coloración de los bordes de una triangulación dual a la subdivisión, con La restricción de que los bordes incidentes en cada vértice forman cuatro subsecuencias contiguas, dentro de las cuales los colores son los mismos. Este etiquetado es dual a una coloración de la subdivisión rectangular en la cual los bordes verticales tienen un color y los bordes horizontales tienen el otro color. También se pueden usar restricciones locales similares en el orden en que pueden aparecer bordes coloreados alrededor de un vértice para codificar incrustaciones de cuadrículas de líneas rectas de gráficos planos y poliedros tridimensionales con lados paralelos a los ejes. Para cada uno de estos tres tipos de etiquetado regular, el conjunto de etiquetado regular de un gráfico fijo forma unred distributiva que se puede usar para enumerar rápidamente todas las estructuras geométricas basadas en el mismo gráfico (como todos los poliedros paralelos al eje que tienen el mismo esqueleto) o para encontrar estructuras que satisfagan restricciones adicionales. [29]
Un autómata finito determinista puede interpretarse como un gráfico dirigido en el que cada vértice tiene el mismo grado d , y en el que los bordes tienen un color d de tal manera que cada dos bordes con el mismo vértice de origen tienen colores distintos. El problema del color de la carretera es el problema de colorear el borde de un gráfico dirigido con grados de salida uniformes, de tal manera que el autómata resultante tenga una palabra de sincronización . Trahtman (2009) resolvió el problema de la coloración vial al demostrar que dicha coloración se puede encontrar siempre que el gráfico dado esté fuertemente conectado y sea aperiódico .
El teorema de Ramsey se refiere al problema de k -colorear los bordes de un gran gráfico completo K n para evitar crear subgrafías completas monocromáticas K s de un tamaño determinado s . Según el teorema, existe un número R k ( s ) tal que, siempre que n ≥ R ( s ) , tal coloración no sea posible. Por ejemplo, R 2 (3) = 6 , es decir, si los bordes del gráfico K 6 son de 2 colores, siempre habrá un triángulo monocromático.
Se dice que una ruta en un gráfico de color de borde es una ruta de arco iris si no se repite ningún color en ella. Se dice que un gráfico es de color arcoíris si hay un camino de arcoíris entre dos pares de vértices. Una coloración de borde de un gráfico G con colores 1.. . t es un intervalo de coloración t si se usan todos los colores, y los colores de los bordes incidentes en cada vértice de G son distintos y forman un intervalo de enteros.
Aplicaciones [ editar ]
Los colores de los bordes de los gráficos completos se pueden usar para programar un torneo round-robin en la menor cantidad de rondas posible para que cada par de competidores jueguen entre sí en una de las rondas; En esta aplicación, los vértices del gráfico corresponden a los competidores en el torneo, los bordes corresponden a los juegos y los colores del borde corresponden a las rondas en las que se juegan los juegos. [30] También se pueden utilizar técnicas de coloración similares para programar otras parejas de deportes que no son todo juego; por ejemplo, en la Liga Nacional de Fútbol, se determinan los pares de equipos que jugarán entre sí en un año determinado, en función de los registros de los equipos del año anterior, y luego se aplica un algoritmo de coloreado de bordes al gráfico formado por el conjunto de emparejamientos para asignar juegos a los fines de semana en que se juegan. [31] Para esta aplicación, el teorema de Vizing implica que no importa qué conjunto de parejas se elija (siempre y cuando ningún equipo juegue entre sí dos veces en la misma temporada), siempre es posible encontrar un horario que utilice como máximo un fin de semana más que hay juegos por equipo.
La programación de taller abierto es un problema de programación de procesos de producción., en el que hay un conjunto de objetos para fabricar, cada objeto tiene un conjunto de tareas para realizar (en cualquier orden), y cada tarea debe realizarse en una máquina específica, evitando cualquier otra tarea que requiera lo mismo máquina de ser realizada al mismo tiempo. Si todas las tareas tienen la misma longitud, entonces este problema puede formalizarse como uno de borde coloreando un multigrafo bipartito, en el que los vértices en un lado de la bipartición representan los objetos a fabricar, los vértices en el otro lado de la bipartición representan Las máquinas de fabricación, los bordes representan las tareas que deben realizarse y los colores representan los pasos de tiempo en los que se puede realizar cada tarea. Dado que la coloración de bordes bipartitos se puede realizar en tiempo polinómico, lo mismo es cierto para este caso restringido de programación de taller abierto.[32]
Gandham, Dawande y Prakash (2005) estudian el problema de la programación de enlaces para protocolos de comunicaciones de redes de acceso múltiple por división de tiempo en redes de sensores como una variante de coloración de bordes. En este problema, uno debe elegir intervalos de tiempo para los bordes de una red de comunicaciones inalámbricas para que cada nodo de la red pueda comunicarse con cada nodo vecino sin interferencia. Usar un color de borde fuerte (y usar dos intervalos de tiempo para cada color de borde, uno para cada dirección) resolvería el problema, pero podría usar más intervalos de tiempo de los necesarios. En cambio, buscan una coloración del gráfico dirigido formado duplicando cada borde no dirigido de la red, con la propiedad de que cada borde dirigido uvtiene un color diferente de los bordes que salen de v y de los vecinos de v . Proponen una heurística para este problema basada en un algoritmo distribuido para la coloración de bordes (Δ + 1) junto con una fase de posprocesamiento que reprograma los bordes que podrían interferir entre sí.
En la comunicación por fibra óptica , el problema de la coloración de la ruta es el problema de asignar colores (frecuencias de luz) a pares de nodos que desean comunicarse entre sí, y rutas a través de una red de comunicaciones de fibra óptica para cada par, sujeto a la restricción que no hay dos caminos que compartan un segmento de fibra usan la misma frecuencia entre sí. Las rutas que pasan a través del mismo conmutador de comunicación pero no a través de ningún segmento de fibra pueden usar la misma frecuencia. Cuando la red de comunicaciones se organiza como una red estelar, con un solo interruptor central conectado por fibras separadas a cada uno de los nodos, el problema de coloreado de la ruta puede modelarse exactamente como un problema de coloreado de bordes de un gráfico o multigrafo, en el que los nodos comunicantes forman los vértices del gráfico, pares de nodos que desean para comunicarse desde los bordes del gráfico, y las frecuencias que pueden usarse para cada par forman los colores del problema de coloración del borde. Para las redes de comunicaciones con una topología de árbol más general, las soluciones de coloración de ruta local para las redes en estrella definidas por cada conmutador en la red pueden parchearse para formar una única solución global. [33]
Problemas abiertos [ editar ]
Jensen y Toft (1995) enumeran 23 problemas abiertos relacionados con la coloración de bordes. Incluyen:
- La conjetura de Goldberg (1973) de que el índice cromático y el índice fraccional están uno dentro del otro, lo que permitiría aproximar el índice cromático dentro de un color en el tiempo polinomial.
- Varias conjeturas de Jakobsen y otras sobre la estructura de gráficos críticos para colorear los bordes, gráficos de clase 2 de manera que cualquier subgrafo tenga un grado máximo menor o sea de clase 1. Jakobsen originalmente conjeturó que todos los gráficos críticos tienen un número impar de vértices, pero Esto finalmente fue refutado. Varias otras conjeturas que debilitan esta, o limitan el número de vértices de gráficos críticos y multigrafos críticos, permanecen abiertas.
- El problema de Vizing de clasificar los grados máximos que son posibles para los gráficos planos de clase 2.
- La conjetura del subgrafo de AJW Hilton, que indica que las gráficas con un grado de al menos n / 3 son de clase 1 o contienen una subgrafía con el mismo grado Δ que la gráfica original, y con un número impar k de vértices, tal que el número de bordes en el subgrafo es mayor que Δ ( k - 1) / 2 , y una conjetura similar de Herbert Grötzsch y Paul Seymour con respecto a los gráficos planos en lugar de los gráficos de alto grado.
- Una conjetura de Amanda Chetwynd y Anthony Hilton (posiblemente volviendo antes al trabajo de Gabriel Andrew Dirac ) de que los gráficos regulares con un número par n de vértices y con un grado de al menos n / 2 son de clase 1.
- Una conjetura de Claude Berge y DR Fulkerson de que los multigrafos de 6 regulares formados al doblar cada borde de un gráfico simple de 3 regulares sin puente pueden ser coloreados con seis colores.
- Una conjetura de Fiorini y Wilson de que cada gráfico plano sin triángulo , que no sea la garra K 1,3 , no es únicamente colorable en 3 bordes .
- A 2.012 conjetura de que si G es un d -regular planar multigrafo, entonces G es decir d -Edge-coloreable si y sólo si G es extrañamente d conectado--Edge. Esta conjetura es una generalización del teorema de los cuatro colores , que surge en d = 3. Maria Chudnovsky , Katherine Edwards y Paul Seymour demostraron que un multigrafo plano 8 regular tiene un número cromático de borde de 8.
No hay comentarios:
Publicar un comentario