stringtranslate.com

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 .

Definiciones

Sea G = ( V , E ) un dígrafo y sea M un grupo abeliano . Una función φ : EM es una M -circulación si para cada vértice vV

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 eE , 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:

Propiedades

Polinomio de flujo

Sea el número de flujos M en G. Satisface la fórmula de deleción-contracción : [1]

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 .

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

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

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 ) = xy . 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]

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:

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]

Aplicaciones

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?

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 11 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

Referencias

  1. ^ abcdefghij 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
  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