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 = C
4, 2. La expresión general para 1 conector y
n nodos es
g1 = C
n, 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 = C
g1, 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 | 3 Comentarios
