Suposiciones
Queremos escribir un algoritmo eficiente para enumerar todos los gráficos etiquetados simples conectados con vértices [math] n \ in \ mathbb {N} [/ math]. En otras palabras, si dos gráficos son isomorfos entre sí, todavía los contamos por separado si las etiquetas de sus vértices son diferentes. Hay al menos [matemáticas] 2 [/ matemáticas] casos diferentes que la pregunta podría estar considerando.
Caso A:
Deseamos enumerar todos los gráficos etiquetados no dirigidos simples conectados con vértices [math] n [/ math].
- Cómo resolver un problema sobre el multiplicador de Lagrange
- ¿[Math] \ Theta (n ^ 2) [/ math] incluye [math] O (n ^ 3) [/ math]?
- ¿Hay un número que consta de 10 factores?
- ¿Existe alguna conexión entre la fórmula para el número de apretones de manos intercambiados entre n personas y la fórmula para una suma aritmética?
- ¿Por qué el algoritmo de división de Euclides del resto no negativo no se sigue en la programación?
Caso B:
Deseamos enumerar todos los gráficos etiquetados dirigidos simples conectados débilmente con vértices [math] n [/ math].
Razonamiento:
Tenga en cuenta que no deseamos simplemente generar el número de gráficos relevantes; eso se puede hacer de manera mucho más eficiente que enumerarlos a todos. Para el caso A , el número de tales gráficos es [matemática] f_A (n) = \ begin {cases} 1 & \ text {,} n = 1 \\ 2 ^ {\ binom {n} {2}} – \ frac {1} {n} \ sum \ limits_ {k = 1} ^ {n-1} {k \ binom {n} {k} 2 ^ {\ binom {nk} {2}} f_A (k)} & \ texto {, de lo contrario} \ end {casos} [/ math]. Para el caso B , el número de tales gráficos es [matemática] f_B (n) = \ begin {cases} 1 & \ text {,} n = 1 \\ 2 ^ {2 \ binom {n} {2}} – \ frac {1} {n} \ sum \ limits_ {k = 1} ^ {n-1} {k \ binom {n} {k} 2 ^ {2 \ binom {nk} {2}} f_B (k)} & \ text {, de lo contrario} \ end {cases} [/ math].
Podemos enumerar nuestros gráficos usando la búsqueda de profundidad primero (también conocida como retroceso). También almacenamos en caché todos los gráficos que ya hemos observado, por lo que nunca volvemos a formar el gráfico a partir de la misma configuración inicial, reduciendo así grandes porciones de la búsqueda. Mientras agregamos bordes, mantenemos la invariante de que el gráfico hasta ahora está conectado.
Al enumerar los gráficos para el caso A , podemos comenzar esencialmente con el nodo [math] 1 [/ math] y crecer a partir de ahí. En otras palabras, podemos asegurarnos de que el siguiente borde que agreguemos al gráfico siempre tenga al menos [math] 1 [/ math] de su origen o destino en el gráfico ya conectado. Por lo tanto, cuando [math] n [/ math] vértices distintos han sido tocados por nuestros bordes añadidos, podemos estar seguros de que tenemos un gráfico válido que cumple los criterios.
Al enumerar los gráficos para el caso B , aún podemos comenzar con el nodo [math] 1 [/ math] y crecer a partir de ahí. Sin embargo, es un poco más ineficiente en este caso garantizar que al menos [math] 1 [/ math] del origen o destino de cada borde agregado se encuentre entre nuestros vértices ya utilizados.
Resultados:
Tenga en cuenta que A001187 – OEIS y A003027 – OEIS también muestran el número de gráficos que se muestran en el Caso A y el Caso B , respectivamente. A continuación se muestran algunos de los resultados que obtuve con mi código, junto con sus tiempos de ejecución.
Caso A:
Caso B:
Código:
El siguiente script de Python enumera eficientemente los gráficos relevantes. La entrada de alto nivel es simplemente “dirigida” (un valor booleano que indica si estamos encontrando gráficos dirigidos (para el caso B ) o no (para el caso A )) y “numNodes” (el número de nodos en el gráfico).
#! / usr / bin / python
tiempo de importación
def main ():
imprima “nodos numéricos \ gráficos tnum \ ttime (s)”
dirigido = falso
para numNodes en el rango (1, 8):
startTime = time.time ()
connectedGraphs = enumerateConnectedGraphs (numNodes, dirigido)
totalTime = time.time () – startTime
# print str (connectedGraphs)
print str (numNodes) + “\ t” + str (len (connectedGraphs)) + “\ t” + str (totalTime)
def enumerateConnectedGraphs (numNodes, dirigido):
allNodes = range (1, numNodes + 1)
# Inicialice el primer nodo como parte de nuestro gráfico creciente.
usedNodes = dict ()
usedNodes [allNodes [0]] = 0
# Rellene los bordes permitidos desde cada vértice de origen.
unusedEdges = dict ()
para src en allNodes:
unusedEdges [src] = set ()
para dest en todos los nodos:
if dest! = src:
unusedEdges [src] .add (dest)
return helpEnumerateConnectedGraphs (set (),
conjunto(),
conjunto(),
usedNodes,
Bordes no utilizados,
allNodes,
dirigido)
def helpEnumerateConnectedGraphs (currentGraph,
visto Gráficos,
respuestas
usedNodes,
Bordes no utilizados,
allNodes,
dirigido):
if currentGraph en seenGraphs:
# No rehaga el trabajo ya realizado para este gráfico.
devolver respuestas
frozenCurrentGraph = frozenset (currentGraph)
seenGraphs.add (frozenCurrentGraph)
if len (usedNodes) == len (allNodes):
# Si ya hemos visitado todos los nodos “allNodes”,
# luego incluya el gráfico actual en las respuestas.
answers.add (frozenCurrentGraph)
si se le indica:
# Si estamos buscando gráficos dirigidos, entonces el potencial
# la fuente del siguiente borde puede ser cualquiera de los nodos.
PotencialSrcs = allNodes
origUsedNodes = set (usedNodes)
más:
# Si estamos buscando gráficos no dirigidos, entonces podemos con seguridad
# limita la fuente del siguiente borde para que ya se visite vértices.
PotencialSrcs = usedNodes
para src en potencialSrcs:
para dest en no utilizadosEdges [src]:
si se dirige y src no en origUsedNodes y dest no en origUsedNodes:
# En el caso dirigido, necesitamos esta verificación para asegurarnos de que
# Mantenemos conectividad en el gráfico hasta ahora.
Hacer continuación
borde = (src, dest)
# Las siguientes líneas solo actualizan todos los datos relevantes
# estructuras con el nuevo borde en el gráfico.
currentGraph.add (borde)
si no se indica:
reverseEdge = (dest, src)
currentGraph.add (reverseEdge)
unusedEdges [dest] .remove (src)
si se indica y src no está en nodos usados:
usedNodes [src] = 0
usedNodes [src] + = 1
si dest no está en los nodos usados:
usedNodes [dest] = 0
usedNodes [dest] + = 1
unusedEdges [src] .remove (dest)
# Haga una búsqueda profunda primero, con este nuevo borde agregado.
helpEnumerateConnectedGraphs (currentGraph,
visto Gráficos,
respuestas
usedNodes,
Bordes no utilizados,
allNodes,
dirigido)
# Las siguientes líneas solo actualizan todos los datos relevantes
# estructuras eliminando el nuevo borde en el gráfico.
si no se indica:
unusedEdges [dest] .add (src)
currentGraph.remove (reverseEdge)
unusedEdges [src] .add (dest)
usedNodes [dest] – = 1
si se usaNodes [dest] == 0:
del usedNodes [dest]
usedNodes [src] – = 1
si se dirige y se usa Nodos [src] == 0:
del usedNodes [src]
currentGraph.remove (borde)
devolver respuestas
if __name__ == ‘__main__’:
principal()