Flujo cero hacia ninguna parte

Concepto en la teoría de grafos

En teoría de grafos , un flujo cero en ninguna parte o flujo NZ es un flujo de red que no tiene cero en ninguna parte. Está íntimamente conectado (por dualidad) con la coloración de grafos planares .

Definiciones

Sea G = ( V , E ) un dígrafo y sea M un grupo abeliano . Una función φ : 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 que salen de v y δ ⁻ ( v ) denota el conjunto de aristas que entran en v . A veces, esta condición se denomina ley de Kirchhoff .

Si φ ( e ) ≠ 0 para cada e ∈ E , llamamos a φ un flujo sin cero, un flujo M o un flujo NZ. Si k es un entero y 0 < | φ ( e )| < k entonces φ es un flujo k . ^[1]

Otras nociones

Sea G = ( V , E ) un grafo 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 grafo G tiene un flujo M si y solo si tiene un flujo | M |. En consecuencia, existe un flujo si y solo si existe un flujo k . ^[1] En consecuencia, si G admite un flujo k , entonces admite un flujo h donde . ${\displaystyle \mathbb {Z} _{k}}$ ${\displaystyle h\geq k}$

• Independencia de la orientación. Modifique un flujo cero en ninguna parte φ en un grafo G eligiendo una arista e , invirtiéndola 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 cero en ninguna parte o un flujo k cero en ninguna parte es independiente de la orientación del grafo. Por lo tanto, se dice que un grafo no dirigido G tiene un flujo M cero en ninguna parte o un flujo k cero en ninguna parte si alguna (y por lo tanto cada) orientación de G tiene dicho flujo.

Polinomio de flujo

Sea el número de flujos M en G. Satisface la fórmula de deleció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 es el orden del grupo M . Llamamos al 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 un número igual de flujos NZ. 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 de coloración del flujo

Gráficos planares sin puentes

Existe una dualidad entre las coloraciones de k -caras y los k -flujos para grafos planares sin puentes . Para ver esto, sea G un grafo planar sin puentes dirigido con una coloración de k -caras adecuada 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 la arista 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 colores diferentes.

Por lo tanto, si G y G* son grafos duales planos y G* es k -coloreable (existe una coloración de las caras de G ), entonces G tiene un flujo k NZ . Usando inducción sobre | E ( G )| Tutte demostró que la inversa también es cierta. Esto se puede expresar de manera concisa como: ^[1]

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

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

Gráficos generales

La dualidad también es válida para los flujos M generales:

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

• Define 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 una coloración de cara | E ( G )| si y solo si es un flujo NZ M (directo). ${\displaystyle \phi _{c}}$

La dualidad se obtiene combinando los dos últimos puntos. Podemos especializarnos para obtener los resultados similares para los flujos k discutidos anteriormente. Dada esta dualidad entre flujos NZ y coloraciones, y dado que podemos definir flujos NZ para grafos arbitrarios (no solo planos), podemos usar esto para extender las coloraciones de caras a grafos no planos. ^[1] ${\displaystyle M=\mathbb {Z} _{k}}$

Aplicaciones

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

• Sea el grupo Klein-4 . Entonces, un grafo cúbico tiene un flujo K si y solo si es coloreable en 3 aristas . Como corolario, un grafo cúbico que es coloreable en 3 aristas es coloreable en 4 caras. ^[1] ${\displaystyle K=\mathbb {Z} _{2}\times \mathbb {Z} _{2}}$

• Un grafo es coloreable de 4 caras si y solo si permite un flujo NZ de 4 (ver Teorema de los cuatro colores ). El grafo de Petersen no tiene un flujo NZ de 4, y esto condujo 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 grado par. Por el primer punto, el grafo dual G * es coloreable en 2 y, por lo tanto, bipartito y cúbico planar. Por lo tanto, G * tiene un flujo NZ de 3 caras 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 una arista de bucle tiene una coloración de vértice adecuada, ningún gráfico con un puente puede tener un flujo NZ M para ningún 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 dea-flujos

Problema sin resolver en matemáticas :

¿Todo grafo sin puente tiene un flujo 5 con cero en ninguna parte? ¿Todo grafo sin puente que no tiene como menor al grafo de Petersen tiene un flujo 4 con cero en ninguna parte?

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

Surgen preguntas interesantes cuando se intenta encontrar flujos k nulos para valores pequeños de k . Se han demostrado las siguientes:

Teorema de los 4 flujos de Jaeger. Todo grafo con 4 aristas conexas tiene un 4 flujo. ^[4]

Teorema de los 6 flujos de Seymour . Todo grafo sin puente tiene un flujo de 6 flujos. ^[5]

Conjeturas de 3 flujos, 4 flujos y 5 flujos

A partir de 2019, los siguientes problemas se encuentran actualmente sin resolver (debido a Tutte ):

Conjetura de flujo tridimensional. Todo grafo con cuatro aristas conectadas tiene un flujo tridimensional que no tiene ningún punto de origen. ^[6]

Conjetura de 4 flujos. Todo grafo sin puente que no tenga como menor el grafo de Petersen tiene un 4 flujo de cero absoluto. ^[7]

Conjetura del 5-flujo. Todo grafo sin puente tiene un 5-flujo que no tiene ningún punto de origen. ^[8]

La conjetura inversa de los 4 flujos no se cumple, ya que el grafo completo K ₁₁ contiene un grafo de Petersen y un 4 flujo. ^[1] Para grafos cúbicos sin puentes y sin menor de Petersen, los 4 flujos existen 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]

Véase también

• Espacio para bicicletas
• Conjetura de doble cobertura cíclica
• Teorema de los cuatro colores
• Coloración de gráficos
• Coloración de bordes
• Polinomio de Tutte

Referencias

1. Diestel, Reinhard (30 de junio de 2017). Teoría de grafos . Springer. ISBN 9783662536216.OCLC 1048203362  .
2. Tutte, WT (1954). "Una contribución a la teoría de polinomios cromáticos". Revista Canadiense de Matemáticas . 6 : 80–91. doi :10.4153/CJM-1954-010-9.
3. Para un resultado más sólido sobre la enumeración de flujos con un límite en la cantidad máxima de flujo por arista, nuevamente usando el teorema de Robbins sobre orientaciones totalmente cíclicas, consulte el Teorema 2 de Kochol, Martin (2002), "Polynomials associate with nowhere-zero flow", 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 grafos, J. Comb. Theory Set. B, 26 (1979), 205–216.
5. PD Seymour, Flujos de 6 en ninguna parte y cero, J. Comb. Theory 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.

Lectura adicional

• Zhang, Cun-Quan (1997). Flujos de enteros y coberturas cíclicas de gráficos . Chapman & Hall/CRC Pure and Applied Mathematics Series. Marcel Dekker, Inc. ISBN 9780824797904. Número de serie LCCN  96037152.
• Zhang, Cun-Quan (2012). Circuito de doble cubierta de gráficos . Cambridge University Press. 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ática discreta 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?". Journal of Combinatorial Theory . Serie B. 103 (4): 532–565. arXiv : 1009.4062 . doi :10.1016/j.jctb.2013.06.001. MR  3071381. S2CID  41483928.