TEORÍA DE TÉRMINOS DE GRAFOS

En la teoría de grafos , una rama de las matemáticas , el color de lista es un tipo de color de gráfico donde cada vértice puede restringirse a una lista de colores permitidos. Fue estudiado por primera vez en la década de 1970 en documentos independientes por Vizing y por Erdős , Rubin y Taylor. 

Definición [ editar ]

Dado un gráfico G y un conjunto de colores L ( v ) para cada vértice v (llamado lista ), un color de lista es una función de elección que asigna cada vértice v a un color en la lista L ( v ). Al igual que con el color del gráfico, generalmente se supone que un color de lista es apropiado , lo que significa que no hay dos vértices adyacentes que reciban el mismo color. Un gráfico es k- elegible (o k -list-colorable ) si tiene una lista de colores adecuada, sin importar cómo se asigne una lista de kcolores a cada vértice. La capacidad de elección (o la capacidad de coloración de la lista o el número cromático de la lista ) ch ( G ) de un gráfico G es el menor número k, de modo que G es k- elegible.

En términos más generales, para una función f que asigna un número entero positivo f ( v ) a cada vértice v , un gráfico G es f- elegible (o f -list-colorable ) si tiene una lista de colores sin importar cómo se asigna una lista de f ( v ) colores para cada vértice v . En particular, si$${\ displaystyle f (v) = k}para todos los vértices v , f -choosability corresponde a k -choosability.

Ejemplos [ editar ]

Considere el gráfico bipartito completo G = K _2,4 , que tiene seis vértices A , B , W , X , Y , Z de modo que A y B estén conectados a todos los W , X , Y y Z , y ningún otro vértice estan conectados. Como gráfico bipartito, G tiene el número cromático habitual 2: uno puede colorear A y B en un color y W , X , Y , Zen otro y no hay dos vértices adyacentes tendrán el mismo color. Por otro lado, G tiene un número cromático de lista mayor que 2, como muestra la siguiente construcción: asigne a A y B las listas {rojo, azul} y {verde, negro}. Asigne a los otros cuatro vértices las listas {rojo, verde}, {rojo, negro}, {azul, verde} y {azul, negro}. Independientemente de la elección que haga uno de un color de la lista de A y un color de la lista de B , habrá otro vértice tal que ambas opciones ya se utilizan para colorear a sus vecinos. Por lo tanto, G no es elegible en 2.

Por otro lado, es fácil ver que G es elegible en 3: elegir colores arbitrarios para los vértices A y B deja al menos un color disponible para cada uno de los vértices restantes, y estos colores pueden elegirse arbitrariamente.

Una instancia de coloración de lista en el gráfico bipartito completo K _3,27 con tres colores por vértice. No importa qué colores se elijan para los tres vértices centrales, uno de los 27 vértices exteriores será incoloro, lo que muestra que el número cromático de la lista de K _3,27 es al menos cuatro.

De manera más general, sea q un número entero positivo y sea G el gráfico bipartito completo K _q , q ^q . Deje que los colores disponibles estén representados por los q ² números diferentes de dos dígitos en la raíz q . En un lado de la bipartición, permita que los vértices q reciban conjuntos de colores { i 0, i 1, i 2, ... } en los que los primeros dígitos sean iguales entre sí, para cada una de las q posibles opciones de primer dígito  i . En el otro lado de la bipartición, deje q^{a los} vértices ^{q se} les dan conjuntos de colores {0 a , 1 b , 2 c , ... } en los que los primeros dígitos son todos distintos, para cada una de las q ^q posibles elecciones de la q -tupla ( a , b , c , ...) La ilustración muestra un ejemplo más grande de la misma construcción, con q  = 3.

Entonces, G no tiene una lista de colores para L : no importa qué conjunto de colores se elija para los vértices en el lado pequeño de la bipartición, esta elección entrará en conflicto con todos los colores para uno de los vértices en el otro lado de La bipartición. Por ejemplo, si el vértice con el conjunto de colores {00,01} tiene el color 01 y el vértice con el conjunto de colores {10,11} tiene el color 10, entonces el vértice con el conjunto de colores {01,10} no puede colorearse. Por lo tanto, el número cromático de la lista de G es al menos q  + 1. ^[2]

