Cuántos conectados gráficos sobre V de vértices y E aristas?

Question

Es allí una manera de calcular el número de sencillos gráficos posibles sobre dadas las aristas y los vértices?

Por ejemplo: 3 vértices y 2 bordes tendrá 3 conectados gráficos Pero 3 vértices y 3 bordes tendrá 1 gráfica conectada

Luego de 4 bordes y 3 de 4 conectado gráficos

Hasta esos valores...es fácil ver su

V elegir E

Pero ¿qué pasa cuando el número de vértices son menos que el número de bordes...cómo calcular entonces?

Yo no soy capaz de visualizar que

Puede ser una variación de las Estrellas y las Barras de problema

Como...número de maneras en que 7 de los bordes(bolas) puede ser conectado a (en) 5 vértices(bolsas) de tal manera que ningún vértice(bolsa) aislado (está vacía)

Aquí tal vez podríamos considerar el número de aristas de dos veces cada borde de las necesidades de los dos vértices...

Answer 1

Desde este enlace que ha demostrado algo popular, pero no todo el mundo tiene acceso a Arce estoy ofreciendo una implementación en C con una piedra de Rosetta efecto en la mente. Utiliza Linux, GCC y GMP, el GNU multiprecision biblioteca, todos los de software libre.

Esta simple aplicación no puede competir con Maple rápida multiplicación de polinomio rutinas pero es fácil y dramáticamente supera a la de Arce, donde los requisitos de memoria son considerados. Esta es una implementación del método de las tres de la otra respuesta.

Aquí es un extracto de la cuenta de etiquetado conectado gráficos en 100 vértices, a partir de una lista inclusiva que fue calculado en siete minutos de tiempo de cálculo.

000099: 100000000000000000000000000000000000000000000000000000000...
00000000000000000000000000000000000000000000000000000000000000000...
00000000000000000000000000000000000000000000000000000000000000000...
0000000000
000100: 510998031510799015012656647840750649920635707969633111192...
74962605644046874114483034395313967828782400387155843473213972763...
99467183347288626786506867710921922978521653363154616320000000000...
000000000000
000101: 142104312990406781581856724418579090842592500736876137027...
51254362674861198019976979320546703753308719954831818261458369844...
20062161942816326874907532100392442319172473774298628096000000000...
000000000000000
000102: 285447614274319041715048588557494933600690703567446638297...
69028676129587231453229391167155803192891772461953364139194426826...
37181075598419404686535843240073366679296837828275433635840000000...
00000000000000000
000103: 463447763717575519689003062414703595381839972980633113575...
39624468095301976364461153148637638737169543440731383717246460520...
02029075049263459712354346265371921759545922872425765142528000000...
0000000000000000000
000104: 645027341544448563672840738480002899046044088823901830764...
81475379638063891987227335687086646777908138584098153398093224443...
15708495657071771542347812451362360998192317323814303705753190400...
000000000000000000000

Y este es el código fuente.

#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>

typedef struct {
 mpz_t *los datos;
 int grado;
} pl, *plptr;

plptr pl_new(int grado)
{
 plptr item = (plptr)malloc(sizeof(pl));

 item->grado = grado;
 item->datos = (mpz_t *)malloc((grado+1)*sizeof(mpz_t));

 int k;
 para(k = 0; k <= grado; k++){
mpz_init(elemento->datos[k]);
}

 devolver el producto;
}

void pl_free(plptr elemento)
{
 int k;

 para(k = 0; k <= item->grado; k++){
mpz_clear(elemento->datos[k]);
}

libre(elemento->data);
libre(elemento);
}

void pl_print(plptr elemento, FILE *stream)
{
 int k;

 para(k = 0; k <= item->grado; k++){
 fprintf(stream, "%06d: ", k);
 mpz_out_str(arroyo, 10, artículo->datos[k]);
 fprintf(stream, "\n");
}
}

plptr pl_binom(int grado)
{
 plptr item = pl_new(grado);

 int k; mpz_t val;
mpz_init(val);
 mpz_set_si(val, 1);

 para(k = 0; k <= grado; k++){
 mpz_set(elemento->datos[k], val);

 mpz_mul_si(val, val, grado-k);
 mpz_divexact_ui(val, val, k+1);
}

mpz_clear(val);

 devolver el producto;
}

