La pregunta que hace se encuentra en el área de Enumeración de gráficos que trata el problema de contar todos los gráficos de un cierto tipo, en este caso, todos los gráficos con un número dado de vértices y aristas [Harary y Palmer, 1973].
El teorema de la enumeración de Pólya [Harary y Palmer, 1973] da el número de gráficos no isomorfos no marcados con un número dado de nodos y aristas.
Sin embargo, no conozco ningún algoritmo para generar esos gráficos. Por supuesto, el problema general de la enumeración de gráficos es NP-hard [Bezem y van Leeuwen, 1987]. Esto implica que no hay algoritmos de tiempo polinomiales conocidos para este problema. En esta respuesta, solo voy a discutir brevemente las dificultades para abordar este problema.
- ¿Cuál es la complejidad temporal del algoritmo de búsqueda binaria?
- ¿Qué algoritmo usa YouTube para crear la lista de sugerencias de reproducción automática?
- ¿Cuál es el mejor algoritmo de reconocimiento de patrones hoy?
- ¿Cómo funciona este algoritmo para encontrar los bordes del corte mínimo de un gráfico?
- ¿Cómo ordenar un millón de números en tiempo de registro usando la solución Norman Hardy?
Primero, algunos conceptos básicos. Dado un gráfico, , existen
bordes o conexiones potenciales dirigidas que se pueden agregar a G. Si los bordes no están dirigidos, entonces hay
Conexiones potenciales.
Los gráficos se pueden etiquetar con vértices, es decir, cada vértice en el gráfico tiene una etiqueta que lo distingue de otros vértices con fines de enumeración, o sin etiquetar. El número de gráficos etiquetados dirigidos con nodos y
bordes es:
El número de gráficos etiquetados no dirigidos con nodos y
bordes es:
.
Cuando hablamos de gráficos no etiquetados, lo que nos importa es la estructura o la topología de la red y no el orden de los nodos. En general, los problemas de enumeración no marcados son más difíciles de resolver que los problemas de enumeración etiquetados.
Aquí es donde entra en escena el teorema de la enumeración de Pólya (consulte también: http://www.cs.columbia.edu/~cs42…). Da el número de gráficos no isomorfos no marcados con un número dado de nodos y aristas.
Generar todos los gráficos no marcados no isomórficos es un problema completamente diferente. No se conocen algoritmos de tiempo polinomiales para resolver el isomorfismo de dos gráficos.
Referencias
[Harary y Palmer, 1973] F. Harary y E. Palmer. Enumeración gráfica, volumen 123. Academic Press, Nueva York, primera edición, 1973.
[Bezem y van Leeuwen, 1987] GJ Bezem y J. van Leeuwen. Enumeración en gráficos. RUU-CS-87-7, Rijksuniversiteit Utrecht, mayo de 1987.