Del mismo modo, si $${\ displaystyle n = {\ binom {2k-1} {k}}}, entonces el gráfico bipartito completo K _n , n no es k- elegible. Para, supongamos que 2 k  - 1 colores están disponibles en total, y que, en un solo lado de la bipartición, cada vértice tiene a su disposición una k -tupla diferente de estos colores que el otro vértice. Luego, cada lado de la bipartición debe usar al menos k colores, porque cada conjunto de k  - 1 colores será disjunto de la lista de un vértice. Como al menos k colores se usan en un lado y al menos kse usan en el otro, debe haber un color que se use en ambos lados, pero esto implica que dos vértices adyacentes tienen el mismo color. En particular, el gráfico de utilidad K _3,3 tiene un número cromático de lista de al menos tres, y el gráfico K _10,10 tiene un número cromático de lista de al menos cuatro. ^[3]

Propiedades [ editar ]

Para un gráfico G , dejar que χ ( G ) denotan el número cromática y Δ ( G ) el grado máximo de G . El número de coloración de la lista ch ( G ) satisface las siguientes propiedades.

1. ch ( G ) ≥ χ ( G ). Un gráfico k -list-colorable debe en particular tener una lista de colores cuando cada vértice se le asigna la misma lista de k colores, que corresponde a un k -coloring habitual .
2. ch ( G ) no puede ser limitada en términos de número cromática en general, es decir, no hay una función f tal que ch ( G ) ≤ f (χ ( G )) se mantiene para cada gráfico G . En particular, como muestran los ejemplos completos de gráficos bipartitos, existen gráficos con χ ( G ) = 2 pero con ch ( G ) arbitrariamente grande. ^[2]
3. ch ( G ) ≤ χ ( G ln) ( n ), donde n es el número de vértices de G . ^[4] [5]
4. ch ( G ) ≤ Δ ( G ) + 1. ^[3] [6]
5. ch ( G ) ≤ 5 si G es un gráfico plano . ^[7]
6. ch ( G ) ≤ 3 si G es un gráfico plano bipartito . ^[8]

Cálculo de la capacidad de elección y ( a , b ) capacidad de elección [ editar ]

Se han considerado dos problemas algorítmicos en la literatura:

1. k - capacidad de elección : decida si un gráfico dado es k- elegible para una k dada , y
2. ( a , b ) - capacidad de elección : decida si un gráfico dado es f- elegible para una función determinada$${\ displaystyle f: V \ to \ {a, \ dots, b \}}.

Se sabe que k- capacidad de elección en gráficos bipartitos es$${\ displaystyle \ Pi _ {2} ^ {p}}-completa para cualquier k ≥ 3, y lo mismo se aplica para la posibilidad de elegir 4 en gráficos planos, la posibilidad de elegir 3 en gráficos libres de triángulos planos y (2, 3) posibilidad de elegir en gráficos planos bipartitos . ^[9] [10] Para gráficos libres de P ₅ , es decir, gráficos que excluyen un gráfico de ruta de 5 vértices , la capacidad de elección de k es manejable con parámetros fijos . ^[11]

Es posible probar si un gráfico se puede elegir 2 en tiempo lineal eliminando repetidamente vértices de grado cero o uno hasta alcanzar el núcleo 2 del gráfico, después de lo cual ya no es posible realizar tales eliminaciones. El gráfico inicial se puede elegir en 2 si y solo si su núcleo de 2 núcleos es un ciclo par o un gráfico theta formado por tres caminos con puntos finales compartidos, con dos caminos de longitud dos y el tercer camino con cualquier longitud par. ^[3]

Aplicaciones [ editar ]

La coloración de la lista surge en problemas prácticos relacionados con la asignación de canal / frecuencia.

En la teoría de grafos , una rama de las matemáticas, el espacio de ciclo (binario) de un gráfico no dirigido es el conjunto de sus subgrafos eulerianos .

Este conjunto de subgrafías se puede describir algebraicamente como un espacio vectorial sobre el campo finito de dos elementos . La dimensión de este espacio es el rango de circuito del gráfico. El mismo espacio también se puede describir en términos de topología algebraica como el primer grupo de homología del gráfico. Usando la teoría de la homología, el espacio del ciclo binario puede generalizarse a espacios del ciclo sobre anillos arbitrarios .

Definiciones [ editar ]

Teoría de grafos [ editar ]

