En la teoría de grafos , un flujo en ninguna parte cero o flujo NZ es un flujo de red que no es cero en ninguna parte. Está íntimamente conectado (por dualidad) a colorear gráficos planos .
Definiciones
Sea G = ( V , E ) un dígrafo y sea M un grupo abeliano . Un mapa φ : E → M es una M -circulación si para cada vértice v ∈ V
donde δ + ( v ) denota el conjunto de aristas fuera de v y δ - ( v ) denota el conjunto de aristas en v . A veces, esta condición se conoce como ley de Kirchhoff .
Si φ ( e ) ≠ 0 para cada e ∈ E , que llamamos φ una ninguna parte de cero flujo, un M -flow, o un flujo de Nueva Zelanda. Si k es un número entero y 0 <| φ ( e ) | < k entonces φ es un k -flujo. [1]
Otras nociones
Sea G = ( V , E ) una gráfica no dirigida . Una orientación de E es un k - flujo modular si para cada vértice v ∈ V tenemos:
Propiedades
- El conjunto de flujos M no necesariamente forma un grupo, ya que la suma de dos flujos en un borde puede sumar 0.
- (Tutte 1950) Un gráfico G tiene un flujo M si y solo si tiene un | M | -flujo. Como consecuencia, unel flujo existe si y solo si existe un flujo k . [1] Como consecuencia, G admite un flujo k entonces admite un flujo h donde.
- Independencia de orientación. Modifique un flujo en ninguna parte cero φ en un gráfico G eligiendo un borde e , invirtiéndolo y luego reemplazando φ ( e ) con - φ ( e ). Después de este ajuste, φ sigue siendo un flujo cero en ninguna parte. Además, si φ era originalmente un flujo k , entonces el φ resultante también es un flujo k . Por lo tanto, la existencia de un flujo M de ninguna parte cero o un flujo k de ninguna parte cero es independiente de la orientación de la gráfica. Por lo tanto, se dice que un gráfico G no dirigido tiene un flujo M en ninguna parte cero o un flujo k en ninguna parte cero si alguna (y, por lo tanto, todas) las orientaciones de G tienen tal flujo.
Polinomio de flujo
Dejar sea el número de M -flows en G . Satisface la fórmula de deleción-contracción : [1]
Combinando esto con la inducción podemos mostrar es un polinomio en dónde es el orden del grupo M . Nosotros llamamosel polinomio de flujo de G y grupo abeliano M .
Lo anterior implica que dos grupos de igual orden tienen el mismo número de flujos NZ. El orden es el único grupo de parámetros que importa, no la estructura de M . En particular Si
Los resultados anteriores fueron probados por Tutte en 1953 cuando estaba estudiando el polinomio de Tutte , una generalización del polinomio de flujo. [2]
Dualidad fluida-colorante
Gráficos planos sin puente
Hay una dualidad entre k -face colorantes y k -flows para sin puente grafos planos . Para ver esto, sea G un gráfico plano sin puentes dirigido con un color de cara k adecuado con colores Construye un mapa
por la siguiente regla: si el borde e tiene una cara de color x a la izquierda y una cara de color y a la derecha, entonces sea φ ( e ) = x - y . Entonces φ es un (NZ) k -flow desde x y y deben ser de colores diferentes.
Entonces, si G y G * son gráficos duales planos y G * es k -colorable (hay una coloración de las caras de G ), entonces G tiene un flujo NZ k . Usando inducción en | E ( G ) | Tutte demostró que lo contrario también es cierto. Esto se puede expresar de forma concisa como: [1]
donde RHS es el número de flujo , el k más pequeño para el que G permite un k -flujo.
Gráficos generales
La dualidad también es cierta para los flujos M generales :
- Dejar la cara colorear función sea con valores en M .
- Definir donde r 1 es la cara a la izquierda de e y r 2 está a la derecha.
- Para cada circulación Mhay una función de coloración c tal que (probado por inducción).
- c es a | E ( G ) | -color-rostro si y solo sies un NZ M -flow (sencillo).
La dualidad sigue combinando los dos últimos puntos. Podemos especializarnos enpara obtener resultados similares para k -flujos discutidos anteriormente. Dada esta dualidad entre los flujos y coloraciones de NZ, y dado que podemos definir los flujos de NZ para gráficos arbitrarios (no solo planos), podemos usar esto para extender los colorantes de caras a gráficos no planos. [1]
Aplicaciones
- G es coloreable en 2 caras si y solo si cada vértice tiene un grado par (considere los flujos NZ 2). [1]
- Dejar sea el grupo Klein-4 . Entonces, una gráfica cúbica tiene un flujo K si y solo si se puede colorear en 3 bordes . Como corolario, una gráfica cúbica que se puede colorear en 3 bordes es coloreable en 4 caras. [1]
- Un gráfico se puede colorear en 4 caras si y solo si permite un flujo de 4 NZ (consulte el teorema de los cuatro colores ). El gráfico de Petersen no tiene un flujo de 4 NZ, y esto llevó a la conjetura de 4 flujos (ver más abajo).
- Si G es una triangulación, entonces G es 3- (vértice) coloreable si y solo si cada vértice tiene un grado par. Según la primera viñeta, el gráfico dual G * es 2-colorante y, por lo tanto, bipartito y cúbico plano. Entonces, G * tiene un flujo NZ 3 y, por lo tanto, es coloreable en 3 caras, lo que hace que el vértice G 3 sea colorable. [1]
Existencia de k -flujos
¿Todos los gráficos sin puentes tienen un flujo 5 cero en ninguna parte? ¿Todos los gráficos sin puentes que no tienen el gráfico de Petersen como menor tienen un flujo 4 cero en ninguna parte?
Surgen preguntas interesantes cuando se trata de encontrar flujos k cero en ninguna parte para valores pequeños de k . Se ha probado lo siguiente:
- Teorema de los 4 flujos de Jaeger. Cada gráfico de 4 aristas conectadas tiene un flujo de 4. [4]
Conjeturas de 3 flujos, 4 flujos y 5 flujos
A partir de 2019, lo siguiente está actualmente sin resolver (debido a Tutte ):
- Conjetura de los 3 flujos. Cada gráfico conectado por 4 aristas tiene un flujo 3 en ninguna parte cero. [6]
- Conjetura de los 4 flujos. Cada gráfico sin puente que no tenga el gráfico de Petersen como menor tiene un flujo 4 en ninguna parte cero. [7]
- Conjetura de los 5 flujos. Cada gráfico sin puente tiene un flujo 5 en ninguna parte cero. [8]
Lo contrario de la conjetura de 4 flujos no se cumple ya que la gráfica completa K 11 contiene una gráfica de Petersen y una de 4 flujos. [1] Para gráficos cúbicos sin puentes sin Petersen minor, existen 4 flujos según el teorema de snark (Seymour, et al 1998, aún no publicado). El teorema de los cuatro colores es equivalente a la afirmación de que ningún snark es plano. [1]
Ver también
- Espacio de ciclo
- Conjetura de la cubierta doble del ciclo
- Teorema de los cuatro colores
- Coloración gráfica
- Coloración de bordes
- Polinomio de Tutte
Referencias
- ↑ a b c d e f g h i j Diestel, Reinhard, 1959- Verfasser. (30 de junio de 2017). Teoría de grafos . ISBN 9783662536216. OCLC 1048203362 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Tutte, William Thomas (1953). "Una contribución a la teoría de los polinomios cromáticos" . Cite journal requiere
|journal=
( ayuda ) - ^ Para un resultado más fuerte en la enumeración de-fluye con un límite en la cantidad máxima de flujo por borde, nuevamente usando el teorema de Robbins en orientaciones totalmente cíclicas, ver Teorema 2 de Kochol, Martin (2002), "Polinomios asociados con flujos en ninguna parte-cero", Journal of Combinatorial Theory , Serie B, 84 (2): 260-269, doi : 10.1006 / jctb.2001.2081 , MR 1889258
- ^ F. Jaeger, Flujos y teoremas de coloración generalizados en gráficos, J. Comb. Conjunto de teoría. B, 26 (1979), 205-216.
- ^ PD Seymour, Nowhere-zero 6-flow, J. Comb. Theory Ser B, 30 (1981), 130-135.
- ^ [1] , Open Problem Garden.
- ^ [2] , Open Problem Garden.
- ^ [3] , Open Problem Garden.
Otras lecturas
- Zhang, Cun-Quan (1997). Flujos enteros y cubiertas de ciclos de gráficos . Serie de Matemáticas Puras y Aplicadas de Chapman & Hall / CRC. Marcel Dekker, Inc. ISBN 9780824797904. LCCN 96037152 .
- Zhang, Cun-Quan (2012). Circuito de doble cubierta de gráficos . Prensa de la Universidad de Cambridge. ISBN 978-0-5212-8235-2.
- Jensen, TR; Toft, B. (1995). "13 Orientaciones y Flujos". Problemas de coloración de gráficos . Wiley-Interscience Serires en Matemática Discreta y Optimización. págs. 209 –219.
- Jacobsen, Jesper Lykke; Salas, Jesús (2013). "¿Es la conjetura de los cinco flujos casi falsa?". Revista de teoría combinatoria . Serie B. 103 (4): 532–565. arXiv : 1009.4062 . doi : 10.1016 / j.jctb.2013.06.001 . Señor 3071381 .