Factorización de gráficos
En la teoría de grafos , un factor de un gráfico G es un subgrafo generador , es decir, un subgrafo que tiene el mismo conjunto de vértices que G. Un k -factor de un gráfico es un k - subgrafo regular de expansión, y una k -factorización divide los bordes del gráfico en k -factores disjuntos . Se dice que un grafo G es k -factorizable si admite una k -factorización. En particular, un factor de 1 es una combinación perfecta y una factorización de 1 de a k- el gráfico regular es un borde que colorea con k colores. Un factor de 2 es una colección de ciclos que abarca todos los vértices del gráfico.
Si un gráfico se puede factorizar en 1 (es decir, tiene una factorización en 1), entonces tiene que ser un gráfico regular . Sin embargo, no todos los gráficos regulares son factorizables en 1. Un gráfico k -regular es factorizable en 1 si tiene un índice cromático k ; ejemplos de tales gráficos incluyen:
Sin embargo, también hay gráficos k -regulares que tienen un índice cromático k + 1, y estos gráficos no son factorizables en 1; ejemplos de tales gráficos incluyen:
Una factorización de 1 de un gráfico completo corresponde a emparejamientos en un torneo de todos contra todos . La factorización en 1 de gráficos completos es un caso especial del teorema de Baranyai sobre la factorización en 1 de hipergrafías completas .
Un método para construir una factorización en 1 de un gráfico completo en un número par de vértices consiste en colocar todos los vértices menos uno en un círculo, formando un polígono regular , con el vértice restante en el centro del círculo. Con esta disposición de vértices, una forma de construir un factor 1 del gráfico es elegir una arista e desde el centro hasta un solo vértice de polígono junto con todas las aristas posibles que se encuentran en líneas perpendiculares a e . Los factores de 1 que se pueden construir de esta manera forman una factorización de 1 del gráfico.
El número de factorizaciones distintas de 1 de K 2 , K 4 , K 6 , K 8 , ... es 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... OEIS : A000438 .