Un subgrafo que abarca de un dado gráfico G se puede definir de cualquier subconjunto S de los bordes de G . El subgrafo tiene el mismo conjunto de vértices que el propio G (este es el significado de la palabra "abarcar") pero tiene los elementos de S como sus bordes. Por lo tanto, un gráfico G con m bordes tiene 2 ^m que abarca subgraphs, incluyendo G en sí, así como el gráfico de vacío en el mismo conjunto de vértices como G . La colección de todas las subgrafías que abarcan un gráfico G forma el espacio de borde deG . ^[1] [2]

Se dice que un gráfico G , o una de sus subgrafías, es euleriano si cada uno de sus vértices tiene un número par de bordes incidentes (este número se llama el grado del vértice). Esta propiedad lleva el nombre de Leonhard Euler, quien demostró en 1736, en su trabajo en los Siete Puentes de Königsberg , que un gráfico conectado tiene un recorrido que visita cada borde exactamente una vez si y solo si es Eulerian. Sin embargo, un subgrafo euleriano no necesita estar conectado; por ejemplo, el gráfico vacío, en el que todos los vértices están desconectados entre sí, es euleriano. El espacio del ciclo de un gráfico es la colección de sus subgráficos que abarcan Eulerian. ^[1] [2]

Álgebra [ editar ]

Si se aplica una operación de conjunto , como la unión o intersección de conjuntos, a dos subgrafos que abarcan un gráfico dado, el resultado será nuevamente un subgrafo. De esta manera, el espacio de borde de un gráfico arbitrario puede interpretarse como un álgebra booleana . ^[3]

La diferencia simétrica de dos subgrafos eulerianos (rojo y verde) es un subgrafo euleriano (azul).

El espacio del ciclo, también, tiene una estructura algebraica, pero más restrictiva. La unión o intersección de dos subgrafos eulerianos puede no ser euleriana. Sin embargo, la diferencia simétrica de dos subgráficos eulerianos (el gráfico que consiste en los bordes que pertenecen exactamente a uno de los dos gráficos dados) es nuevamente euleriano. ^[1] Esto se deduce del hecho de que la diferencia simétrica de dos conjuntos con un número par de elementos también es par. La aplicación de este hecho por separado a las vecindades de cada vértice muestra que el operador de diferencia simétrica conserva la propiedad de ser euleriano.

Una familia de conjuntos cerrados bajo la operación de diferencia simétrica puede describirse algebraicamente como un espacio vectorial sobre el campo finito de dos elementos $${\ displaystyle \ mathbb {Z} _ {2}}. ^[4] Este campo tiene dos elementos, 0 y 1, y sus operaciones de suma y multiplicación pueden describirse como la suma y multiplicación familiar de enteros , tomada en el módulo 2 . Un espacio vectorial consiste en un conjunto de elementos junto con una operación de suma y multiplicación escalar que satisface ciertas propiedades que generalizan las propiedades de los espacios vectoriales reales familiares ; para el espacio del ciclo, los elementos del espacio vectorial son las subgrafías Eulerianas, la operación de suma es la diferencia simétrica, la multiplicación por el escalar 1 es la operación de identidad , y la multiplicación por el escalar 0 lleva cada elemento al gráfico vacío, que forma el identidad aditiva elemento para el espacio del ciclo.

El espacio del borde también es un espacio vectorial sobre $${\ displaystyle \ mathbb {Z} _ {2}}si usamos la diferencia simétrica como suma. Como espacios vectoriales, el espacio del ciclo y el espacio de corte del gráfico (la familia de conjuntos de bordes que abarcan los cortes del gráfico) son los complementos ortogonales entre sí dentro del espacio del borde. Esto significa que un conjunto$${\ displaystyle S} de bordes en un gráfico forma un corte si y solo si cada subgrafo euleriano tiene un número par de bordes en común con $${\ displaystyle S}y $${\ displaystyle S} forma un subgrafo euleriano si y solo si cada corte tiene un número par de bordes en común con $${\ displaystyle S}. ^[2] Aunque estos dos espacios son complementos ortogonales, algunos gráficos tienen subgrafías no vacías que pertenecen a ambos. Tal subgrafo (un corte euleriano) existe como parte de un gráfico$${\ displaystyle G} si y solo si $${\ displaystyle G}tiene un número par de bosques que se extienden . ^[5]

Topología [ editar ]

Un gráfico no dirigido puede verse como un complejo simplicial con sus vértices como simplificadores de dimensión cero y los bordes como simplificadores unidimensionales. ^[6] El complejo de cadena de este espacio topológico consiste en su espacio de borde y espacio de vértice (el álgebra booleana de conjuntos de vértices), conectado por un operador de límite que asigna cualquier subgrafo de expansión (un elemento del espacio de borde) a su conjunto de vértices de grados impares (un elemento del espacio de vértices). El grupo de homologia

