Factorización de gráficos
En la teoría de grafos , un factor de de un gráfico G es un subgrafo spanning , es decir, un subgrafo que tiene el mismo conjunto de vértices como G . A k -factor de un gráfico es una que abarca k - regular de subgrafo, y una k -factorization particiones de los bordes de la gráfica en disjuntos k factores g. Se dice que una gráfica G es k -factorizable si admite una k -factorización. En particular, un factor 1 es una coincidencia perfecta y una factorización 1 de un k- el gráfico regular es una coloración de bordes con k colores. Un factor 2 es una colección de ciclos que abarca todos los vértices del gráfico.
Si una gráfica se puede factorizar en 1 (es decir, tiene una factorización en 1), entonces tiene que ser una gráfica regular . Sin embargo, no todos los gráficos regulares son de 1 factor. Un grafo k -regular es 1-factorizable si tiene un índice cromático k ; ejemplos de tales gráficos incluyen:
Sin embargo, también hay k- gráficos regulares que tienen un índice cromático k + 1, y estos gráficos no son 1-factorizables; ejemplos de tales gráficos incluyen:
Una factorización 1 de un gráfico completo corresponde a emparejamientos en un torneo de todos contra todos . El 1-factorización de grafos completos es un caso especial del teorema de Baranyai en relación con la 1-factorización de completas hipergrafos .
Un método para construir una factorización 1 de un gráfico completo en un número par de vértices implica 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 a un único vértice poligonal junto con todas las aristas posibles que se encuentran en líneas perpendiculares a e . Los factores 1 que se pueden construir de esta manera forman una factorización 1 del gráfico.
El número de 1-factorizaciones distintas de K 2 , K 4 , K 6 , K 8 , ... es 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... OEIS : A000438 .
