Flujo cero en ninguna parte

Concepto en teoría de grafos

En teoría de grafos , un flujo en ninguna parte cero o flujo de Nueva Zelanda es un flujo de red que no es cero en ninguna parte. Está íntimamente conectado (por dualidad) con 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

${\displaystyle \sum _{e\in \delta ^{+}(v)}\varphi (e)=\sum _{e\in \delta ^{-}(v)}\varphi (e),}$

donde δ ⁺ ( v ) denota el conjunto de aristas fuera de v y δ ⁻ ( v ) denota el conjunto de aristas en v . En ocasiones, esta condición se denomina ley de Kirchhoff .

Si φ ( e ) ≠ 0 para cada e ∈ E , llamamos a φ un flujo en ninguna parte cero, un flujo M o un flujo NZ. Si k es un número entero y 0 < | φ ( mi )| < k entonces φ es un k -flujo. ^[1]

Otras nociones

Sea G = ( V , E ) un gráfico no dirigido . Una orientación de E es un flujo k modular si para cada vértice  v  ∈  V tenemos:

${\displaystyle |\delta ^{+}(v)|\equiv |\delta ^{-}(v)|{\bmod {k}}.}$

Propiedades

• El conjunto de M -flujos 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 sólo si tiene un | M |-flujo. Como consecuencia, existe un flujo si y sólo si existe un k -flujo. ^[1] Como consecuencia, si G admite un flujo k , entonces admite un flujo h donde . ${\displaystyle \mathbb {Z} _{k}}$ ${\displaystyle h\geq k}$

• 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. Además, si φ era originalmente un k -flujo, entonces el φ resultante también es un k -flujo. Por lo tanto, la existencia de un flujo M en ninguna parte cero o un flujo k en ninguna parte cero es independiente de la orientación del gráfico. Por lo tanto, se dice que un gráfico no dirigido G tiene un flujo M en ninguna parte cero o un flujo k en ninguna parte cero si alguna (y por tanto cada) orientación de G tiene tal flujo.

Polinomio de flujo

Sea el número de M -flujos en G . Satisface la fórmula de eliminación-contracción : ^[1] ${\displaystyle N_{M}(G)}$

${\displaystyle N_{M}(G)=N_{M}(G/e)-N_{M}(G\setminus e).}$

Combinando esto con la inducción podemos demostrar que es un polinomio en donde está el orden del grupo M. Llamamos polinomio de flujo de G y grupo abeliano M. ${\displaystyle N_{M}(G)}$ ${\displaystyle |M|-1}$ ${\displaystyle |M|}$ ${\displaystyle N_{M}(G)}$

Lo anterior implica que dos grupos de igual orden tienen el mismo número de flujos en Nueva Zelanda. El orden es el único parámetro de grupo que importa, no la estructura de M . En particular si ${\displaystyle N_{M_{1}}(G)=N_{M_{2}}(G)}$ ${\displaystyle |M_{1}|=|M_{2}|.}$

Los resultados anteriores fueron demostrados por Tutte en 1953 cuando estudiaba el polinomio de Tutte , una generalización del polinomio de flujo. ^[2]

Dualidad fluir-colorear

Gráficos planos sin puente

Existe una dualidad entre k -coloraciones de caras y k -flujos para gráficos planos sin puentes . Para ver esto, sea G un gráfico plano dirigido sin puentes con una k adecuada coloración de caras con colores. Construya un mapa. ${\displaystyle \{0,1,\ldots ,k-1\}.}$

${\displaystyle \phi :E(G)\to \{-(k-1),\ldots ,-1,0,1,\ldots ,k-1\}}$

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 flujo k (NZ) ya que x e y deben ser de diferentes colores.

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 | mi ( sol )| Tutte demostró que lo contrario también es cierto. Esto se puede expresar de manera concisa como: ^[1]

${\displaystyle \chi (G^{*})=\phi (G),}$

donde el RHS es el número de flujo , el k más pequeño para el cual G permite un k -flujo.

Gráficos generales

La dualidad también es cierta para los flujos M generales:

• Sea la función de coloración de caras con valores en M . ${\displaystyle c}$

• Defina donde r ₁ es la cara a la izquierda de e y r ₂ está a la derecha. ${\displaystyle \phi _{c}(e)=c(r_{1})-c(r_{2})}$

• Para cada M -circulación existe una función colorante c tal que (probado por inducción). ${\displaystyle \phi }$ ${\displaystyle \phi =\phi _{c}}$

• c es un | E ( G )| -coloración de caras si y solo si es un flujo NZ M (sencillo). ${\displaystyle \phi _{c}}$

La dualidad surge al combinar los dos últimos puntos. Podemos especializarnos para obtener resultados similares para k -flujos discutidos anteriormente. Dada esta dualidad entre flujos y coloraciones de Nueva Zelanda, y dado que podemos definir flujos de Nueva Zelanda para gráficos arbitrarios (no solo planos), podemos usar esto para extender los colores de caras a gráficos no planos. ^[1] ${\displaystyle M=\mathbb {Z} _{k}}$

