Hispanopedia Wiki
Articulo de referencia

factorización de grafos

1-factorización del grafo de Desargues : cada clase de color es un 1-factor . El grafo de Petersen se puede particionar en un factor de 1 (rojo) y un factor de 2 (azul). Sin emb...

Hispanopedia WikiContenido en espanolLectura gratuita
1-factorización del grafo de Desargues : cada clase de color es un 1-factor .
El grafo de Petersen se puede particionar en un factor de 1 (rojo) y un factor de 2 (azul). Sin embargo, el grafo no es 1-factorizable .
Problema sin resolver en matemáticas
Conjetura: Si n es impar y k  ≥ n , entonces G es 1-factorizable. Si n es par y k ≥ n − 1, entonces G es 1-factorizable.     
Más problemas sin resolver en matemáticas

En teoría de grafos , un factor de un grafo G es un subgrafo generador , es decir, un subgrafo que tiene el mismo conjunto de vértices que G. Un k -factor de un grafo es un subgrafo generador k - regular , y una k- factorización divide las aristas del grafo en k -factores disjuntos. Se dice que un grafo G es k- factorizable si admite una k- factorización. En particular, un 1-factor es un emparejamiento perfecto , y una 1-factorización de un grafo k -regular es una coloración de aristas propia con k colores. Un 2-factor es una colección de ciclos disjuntos que genera todos los vértices del grafo.

1-factorización

Si un grafo es 1-factorizable, entonces debe ser un grafo regular . Sin embargo, no todos los grafos regulares son 1-factorizables. Un grafo k -regular es 1-factorizable si tiene índice cromático k ; ejemplos de tales grafos incluyen:

Sin embargo, también existen grafos k -regulares con índice cromático k  +  1, y estos grafos no son 1-factorizables; ejemplos de tales grafos incluyen:

Gráficos completos

1-factorización de K 8 en la que cada 1-factor consiste en una arista desde el centro hasta un vértice de un heptágono junto con todas las posibles aristas perpendiculares.

Una 1-factorización de un grafo completo corresponde a emparejamientos en un torneo round-robin . La 1-factorización de grafos completos es un caso especial del teorema de Baranyai sobre la 1-factorización de hipergrafos completos .

Un método para construir una 1-factorización de un grafo completo con un número par de vértices consiste en colocar todos los vértices, excepto uno, en un polígono regular , con el vértice restante en el centro. Con esta disposición de vértices, una forma de construir un 1-factor del grafo es elegir una arista e desde el centro hasta un único vértice del polígono, junto con todas las aristas posibles que se encuentran sobre líneas perpendiculares a e . Los 1-factores que se pueden construir de esta manera forman una 1-factorización del grafo.

El número de 1-factorizaciones distintas de K 2 , K 4 , K 6 , K 8 , ... es 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... (secuencia A000438 en el OEIS ) .

Conjetura de 1-factorización

Sea G un grafo k -regular con 2 n nodos. Si k es suficientemente grande, se sabe que G debe ser 1-factorizable:

  • Si k  =  2 n − 1, entonces G es el grafo completo K 2 n , y por lo tanto 1-factorizable (ver arriba ).  
  • Si k  =  2 n − 2, entonces G se puede construir quitando un emparejamiento perfecto de K 2 n . Nuevamente, G es 1-factorizable.  
  • Chetwynd y Hilton (1985) muestran que si k  ≥  12 n /7, entonces G es 1-factorizable.

La conjetura de 1-factorización [ 3 ] es una conjetura de larga data que afirma que k  ≈ n es suficiente. En términos precisos, la conjetura es: 

  • Si n es impar y k  ≥ n , entonces G es 1-factorizable. Si n es par y k ≥ n − 1, entonces G es 1-factorizable.     

La conjetura de sobrellenado implica la conjetura de 1-factorización. La conjetura fue confirmada por Csaba, Kühn, Lo, Osthus y Treglown para n suficientemente grande . [ 4 ]

1-factorización perfecta

Un par perfecto de una 1-factorización es un par de 1-factores cuya unión induce un ciclo hamiltoniano .

Una factorización perfecta de un grafo (P1F) es aquella que tiene la propiedad de que cada par de factores es un par perfecto. No se debe confundir una factorización perfecta con un emparejamiento perfecto (también llamado factor).

En 1964, Anton Kotzig conjeturó que todo grafo completo K 2 n donde n ≥ 2 tiene una 1-factorización perfecta. Hasta ahora, se sabe que los siguientes grafos tienen una 1-factorización perfecta: [ 5 ]

  • la familia infinita de grafos completos K 2 p donde p es un primo impar (por Anderson y también Nakamura, independientemente),
  • la familia infinita de grafos completos K p +1 donde p es un primo impar,
  • y resultados adicionales esporádicos, incluyendo K 2 n donde 2 n ∈ {16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792}. Algunos resultados más recientes se recopilan aquí .

