Flujo cero hacia ninguna parte

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 .

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]

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}}.}$

• 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.

Sea el número de flujos M en G. Satisface la fórmula de deleción-contracción : ^[1]$Estilo de visualización 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 .$Estilo de visualización N_ {M}(G)}$${\displaystyle |M|-1}$${\estilo de visualización |M|}$$Estilo de visualización 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]

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 .

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 .${\estilo de visualización 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).${\estilo de visualización \phi}$${\displaystyle \phi =\phi _ {c}}$

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

• 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}}$

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]

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-flujo. Todo grafo sin puente que no tenga como menor al 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]

• 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

• 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.