Enumeración de gráficos

La lista completa de todos los árboles libres en 2, 3 y 4 vértices etiquetados: árbol con 2 vértices, árboles con 3 vértices y árboles con 4 vértices. ${\displaystyle 2^{2-2}=1}$ ${\displaystyle 3^{3-2}=3}$ ${\displaystyle 4^{4-2}=16}$

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

Problemas etiquetados versus no etiquetados

En algunos problemas de enumeración gráfica, se considera que los vértices del gráfico están etiquetados de tal manera que se pueden distinguir entre sí, mientras que en otros problemas se considera que cualquier permutación de los vértices forma el mismo gráfico, 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 problemas no etiquetados a problemas etiquetados: cada clase no etiquetada se considera como una clase de simetría de objetos etiquetados.

Fórmulas de enumeración exacta.

Algunos resultados importantes en esta área incluyen los siguientes.

• El número de gráficos no dirigidos simples de n -vértices etiquetados es 2 ^{n ( n  −1)/2} . ^[6]
• El número de gráficos dirigidos simples de n -vértices etiquetados es 2 ^{n ( n  −1 )} . ^[7]
• El número C _n de gráficos no dirigidos de n vértices conectados y etiquetados satisface la relación de recurrencia ^[8]

${\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 ^[9]

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

Base de datos de gráficos

Varios grupos de investigación han proporcionado una base de datos con capacidad de búsqueda que enumera gráficos con ciertas propiedades de tamaño pequeño. Por ejemplo

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

Referencias

1. Harary, Frank ; Palmer, Edgar M. (1973). Enumeración gráfica . Prensa académica . ISBN 0-12-324245-2.
2. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Matemáticas. 68 (1937), 145-254
3. "Cayley, Arthur (CLY838A)". Una base de datos de antiguos alumnos de Cambridge . Universidad de Cambridge.
4. La teoría de las distribuciones reducidas en grupos. American J. Matemáticas. 49 (1927), 433-455.
5. Harary y Palmer, pag. 1.
6. Harary y Palmer, pag. 3.
7. Harary y Palmer, pag. 5.
8. Harary y Palmer, pag. 7.
9. Harary, Frank ; Schwenk, Allen J. (1973), "El número de orugas" (PDF) , Matemáticas discretas , 6 (4): 359–365, doi :10.1016/0012-365x(73)90067-8, hdl : 2027.42/33977.