void pl_scale(plptr elemento, mpz_t hecho)
{
 int k;

 para(k = 0; k <= item->grado; k++){
 mpz_mul(elemento->datos[k], elemento->datos[k], dato);
}
}

plptr pl_mul(plptr op1, plptr op2)
{
 int newdeg = op1->grado + op2->grado;
 plptr item = pl_new(newdeg);

 int p; mpz_t plazo; mpz_t cfprod;
 mpz_init(plazo); mpz_init(cfprod);
 para(q = 0; q <= newdeg; q++){
 mpz_set_si(término, 0);

 int p;
 para(p = 0; p <= p; p++){
 si(p <= op1->grado && p-p <= op2->grado){
 mpz_mul(cfprod, op1->datos[p], op2->datos[p-p]);
 mpz_add(plazo, plazo, cfprod);
}
}

 mpz_set(elemento->datos[q], duración);
}
 mpz_clear(cfprod); mpz_clear(plazo);

 devolver el producto;
}

plptr pl_add(plptr op1, plptr op2)
{
 int newdeg = 
 (op1->grado > op2->grado ?
 op1->grado : op2->grado);
 plptr item = pl_new(newdeg);

 int p; mpz_t plazo;
mpz_init(plazo);
 para(q = 0; q <= newdeg; q++){
 si(p > op1->grado){
 mpz_set(plazo, op2->datos[q]);
}
 else if(p > op2->grado){
 mpz_set(plazo, op1->datos[q]);
}
else{
 mpz_add(plazo, op1->datos[q], op2->datos[q]);
}

 mpz_set(elemento->datos[q], duración);
}
mpz_clear(plazo);

 devolver el producto;
}

void elegir(mpz_t targ, int n, int k)
{
 mpz_set_si(targ, 1);

 int p;
 para(q = 0; q < k; q++){
 mpz_mul_si(targ, targ, n-q);
 mpz_divexact_ui(targ, targ, q+1);
}
}

int main(int argc, char **argv)
{
 de largo n = 3, k = -1;

 if(argc >= 2){
 n = atol(argv[1]);

 si(n < 1){
 fprintf(stderr, "el número de vértices fuera de rango "
 "tiene %ld\n", n);
exit(-1);
}
}

 if(argc >= 3){
 k = atol(argv[2]);

 si(k < n-1 || k > n*(n-1)/2){
 fprintf(stderr, "borde conteo fuera del intervalo para el %ld "
 "tiene %ld\n", n, k);
exit(salir) (-2);
}
}

 plptr *bintable = 
 (plptr *)malloc((n+1)*sizeof(plptr));

 plptr *gftable = 
 (plptr *)malloc((n+1)*sizeof(plptr));

 int deg;
 para(deg = 0; gr <= n; deg++){
 bintable[deg] = pl_binom(deg*(gr-1)/2);
 gftable[deg] = NULL;
}

 gftable[0] = pl_binom(0);
 gftable[1] = pl_binom(0);

 int nval; mpz_t factor;

mpz_init(factor);
 para(nval = 2; nval <= n; nval++){
 int q = nval-1;

 int m; plptr contrib; plptr todos;
 todos = bintable[q+1];

 for(m = 0; m <= q-1; m++){
 elegir(factor q, m);
 mpz_neg(factor, factor);

 contrib = pl_mul(bintable[q-m], gftable[m+1]);
 pl_scale(contrib factor);

 plptr prev = todos;
 todos = pl_add(todos, contrib);
 si(m > 0) pl_free(prev);

pl_free(contrib);
}

 gftable[nval] = todos;
}
mpz_clear(factor);

 if(argc == 2){
 pl_print(gftable[n], stdout);
}
else{
 mpz_out_str(stdout, 10, gftable[n]->datos[k]);
printf("\n");
}

 para(deg = 0; gr <= n; deg++){
pl_free(gftable[deg]);
pl_free(bintable[deg]);
}
libre(gftable);
libre(bintable);

 return 0;
}