Sin isomorfismos (cada fila de tu figura muestra grafos que matematicamente son los mismos):

1 1
2 2
3 4
4 11
5 34
6 156
7 1044
8 12346
9 274668
10 12005168
11 1018997864
12 165091172592
13 50502031367952

Si son diferentes : 2^n, por supuesto :-)

Matemáticamente quizá sí, pero si consideramos una situación real, como por ejemplo un circuito eléctrico en el que uno de los nodos es el proveedor de energía al circuito y los otros dos simples interruptores (los conectores serían obviamente los cables)... entonces, aunque el valor matemático de la figura sea el mismo... el resultado no lo es. A ver si me explico. Imaginemos que A es el interruptor que aporta la energía al circuito y B y C son los otros dos nodos. Entonces para A+B= se enciende la bombillita, pero B+C= apagón.

¿O me estoy equivocando de nuevo?

Me has arruinado la sorpresa de las clases de equivalencias, Zifra. :oD

Gracias por pasar y tomarte el tiempo para dejar tu comentario. Y sí, admito que no he definido cuando dos grafos son iguales. Consideremos que los nodos son distinguibles, pero que el grafo es no dirigido, es decir, < i, j > = < j, i > .

Pues no, el resultado que das ya no es correcto para n=4. Faltarían incluir, por ejemplo y según vengas contando, los grafos con nodos de grado 3. Incluso hay más de once si solo cuentas cuentas los grafos de 4 nodos con 1 y 2 conectores.

2^n no es válido para n = 1, 2, 3.

Despistá: ¡Vas muy rápido, mujer! :o) "Déjanos" a los de exactas hacer todo este menjunje teórico antes de aplicarlo a cuestiones concretas.

Por ahora solo estamos contando todas las diferentes maneras que se pueden comunicar entre si los nodos de un mismo tipo. La idea general es que una vez que sabes cuantos son todos los grafos posibles y los clasificas por sus formas -eso que decía Zifra del isomorfismo-, seleccionas aquellas maneras de comunicación compatibles con los resultados de las mediciones hechas en la realidad.

Sin duda en lo que dices tienes razón, pero estamos en un nivel previo. Todavía no estoy considerando el estado de cada nodo en particular (interruptor 'on' u 'off'), tampoco el estado de cada conector (cantidad de flujo eléctrico que puede transportar, por ejemplo) simplemente estoy viendo como están conectados los cables. Pero no me apures, tiempo al tiempo y llegará.

Yo es que soy de letras, qué se le va a hacer. Mi mente no llegaba pa más. Y necesito aplicar las matemáticas para entenderlas un poquito. Ya avisé de que andaba un poco despistada en el tema ;) Pero que conste que le pongo empeño

La aplicación que te propongo, despistá, es hacer dibujitos. En el problema puse los tres primeros grafos y todas sus conexiones, para el cuarto ya se complica un poco (aunque no se hace cualitativamente más difícil).

Lo que hay que hacer es poner cuatro nodos (puntos) en los vértices de un cuadrado y ver cuantas maneras hay de conectarlos.

Con un solo conector (es decir sólo dos nodos conectados y los otros dos desconectados) hay 6 maneras posibles, con dos conectores son 15 las configuraciones posibles (ya van 6+15=21); con tres conectores hay 20 formas diferentes (41).

Como con 4 nodos la cantidad máxima de conectores es 6, todavía falta ver cuantas configuraciones posibles hay con 4, 5 y 6 conectores.

Pero sobre todo hay que empezar a buscar una forma general (una fórmula) que me diga: Tienes n nodos distintos, entonces tienes g grafos posibles, donde n y g son números, claro.

Mis resultados son para nodos no distinguibles, por eso no te coinciden.

Sin embargo, es correcta tu apreciación para el caso de nodos distinguibles. No es 2^n.

Existen n(n-1)/2 aristas posibles para n vértices. Entonces, el número de grafos posibles es exactamente el cardinal del conjunto de partes de n(n-1)/2, o sea 2^(n(n-1)/2)

n n(n-1)/2 2^(n(n-1)/2)
-- ----------- ----------------
1 0 1
2 1 2
3 3 8
4 6 64
5 10 1024

¿ok?

ops... se me olvido el tag PRE

a ver ahora:

n       n(n-1)/2      2^(n(n-1)/2)
--      -----------      ----------------
1             0                     1
2             1                     2
3             3                     8
4             6                   64
5           10              1024 

je je


más o menos :-)

¡Y yo que le dediqué horas-Corel a hacer los dibujitos!

Si hubiera leído esta entrada antes no hubiera hecho la entrada que vino después (o por lo menos no una tan larga, pudiendo decirlo con menos palabras).

El tag < pre > no lo conocía, no faltará oportunidad de utilizarlo ;o)