Enumeración de gráficos

La enumeración de gráficos es una categoría de  problemas de combinatoria enumerativa en la que es necesario enumerar 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 se pueden resolver exactamente (como el problema de la enumeración algebraica) o asintóticamente . Los pioneros en esta área de las matemáticas fueron Poya [2] , Cayley [3] y Redfield[4] .

Tareas marcadas y no marcadas

En algunos problemas de enumeración de gráficos, los vértices de los gráficos se consideran etiquetados , lo que los hace distinguibles entre sí. En otros problemas, cualquier permutación de vértices se considera 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 simples [1] . El teorema de Redfield-Polyi es una herramienta importante para reducir un problema no etiquetado a uno etiquetado: cada clase no etiquetada se considera una clase de simetría de objetos etiquetados.

Fórmulas de enumeración exacta

Algunos resultados importantes en esta área.

• El número de grafos no dirigidos simples etiquetados con n vértices es 2 n ( n  − 1)/2 [5]
• El número de gráficos dirigidos simples etiquetados con n vértices es 2 n ( n  − 1) [6]
• El número C n de grafos no dirigidos etiquetados conectados con n vértices satisface la relación recursiva [7]

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

Véase también

• Teoría de grafos algebraicos
• Teoría de grafos espectrales
• Teoría de grafos topológicos

Notas

1. ↑ 12Harary , Palmer , 1973 .
2. ↑ Polonia, 1937 , p. 145-254.
3. ↑ Arthur Cayley  (enlace no disponible) Una base de datos de antiguos alumnos de Cambridge . Universidad de Cambridge.
4. ↑ Redfield, 1927 , pág. 433-455.
5. ↑ Harary, Palmer, 1973 , pág. 3.
6. ↑ Harary, Palmer, 1973 , pág. 5.
7. ↑ Harary, Palmer, 1973 , pág. 7.
8. ↑ Secuencia OEIS A001187 _
9. ↑ Harary, Schwenk, 1973 , pág. 359–365.

Literatura

• Harary F. , Palmer E.M. Enumeración gráfica. - Prensa Académica , 1973. - ISBN 0-12-324245-2 .
• Harari F., Palmer E. Enumeración de gráficos = traducción al ruso del párrafo anterior. - Mundo , 1977.
• Harary F. , Schwenk AJ El número de orugas // Matemáticas discretas. - 1973. - T. 6 , núm. 4 . — S. 359–365 . - doi : 10.1016/0012-365x(73)90067-8 .
• Pólya G. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen  // Acta Mathematica . - 1937. - Vol. 68. -doi : 10.1007/BF02546665 .  (enlace no disponible)
• La teoría de las distribuciones de grupos reducidos // American J. Math. - 1927. - T. 49 .