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 no dirigidos o dirigidos de ciertos tipos, típicamente en función del número de vértices del gráfico. [1] Estos problemas pueden resolverse 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 vs 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éntico o sin etiqueta . En general, los problemas etiquetados tienden a ser más fáciles. [5] Como ocurre con la enumeración combinatoria en 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 una clase de simetría de objetos etiquetados.
Fórmulas de enumeración exactas
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 . [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értice etiquetados conectados satisface la relación de recurrencia [8]
- a partir del cual se puede calcular fácilmente, para n = 1, 2, 3, ..., que los valores de C n son
- El número de árboles libres de n- vértices etiquetados es n n - 2 ( fórmula de Cayley ).
- El número de orugas n- vértice sin etiquetar es [9]
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
Referencias
- ^ Harary, Frank ; Palmer, Edgar M. (1973). Enumeración gráfica . Prensa académica . ISBN 0-12-324245-2.
- ^ Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145-254
- ^ "Cayley, Arthur (CLY838A)" . Una base de datos de antiguos alumnos de Cambridge . Universidad de Cambridge.
- ^ La teoría de distribuciones reducidas por grupos. American J. Math. 49 (1927), 433-455.
- ^ Harary y Palmer, p. 1.
- ^ Harary y Palmer, p. 3.
- ^ Harary y Palmer, p. 5.
- ^ Harary y Palmer, p. 7.
- ^ Harary, Frank ; Schwenk, Allen J. (1973), "El número de orugas" (PDF) , Discrete Mathematics , 6 (4): 359–365, doi : 10.1016 / 0012-365x (73) 90067-8 , hdl : 2027.42 / 33977.