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 > Cantidad de grafos

2005-08-19

Cantidad de grafos

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


La cantidad g de grafos no dirigidos distintos con n nodos distinguibles sin conectores repetidos ni auto-conectores es:

g = 2½n(n – 1)

(1)



Primeros grafos para n = 4.
g0 = 1
g1 = C(C4, 2), 1 = 6
g2 = C(C4, 2), 2 = 15.


La cosa es así: Supongamos que tenemos n nodos y queremos conectarlos de a dos. Podría tratarse, por ejemplo, de todas las formas posibles de establecer contactos en una fiesta, cada nodo representa una persona y cada conector una amistad subyacente. Para dar el primer paso contemos cuantas formas diferentes hay de conectar dos nodos cualesquiera (pero sólo dos) entre los n existentes. La respuesta se puede encontrar en cualquier manual que tenga un capítulo de combinatoria, aquí hay algunas definiciones. El resultado es el número combinatorio de n nodos tomados de dos en dos.

1. Para concretar supongamos n = 4. Si bien se lo mira, el conteo anterior es equivalente a enumerar las diferentes maneras de colocar un único segmento entre 6 posiciones disponibles. Hay, obviamente, seis formas de poner un solo segmento en los seis huecos. Seis es la cantidad máxima de conexiones que puede haber entre 4 nodos y, justamente, es el número combinatorio de 4 tomado de 2 en 2: 6 = C4, 2. La expresión general para 1 conector y n nodos es

g1 = Cn, 2.

(El subíndice 1 de la g indica que se trata de la cantidad de grafos con un solo conector.)

2. El segundo paso consiste en conocer las g2 maneras diferentes de distribuir 2 conectores entre los 6 lugares permitidos (y así hasta que lleguemos a g6, la cantidad máxima de conectores posibles para 4 nodos). Hay dos formas de averiguar este número. La primera surge al notar que sólo se trata de combinar (sin repetición) de dos en dos las g1 (=6) disposiciones calculadas en el paso 1.

La pregunta concreta, entonces, es: ¿Cuántas formas hay de combinar g1 conectores tomados de dos en dos? Y la respuesta es inmediata:

g2 = Cg1, 2 = C(Cn, 2), 2

La otra forma de obtener exactamente la misma respuesta es preguntarse de cuantas maneras distintas se pueden distribuir 2 conectores entre 6 (=g1) espacios posibles.

3. Tres conectores se dispondrán entre los g1 ubicaciones permitidas de

g3 = C(Cn, 2), 3

4.En general, para m conectores logramos:

gm = C(Cn, 2), m

La cantidad total de grafos generados a partir de n nodos es la suma de las cantidades obtenidas:


Aclaración: El símbolo del paréntesis tiene el mismo significado que C. Por ejemplo, el que aparece sobre la sumatoria es idéntico a Cn, 2.


Si uno introduce en el Mathematica (3.0) esa expresión y luego hace FullSimplify[%] recibe:

g = g0 + g1 + g2+ … + gg1 = 2½n(n – 1)

(2)



Para un agasajo pequeño la cantidad de formas posibles de amistades subyacentes es verdaderamente espeluznante:

 1  1
 2  2
 3  8
 4  64
 5  1024
 6  32768
 7  2097152
 8  268435456
 9  68719476736
10  35184372088832
11  36028797018963968
12  73786976294838206464
13  302231454903657293676544
14  2475880078570760549798248448
15  40564819207303340847894502572032
16  1329227995784915872903807060280344576
17  87112285931760246646623899502532662132736
18  11417981541647679048466287755595961091061972992
19  2993155353253689176481146537402947624255349848014848
20  1569275433846670190958947355801916604025588861116008628224

¿En las fiestas se darán cada una de estas posibilidades con igual probabilidad o habrá algún sesgo? Quiero decir, ¿se dará más un tipo de grafos que de otros? ¿cuáles? ¿Dependerán los grafos más probables, si es que hay grafos más probables que otros, del tipo de evento?


2005-08-19 16:10 | 4 Comentarios


Referencias (TrackBacks)

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

Comentarios

1
De: malambo Fecha: 2005-08-19 17:32

"Si uno introduce en el Mathematica (3.0) esa expresión y luego hace FullSimplify[%] quiere decir: "Hay una demostración que nos lleva de una expresión a otra, pero soy muy perezoso para deducirla"



2
De: malambo Fecha: 2005-08-20 09:40

Ver, además, una explicación alternativa y mucho más corta dada por Zifra en los comentarios de la entrada anterior, donde se planteaba el problema.



3
De: Edu Fecha: 2006-02-06 18:19

Hola Malambo y Zifra,

Tengo un problema parecido al que habéis expuesto, aunque creo que no del todo igual....

Lo tengo en Word ya que tiene unos dibujillos de grafos. ¿Podría pasaroslo a alguna dirección de email para que le echéis un vistazo?

Muchas gracias,
Edu



4
De: Martha Guadarrama Fecha: 2012-02-25 03:56

Me gusta el sistema de marketin en red me invitan a formar parte de un sistema para generar ingresos muy muy atractivos me gustaría saber si esta forma de generarlos es posible ya que me di a la tarea de multiplicar de 2x2x2 hasta 64 veces y la cantidad de personas en este caso que tendrían que participar es un número para mi innombrable.envío a tu correo el plan y sinceramente espero puedas tener tiempo de checar ya que somos un gran número de personas que invertimos nuestro tiempo queriendo progresar económicamente a través de estas redes de mercadeo.



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