Ves esta página sin formato porque esta hecha cumpliendo el estándar web CSS 2.
Tu navegador no soporta este estándar, o tienes dicho soporte desactivado.
si estas en el primer caso, actualízate. merece mucho la pena.

Una aventura personal hacia las redes complejas.


Inicio > Historias > Habituales problemas de los 14 de agosto de 2005

2005-08-15

Habituales problemas de los 14 de agosto de 2005

Por malambo en Invariancia.Matemáticas | 2005-08-15


¿Qué cantidad g de grafos G = <N, D> distintos pueden formarse a partir de n nodos?

Nota: No están permitidos los auto-conectores (<i, i>) ni más de un conector por cada par de nodos. Los nodos se consideran distinguibles, es decir, las configuraciones de la figura de la izquierda son distintas (ver comentarios).

Para n = 1 es fácil, g = 1; para n = 2, g = 2; si n = 3, g = 8 (aquí ya hay que usar papel y lapiz). Me resulta extraño llamar grafo a uno cuya estructura D sea un conjunto vacío, pero decidí incluirlos también.


2005-08-15 01:07 | 9 Comentarios


Referencias (TrackBacks)

URL de trackback de esta historia http://invariancia.blogalia.com//trackbacks/32312

Comentarios

1
De: Zifra Fecha: 2005-08-16 10:39

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 :-)



2
De: DESPISTÁ Fecha: 2005-08-16 13:45

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?



3
De: malambo Fecha: 2005-08-16 19:29

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á.



4
De: DESPISTÁ Fecha: 2005-08-17 15:22

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



5
De: malambo Fecha: 2005-08-17 22:52

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.



6
De: Zifra Fecha: 2005-08-19 12:23

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?



7
De: Zifra Fecha: 2005-08-19 12:26

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 



8
De: Zifra Fecha: 2005-08-19 12:27

je je


más o menos :-)



9
De: malambo Fecha: 2005-08-20 09:48

¡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)



Nombre
Correo-e
URL
Dirección IP: 54.224.103.239 (68fab4310c)
Comentario
¿Cuánto es: diez mil + uno?

portada | subir

(CC) 2005-2006 - malambo