Si el grafo completo K n +1 tiene una 1-factorización perfecta, entonces el grafo bipartito completo K n , n también tiene una 1-factorización perfecta. [ 6 ]

2-factorización

Si un grafo es 2-factorizable, entonces debe ser 2k - regular para algún entero k . Julius Petersen demostró en 1891 que esta condición necesaria también es suficiente: cualquier grafo 2k - regular es 2-factorizable . [ 7 ]

Si un grafo conexo es 2k - regular y tiene un número par de aristas, también puede ser k- factorizado, eligiendo cada uno de los dos factores como un subconjunto alterno de las aristas de un recorrido euleriano . [ 8 ] Esto se aplica solo a grafos conexos; los contraejemplos desconectados incluyen uniones disjuntas de ciclos impares o de copias de K2k + 1 .

El problema de Oberwolfach trata sobre la existencia de 2-factorizaciones de grafos completos en subgrafos isomorfos . Se pregunta para qué subgrafos esto es posible. Esto se sabe cuando el subgrafo es conexo (en cuyo caso es un ciclo hamiltoniano y este caso particular es el problema de la descomposición hamiltoniana ), pero el caso general permanece abierto .

Referencias

  1. ^ Harary (1969) , Teorema 9.2, pág. 85. Diestel (2005) , Corolario 2.1.3, p. 37.
  2. ^ Harary (1969) , Teorema 9.1, pág. 85.
  3. ↑ Chetwynd y Hilton (1985) . Niessen (1994) . Perkovic y Reed (1997) . West .
  4. ↑ Csaba, Béla; Kühn, Daniela; Lo, Allan; Osthus, Deryk; Treglown, Andrew (junio de 2016), "Prueba de las conjeturas de 1-factorización y descomposición hamiltoniana", Memoirs of the American Mathematical Society , doi : 10.1090/memo/1154
  5. ↑ Wallis, WD (1997), "16. Factorizaciones perfectas", One-factorizations , Mathematics and Its Applications, vol. 390 (1.ª ed.), Springer US , p. 125, doi : 10.1007/978-1-4757-2564-3_16 , ISBN    978-0-7923-4323-3
  6. ↑ Bryant, Darryn; Maenhaut, Barbara M.; Wanless, Ian M. (mayo de 2002), "Una familia de factorizaciones perfectas de grafos bipartitos completos", Journal of Combinatorial Theory , A, 98 (2): 328–342 , doi : 10.1006/jcta.2001.3240 , ISSN 0097-3165 
  7. ↑ Petersen (1891) , §9, pág. 200. Harary (1969) , Teorema 9.9, pág. 90. Véase Diestel (2005) , Corolario 2.1.5, p. 39 para una prueba.
  8. ↑ Petersen (1891) , §6, pág. 198.

Bibliografía

  • Bondy, John Adrian ; Murty, USR (1976), Teoría de grafos con aplicaciones , North-Holland, ISBN 0-444-19451-7Archivado del original el 13 de abril de 2010 , consultado el 18 de diciembre de 2019., Sección 5.1: "Coincidencias".
  • Chetwynd, AG ; Hilton, AJW (1985), "Los grafos regulares de alto grado son 1-factorizables", Actas de la Sociedad Matemática de Londres , 50 (2): 193–206 , doi : 10.1112/plms/s3-50.2.193.
  • Diestel, Reinhard (2005), Teoría de grafos (3.ª  ed.), Springer , ISBN 3-540-26182-6, Capítulo 2: "Combinar, cubrir y empaquetar". Edición electrónica .
  • Harary, Frank (1969), Teoría de grafos , Addison-Wesley, ISBN 0-201-02787-9Capítulo 9: "Factorización".
  • "Un factorización" , Enciclopedia de Matemáticas , EMS Press, 2001 [1994]
  • Niessen, Thomas (1994), "Cómo encontrar subgrafos sobrecargados en grafos con un grado máximo grande", Matemáticas Aplicadas Discretas , 51 ( 1–2 ): 117–125 , doi : 10.1016/0166-218X(94)90101-5.
  • Perkovic, L.; Reed, B. (1997), "Coloración de aristas de grafos regulares de alto grado", Matemáticas Discretas , 165–166 : 567–578 , doi : 10.1016/S0012-365X(96)00202-6.
  • Petersen, Julius (1891), "Die Theorie der regulären graphs" (PDF) , Acta Mathematica , 15 : 193– 220, doi : 10.1007/BF02392606.
  • West, Douglas B. "Conjetura de 1-factorización (1985?)" . Problemas abiertos: teoría de grafos y combinatoria . Consultado el 9 de enero de 2010 .
  • Weisstein, Eric W. "Factor de grafos" . MathWorld .
  • Weisstein, Eric W. "Factor k" . MathWorld .
  • Weisstein, Eric W. "Grafo k-factorizable" . MathWorld .

Lecturas adicionales