Hispanopedia Wiki
Articulo de referencia

flujo cero en ninguna parte

En teoría de grafos , un flujo sin ceros o flujo NZ es un flujo de red que no es cero en ningún punto. Está íntimamente relacionado (por dualidad) con la coloración de grafos pl...

Hispanopedia WikiContenido en espanolLectura gratuita

En teoría de grafos , un flujo sin ceros o flujo NZ es un flujo de red que no es cero en ningún punto. Está íntimamente relacionado (por dualidad) con la coloración de grafos planares .

Definiciones

Sea G = ( V , E ) un digrafo y sea M un grupo abeliano . Una aplicación φ : E → M es una M -circulación si para cada vértice v ∈ V

∑mi∈δ+(v)φ(mi)=∑mi∈δ−(v)φ(mi),{\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 conoce como la ley de Kirchhoff .

Si φ ( e ) ≠ 0 para todo e ∈ E , llamamos a φ un flujo sin ceros en ninguna parte, un flujo M o un flujo NZ. Si k es un entero y 0 < | φ ( e )| < k entonces φ es un flujo k . [ 1 ]

Otras ideas

Sea G = ( V , E ) un grafo no dirigido . Una orientación de E es un k - flujo modular si para cada vértice v ∈ V se cumple:   

|δ+(v)|≡|δ−(v)|modk.{\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 una arista puede ser igual a 0.
  • (Tutte 1950) Un grafo G tiene un flujo M si y solo si tiene un flujo | M |. Como consecuencia, unZk{\displaystyle \mathbb {Z} _ {k}}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 dondeh≥k{\displaystyle h\geq k}.
  • Independencia de la orientación. Modifique un flujo nulo φ en un grafo G eligiendo una arista e , invirtiéndola y luego reemplazando φ ( e ) por −φ ( e ) . Tras este ajuste, φ sigue siendo un flujo nulo. Además, si φ era originalmente un flujo k , el φ resultante también lo es . Por lo tanto, la existencia de un flujo M nulo o un flujo k nulo es independiente de la orientación del grafo. Así, se dice que un grafo no dirigido G tiene un flujo M nulo o un flujo k nulo si alguna (y por ende , todas) las orientaciones de G poseen dicho flujo.

polinomio de flujo

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

norteMETRO(GRAMO)=norteMETRO(GRAMO/mi)−norteMETRO(GRAMO∖mi).{\displaystyle N_{M}(G)=N_{M}(G/e)-N_{M}(G\setminus e).}

Combinando esto con la inducción podemos demostrarnorteMETRO(GRAMO){\displaystyle N_{M}(G)}es un polinomio en|METRO|−1{\displaystyle |M|-1}dónde|METRO|{\displaystyle |M|}es el orden del grupo M. Lo llamamosnorteMETRO(GRAMO){\displaystyle N_{M}(G)}el polinomio de flujo de G y del grupo abeliano M.

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 particularnorteMETRO1(GRAMO)=norteMETRO2(GRAMO){\displaystyle N_{M_{1}}(G)=N_{M_{2}}(G)}si|METRO1|=|METRO2|.{\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

Grafos planares sin puente

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 dirigido sin puentes con una coloración de k caras propia con colores{0,1,…,k−1}.{\displaystyle \{0,1,\ldots ,k-1\}.}Construye un mapa

ϕ:mi(GRAMO)→{−(k−1),…,−1,0,1,…,k−1}{\displaystyle \phi :E(G)\to \{-(k-1),\ldots ,-1,0,1,\ldots ,k-1\}}

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

Entonces, si G y G* son grafos duales planares y G* es k -coloreable (hay una coloración de las caras de G ), entonces G tiene un k -flujo NZ. Usando inducción sobre | E ( G )| Tutte demostró que lo contrario también es cierto. Esto se puede expresar concisamente como: [ 1 ]

χ(GRAMO∗)=ϕ(GRAMO),{\displaystyle \chi (G^{*})=\phi (G),}

donde el lado derecho 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:

  • Dejardo{\displaystyle c}Sea la función de coloración facial con valores en M.
  • Definirϕdo(mi)=do(r1)−do(r2){\displaystyle \phi _{c}(e)=c(r_{1})-c(r_{2})}donde r 1 es la cara a la izquierda de e y r 2 es a la derecha.
  • Para cada M -circulaciónϕ{\displaystyle \phi }existe una función de coloración c tal queϕ=ϕdo{\displaystyle \phi =\phi _ {c}}(demostrado por inducción).
  • c es un coloreado facial | E ( G )| si y solo siϕdo{\displaystyle \phi _{c}}es un flujo M de Nueva Zelanda (sencillo).

La dualidad se deduce al combinar los dos últimos puntos. Podemos especializarnos enMETRO=Zk{\displaystyle M=\mathbb {Z} _ {k}}para obtener resultados similares para los k -flujos discutidos anteriormente. Dada esta dualidad entre flujos NZ y coloraciones, y puesto que podemos definir flujos NZ para grafos arbitrarios (no solo planares), podemos usar esto para extender las coloraciones de caras a grafos no planares. [ 1 ]

Aplicaciones

  • G es 2-coloreable por caras si y solo si cada vértice tiene grado par (considere los 2-flujos NZ). [ 1 ]
  • DejarK=Z2×Z2{\displaystyle K=\mathbb {Z} _{2}\times \mathbb {Z} _{2}}Sea el grupo Klein-4 . Entonces, un grafo cúbico tiene un K -flujo si y solo si es coloreable por 3 aristas . Como corolario, un grafo cúbico que es coloreable por 3 aristas es coloreable por 4 caras. [ 1 ]
  • Un grafo es coloreable con 4 caras si y solo si permite un flujo NZ de 4 caras (véase el teorema de los cuatro colores ). El grafo de Petersen no tiene un flujo NZ de 4 caras, lo que dio lugar a la conjetura del flujo de 4 caras (véase más abajo).
  • Si G es una triangulación, entonces G es 3-coloreable (en vértices) si y solo si cada vértice tiene grado par. Según el primer punto, el grafo dual G * es 2-coloreable y, por lo tanto, bipartito y cúbico planar. Así pues, G * tiene un 3-flujo NZ y, por lo tanto, es 3-coloreable en caras, lo que hace que G sea 3-coloreable en vértices. [ 1 ]
  • Así como ningún grafo con una arista de bucle tiene una coloración de vértice adecuada, ningún grafo con un puente puede tener un flujo NZ M para ningún grupo M. Por el contrario, todo grafo sin puente tiene un NZZ{\displaystyle \mathbb {Z} }-flujo (una forma del teorema de Robbins ). [ 3 ]

Existencia de flujos k

Problema sin resolver en matemáticas
¿Tiene todo grafo sin puentes un flujo de 5 elementos que no sea cero en ningún lugar? ¿Tiene todo grafo sin puentes que no tenga el grafo de Petersen como menor un flujo de 4 elementos que no sea cero en ningún lugar?
Más problemas sin resolver en matemáticas

Surgen preguntas interesantes al intentar encontrar flujos k nulos para valores pequeños de k . Se han demostrado los siguientes:

Teorema del 4-flujo de Jaeger. Todo grafo 4 -conectado por aristas tiene un 4-flujo. [ 4 ]
Teorema del flujo 6 de Seymour . Todo grafo sin puentes tiene un flujo 6. [ 5 ]

Conjeturas de flujo 3, flujo 4 y flujo 5

A fecha de 2019, los siguientes casos permanecen sin resolver (debido a Tutte ):

Conjetura del flujo 3. Todo grafo 4-arista-conectado tiene un flujo 3-nulo. [ 6 ]
Conjetura del 4-flujo. Todo grafo sin puentes que no tenga el grafo de Petersen como menor tiene un 4-flujo sin ceros en ninguna parte. [ 7 ]
Conjetura del flujo 5. Todo grafo sin puentes tiene un flujo 5 que no es cero en ninguna parte. [ 8 ]

La recíproca de la conjetura del 4-flujo no se cumple, ya que el grafo completo K 11 contiene un grafo de Petersen y un 4-flujo. [ 1 ] Para grafos cúbicos sin puentes y sin menor de Petersen, existen 4-flujos según el teorema del 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 planar. [ 1 ]

Véase también

Referencias

  1. 1 2 3 4 5 6 7 8 9 10 Diestel, Reinhard (30 de junio de 2017). Teoría de grafos . Springer. ISBN 9783662536216OCLC 1048203362 .​ 
  2. ↑ Tutte, WT (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 un resultado más sólido sobre la enumeración deZ{\displaystyle \mathbb {Z} }-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, véase el Teorema 2 de Kochol, Martin (2002), "Polynomials associated with nowhere-zero flows", Journal of Combinatorial Theory , Serie B, 84 (2): 260– 269, doi : 10.1006/jctb.2001.2081 , MR 1889258 
  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 6-cero en ninguna parte, J. Comb. Theory Ser B, 30 (1981), 130–135.
  6. ↑, Jardín de Problemas Abiertos.
  7. ↑, Jardín de Problemas Abiertos.
  8. ↑, Jardín de Problemas Abiertos.

Lecturas adicionales

  • Zhang, Cun-Quan (1997). Flujos enteros y recubrimientos cíclicos de grafos . Chapman & Hall/CRC Pure and Applied Mathematics Series. Marcel Dekker, Inc. ISBN 9780824797904. LCCN 96037152 . 
  • Zhang, Cun-Quan (2012). Circuit Double Cover of Graphs . Cambridge University Press. ISBN 978-0-5212-8235-2.
  • Jensen, TR; Toft, B. (1995). "13 Orientaciones y flujos". Problemas de coloración de grafos . Serie Wiley-Interscience en matemáticas discretas y optimización. pp. 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 .