Aplicaciones

• G es coloreable en 2 caras si y solo si cada vértice tiene un grado par (considere los 2 flujos de Nueva Zelanda). ^[1]

• Sea el grupo Klein-4 . Entonces un gráfico cúbico tiene un flujo K si y sólo si es coloreable en 3 aristas . Como corolario, un gráfico cúbico que se puede colorear en 3 aristas también se puede colorear en 4 caras. ^[1] ${\displaystyle K=\mathbb {Z} _{2}\times \mathbb {Z} _{2}}$

• Un gráfico se puede colorear en 4 caras si y sólo si permite un flujo de 4 caras en Nueva Zelanda (ver Teorema de los cuatro colores ). El gráfico de Petersen no tiene un flujo de 4 en Nueva Zelanda, y esto llevó a la conjetura de los 4 flujos (ver más abajo).

• Si G es una triangulación, entonces G es coloreable en 3 (vértices) si y solo si cada vértice tiene un grado par. En el primer punto, el gráfico dual G * tiene dos colores y, por lo tanto, es 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 G sea coloreable en 3 vértices. ^[1]

• Así como ningún gráfico con un borde de bucle tiene una coloración de vértice adecuada, ningún gráfico con un puente puede tener un flujo NZ M para cualquier grupo M. Por el contrario, todo gráfico sin puente tiene un flujo NZ (una forma del teorema de Robbins ). ^[3] ${\displaystyle \mathbb {Z} }$

Existencia de k -flujos

Problema no resuelto en matemáticas :

¿Todo gráfico sin puente tiene un flujo 5 en ninguna parte cero? ¿Cada gráfico sin puente que no tiene el gráfico de Petersen como menor tiene un flujo 4 en ninguna parte cero?

(más problemas sin resolver en matemáticas)

Surgen preguntas interesantes cuando se intenta encontrar flujos k en ninguna parte cero para valores pequeños de k . Se ha demostrado lo siguiente:

Teorema de los 4 flujos de Jaeger. Cada gráfico conectado con 4 aristas tiene un flujo de 4. ^[4]

Teorema de los 6 flujos de Seymour . Cada gráfico sin puente tiene un flujo de 6. ^[5]

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 con 4 aristas tiene un flujo 3 sin cero. ^[6]

Conjetura de los 4 flujos. Cada gráfico sin puente que no tiene 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 sin cero. ^[8]

Lo contrario de la conjetura de los 4 flujos no se cumple ya que el gráfico completo K ₁₁ contiene un gráfico de Petersen y un gráfico de 4 flujos. ^[1] Para gráficos cúbicos sin puente sin menor de Petersen, existen 4 flujos según el teorema de snark (Seymour, et al 1998, aún no publicado). El teorema de los cuatro colores equivale a la afirmación de que ningún snark es plano. ^[1]

Ver también

• espacio de ciclo
• Conjetura de la doble cobertura del ciclo
• Teorema de los cuatro colores
• Coloración de gráficos
• Coloración de bordes
• polinomio tutte

Referencias

1. Diestel, Reinhard (30 de junio de 2017). Teoría de grafos . ISBN 9783662536216. OCLC  1048203362.
2. Tutte, peso (1954). "Una contribución a la teoría de los polinomios cromáticos". Revista Canadiense de Matemáticas . 6 : 80–91. doi :10.4153/CJM-1954-010-9.
3. Para obtener un resultado más sólido sobre la enumeración de flujos con un límite en la cantidad máxima de flujo por borde, utilizando nuevamente el teorema de Robbins en orientaciones totalmente cíclicas, consulte el Teorema 2 de Kochol, Martin (2002), "Polinomios asociados con cero en ninguna parte flows", Journal of Combinatorial Theory , Serie B, 84 (2): 260–269, doi : 10.1006/jctb.2001.2081 , MR  1889258 ${\displaystyle \mathbb {Z} }$
4. F. Jaeger, Flujos y teoremas de coloración generalizados en gráficos, J. Comb. Conjunto de teoría. B, 26 (1979), 205–216.
5. PD Seymour, En ninguna parte-cero 6 flujos, J. Comb. Teoría Ser B, 30 (1981), 130-135.
6. [1], Jardín de problemas abiertos.
7. [2], Jardín de problemas abiertos.
8. [3], Jardín de problemas abiertos.

Otras lecturas

• Zhang, Cun-Quan (1997). Flujos enteros y cubiertas de ciclos de gráficos . Serie Chapman & Hall/CRC Matemática pura y aplicada. Marcel Dekker, Inc. ISBN 9780824797904. LCCN  96037152.
• Zhang, Cun-Quan (2012). Circuito Doble Portada 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 . Serie Wiley-Interscience en Matemáticas Discretas y Optimización. págs. 209-219. ISBN 9780471028659.
• Jacobsen, Jesper Lykke; Salas, Jesús (2013). "¿Es casi falsa la conjetura de los cinco flujos?". 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. S2CID  41483928.