$${\ displaystyle H_ {1} (G, \ mathbb {Z} _ {2})}

consiste en los elementos del espacio del borde que se asignan al elemento cero del espacio del vértice; Estas son exactamente las subgrafías eulerianas. Su operación grupal es la operación de diferencia simétrica en subgrafos eulerianos.

Sustitución $${\ displaystyle \ mathbb {Z} _ {2}}en esta construcción por un anillo arbitrario permite que la definición de espacios de ciclo se extienda a espacios de ciclo con coeficientes en el anillo dado, que forman módulos sobre el anillo. ^[7] En particular, el espacio del ciclo integral es el espacio

$${\ displaystyle H_ {1} (G, \ mathbb {Z}).}

Se puede definir en términos teóricos de gráficos eligiendo una orientación arbitraria del gráfico y definiendo un ciclo integral de un gráfico$${\ displaystyle G} ser una asignación de enteros a los bordes de $${\ displaystyle G}(un elemento del grupo abeliano libre sobre los bordes) con la propiedad de que, en cada vértice, la suma de los números asignados a los bordes entrantes es igual a la suma de los números asignados a los bordes salientes. ^[8]

Un miembro de $${\ displaystyle H_ {1} (G, \ mathbb {Z})} o de $${\ displaystyle H_ {1} (G, \ mathbb {Z} _ {k})} (el módulo de espacio del ciclo $${\ displaystyle k}) con la propiedad adicional de que todos los números asignados a los bordes son distintos de cero se llama flujo de cero o cero cero$${\ displaystyle k}-fluir. ^[9]

Rango de circuito [ editar ]

Artículo principal: Rango del circuito

Como espacio vectorial, la dimensión del espacio del ciclo de un gráfico con $${\ displaystyle n} vértices $${\ displaystyle m} bordes y $${\ displaystyle c} componentes conectados es$${\ displaystyle m-n + c}. ^{[1] [2] [10]} Este número puede interpretarse topológicamente como el primer número Betti del gráfico. ^[6] En la teoría de grafos, se conoce como rango de circuito , número ciclomático o nulidad del gráfico.

La combinación de esta fórmula para el rango con el hecho de que el espacio del ciclo es un espacio vectorial sobre el campo de dos elementos muestra que el número total de elementos en el espacio del ciclo es exactamente $${\ displaystyle 2 ^ {m-n + c}}.

Bases del ciclo [ editar ]

Artículo principal: base del ciclo

Una base de un espacio vectorial es un subconjunto mínimo de los elementos con la propiedad de que todos los demás elementos pueden escribirse como una combinación lineal de elementos básicos. Cada base de un espacio de dimensión finita tiene el mismo número de elementos, lo que equivale a la dimensión del espacio. En el caso del espacio del ciclo, una base es una familia de exactamente$${\ displaystyle m-n + c} Subgrafías eulerianas, con la propiedad de que cada subgrafía euleriana puede escribirse como la diferencia simétrica de una familia de elementos básicos.

Existencia [ editar ]

Según el teorema de Veblen , ^[11] cada subgrafo euleriano de un gráfico dado puede descomponerse en ciclos simples , subgrafos en los que todos los vértices tienen grados cero o dos y en los que los vértices de grado dos forman un conjunto conectado. Por lo tanto, siempre es posible encontrar una base en la cual los elementos básicos sean en sí mismos ciclos simples. Tal base se llama una base de ciclo del gráfico dado. Más fuertemente, siempre es posible encontrar una base en la cual los elementos básicos son ciclos inducidos o incluso (en un gráfico conectado a 3 vértices ) ciclos inducidos cuya eliminación no separa el gráfico restante. ^[12]

Bases fundamentales y débilmente fundamentales [ editar ]

Una forma de construir una base de ciclo es formar un bosque de expansión del gráfico, y luego para cada borde$${\ displaystyle e} que no pertenece al bosque, forma un ciclo $${\ displaystyle C_ {e}} que consiste en $${\ displaystyle e} junto con el camino en el bosque que conecta los puntos finales de $${\ displaystyle e}. El conjunto de ciclos$${\ displaystyle C_ {e}} formados de esta manera son linealmente independientes (cada uno contiene un borde $${\ displaystyle e} que no pertenece a ninguno de los otros ciclos) y tiene el tamaño correcto $${\ displaystyle m-n + c}para ser una base, por lo que necesariamente es una base. Una base formada de esta manera se denomina base de ciclo fundamental . ^[1]

