Enumeración de gráficos

La lista completa de todos los árboles libres con 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 grafos describe una clase de problemas de enumeración combinatoria en los que se deben contar grafos dirigidos o no dirigidos de ciertos tipos, típicamente como una función del número de vértices del grafo. ^[1] Estos problemas se pueden resolver de forma exacta (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 y no etiquetados

En algunos problemas de enumeración gráfica, se considera que los vértices del grafo 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 grafo, por lo que los vértices se consideran idénticos o no etiquetados . En general, los problemas etiquetados tienden a ser más fáciles. ^[5] Al igual que con la enumeración combinatoria de manera más general, el teorema de enumeración de Pólya es una herramienta importante para reducir los problemas no etiquetados a los etiquetados: cada clase no etiquetada se considera como una clase de simetría de objetos etiquetados.

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

Fórmulas de enumeración exacta

Algunos resultados importantes en esta área incluyen los siguientes.

• El número de gráficos simples no dirigidos con n vértices etiquetados es 2 ^{n ( n  −1)/2} . ^[8]
• El número de gráficos dirigidos simples con n vértices etiquetados es 2 ^{n ( n  −1)} . ^[9]
• El número C _n de grafos no dirigidos con n vértices etiquetados y conectados 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}.}$

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 la OEIS )

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

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

Base de datos de gráficos

Varios grupos de investigación han creado bases de datos que permiten realizar búsquedas y que enumeran gráficos con determinadas propiedades de tamaños pequeños. 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 . Academic Press . 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)". Base de datos de antiguos alumnos de Cambridge . Universidad de Cambridge.
4. La teoría de distribuciones reducidas en grupos. American J. Math. 49 (1927), 433-455.
5. Harary y Palmer, pág. 1.
6. Sloane, N. J. A. (ed.). "Secuencia A000088 (Número de grafos en n nodos no etiquetados)". La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
7. Cameron, Peter J. (2004), "Automorfismos de grafos", en Beineke, Lowell W.; Wilson, Robin J. (eds.), Temas de teoría de grafos algebraicos , Enciclopedia de matemáticas y sus aplicaciones, vol. 102, Cambridge University Press, págs. 137-155, ISBN 0-521-80197-4
8. Harary y Palmer, pág. 3.
9. Harary y Palmer, pág. 5.
10. Harary y Palmer, pág. 7.
11. 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.