enumeración de grafos

En combinatoria , un área de las matemáticas , la enumeración de grafos describe una clase de problemas de enumeración combinatoria en los que se deben contar grafos no dirigidos o dirigidos de ciertos tipos, generalmente en función del número de vértices del grafo. ^{[ 1 ]} Estos problemas pueden resolverse de forma exacta (como un problema de enumeración algebraica ) o asintótica . Los pioneros en esta área de las matemáticas fueron George Pólya , ^{[ 2 ]} Arthur Cayley ^{[ 3 ]} y J. Howard Redfield . ^{[ 4 ]}

En algunos problemas de enumeración gráfica, los vértices del grafo se consideran etiquetados de tal manera que se distinguen entre sí, mientras que en otros problemas cualquier permutación de los vértices se considera que forma el mismo grafo, por lo que los vértices se consideran idénticos o sin etiquetar . En general, los problemas etiquetados tienden a ser más fáciles. ^{[ 5 ]} Al igual que con la enumeración combinatoria en general, el teorema de enumeración de Pólya es una herramienta importante para reducir los problemas sin etiquetar a problemas etiquetados: cada clase sin etiquetar se considera como una clase de simetría de objetos etiquetados.

El número de gráficos sin etiquetar con${\displaystyle n}$El número de vértices aún no se conoce en una solución de forma cerrada , ^{[ 6 ]} pero como casi todos los grafos son asimétricos, este número es asintótico a ^{[ 7 ].}$${\displaystyle {\frac {2^{\tbinom {n}{2}}}{n!}}.}$$

Algunos resultados importantes en esta área incluyen los siguientes.

• El número de grafos simples no dirigidos de n vértices etiquetados es 2 ^{n ( n −1)/2} . ^{[ 8 ]}
• El número de grafos dirigidos simples etiquetados de n vértices es 2 ^{n ( n −1)} . ^{[ 9 ]}
• El número C _n de grafos no dirigidos conexos etiquetados de n vértices satisface la relación de recurrencia ^{[ 10 ].}

${\displaystyle C_{n}=2^{n \choose 2}-{\frac {1}{n}}\sum _{k=1}^{n-1}k{n \choose k}2^{n-k \choose 2}C_{k}.}$

a partir de lo cual se puede calcular fácilmente, para n = 1, 2, 3, ..., que los valores para C _n son

1, 1, 4, 38, 728, 26704, 1866256, ... (secuencia A001187 en el OEIS )

• El número de árboles libres de n vértices etiquetados es n ^{n −2} ( fórmula de Cayley ).
• El número de orugas de n vértices sin etiquetar es ^{[ 11 ].}

${\displaystyle 2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.}$

Diversos grupos de investigación han proporcionado bases de datos consultables que enumeran gráficos con ciertas propiedades de tamaño reducido. Por ejemplo

• La Casa de los Gráficos
• Base de datos de grafos pequeños