Si existe un orden lineal de los ciclos en una base de ciclo tal que cada ciclo incluye al menos un borde que no es parte de ningún ciclo anterior, entonces la base del ciclo se llama débilmente fundamental . Cada base de ciclo fundamental es débilmente fundamental (para todos los ordenamientos lineales) pero no necesariamente viceversa. Existen gráficos y bases de ciclo para esos gráficos, que no son débilmente fundamentales. ^[13]

Bases de peso mínimo [ editar ]

Si los bordes de un gráfico tienen pesos numéricos reales, el peso de un subgrafo puede calcularse como la suma de los pesos de sus bordes. La base de peso mínimo del espacio del ciclo es necesariamente una base del ciclo, y puede construirse en tiempo polinómico. ^[8] La base de peso mínimo no siempre es débilmente fundamental, y cuando no lo es, es NP-difícil encontrar la base débilmente fundamental con el mínimo peso posible. ^[13]

Gráficos planos [ editar ]

Homología [ editar ]

Si un gráfico plano está incrustado en el plano, su complejo de cadena de bordes y vértices puede incrustarse en un complejo de cadena dimensional superior que también incluye los conjuntos de caras del gráfico. El mapa de límites de este complejo de cadena lleva cualquier cadena de 2 (un conjunto de caras) al conjunto de bordes que pertenecen a un número impar de caras en la cadena de 2. El límite de una cadena de 2 es necesariamente un subgrafo de Eulerian, y cada subgrafo de Eulerian se puede generar de esta manera a partir de exactamente dos cadenas de 2 diferentes (cada una de las cuales es el complemento de la otra). ^[14] De esto se deduce que el conjunto de caras delimitadas de la incrustación forma una base de ciclo para el gráfico plano: la eliminación de la cara sin límites de este conjunto de ciclos reduce el número de formas en que cada subgrafo de Eulerian se puede generar de dos a exactamente uno.

Criterio de planaridad de Mac Lane [ editar ]

Artículo principal: criterio de planaridad de Mac Lane

El criterio de planaridad de Mac Lane , llamado así por Saunders Mac Lane , caracteriza los gráficos planos en términos de sus espacios de ciclo y bases de ciclo. Establece que un gráfico finito no dirigido es plano si y solo si el gráfico tiene una base de ciclo en el que cada borde del gráfico participa en un máximo de dos ciclos básicos. En un gráfico plano, una base de ciclo formada por el conjunto de caras delimitadas de una incrustación necesariamente tiene esta propiedad: cada arista participa solo en los ciclos de base para las dos caras que separa. Por el contrario, si una base de ciclo tiene como máximo dos ciclos por borde, entonces sus ciclos se pueden usar como el conjunto de caras delimitadas de una incrustación plana de su gráfico. ^[14] [15]

Dualidad [ editar ]

El espacio del ciclo de un gráfico plano es el espacio de corte de su gráfico dual , y viceversa. La base del ciclo de peso mínimo para un gráfico plano no es necesariamente la misma que la base formada por sus caras limitadas: puede incluir ciclos que no son caras, y algunas caras pueden no incluirse como ciclos en la base del ciclo de peso mínimo. Existe una base de ciclo de peso mínimo en el que no se cruzan dos ciclos entre sí: por cada dos ciclos en la base, los ciclos encierran subconjuntos disjuntos de las caras delimitadas, o uno de los dos ciclos encierra el otro. Siguiendo la dualidad entre espacios de ciclo y espacios de corte, esta base para un gráfico plano corresponde a un árbol Gomory-Hu del gráfico dual, una base de peso mínimo para su espacio de corte. ^[dieciséis]

En ninguna parte fluye cero [ editar ]

En gráficos planos, coloraciones con$${\ displaystyle k} colores distintos son duales a ninguna parte fluye cero sobre el anillo $${\ displaystyle \ mathbb {Z} _ {k}} del módulo de enteros $${\ displaystyle k}. En esta dualidad, la diferencia entre los colores de dos regiones adyacentes está representada por un valor de flujo a través del borde que separa las regiones. En particular, la existencia de cero 4 flujos en ninguna parte es equivalente al teorema de los cuatro colores . El teorema de snark generaliza este resultado a gráficos no planos.