23 enero 2007

Los grafos: Cadena de favores

Hace unas semanas en mis clases de Matemática Discreta comenzamos a dar un nuevo concepto, los grafos. Los grafos son algo así como representación de puntos unidos por líneas, los puntos se llaman vértices y las líneas lados. Si el lado en lugar de ser una simple línea es una flecha, se llama un lado dirigido (y lógicamente, su dirección es la representada por la flecha). Luego la cosa se complica un poco más (tampoco mucho), entran muchos conceptos nuevos, los caminos, los ciclos, la matriz de adyacencia, los grafos planos y los conexos, los subgrafos.

Hasta aquí, todo muy interesante. Pero lo cierto es que a mí me costaba verle aplicación práctica.
Entonces llegó el concepto de árbol. Un árbol es un grafo conexo sin ciclos. Es decir, es una sucesión de puntos unidos por líneas en los cuales no coincide el principio con el final (ésta explicación no es del todo exacta pero sirve para forjarse una idea). El profesor explica tras esto el concepto de bosque, el de hoja, y el de altura del árbol. Entonces dibuja varios ejemplos y es cuando yo entonces lo veo claro viendo este grafo:
Y así infinitamente, partiendo desde cada vértice padre (desde los cuales parte la flecha) tres vértices hijo (a los cuales apunta la flecha).

Este grafo es la representación de la Cadena de favores. Tal vez no hayáis visto esta película, así que explico brevemente el concepto de la cadena de favores. Una persona debe hacerle un favor a otras tres, pero debe ser un favor importante, debe ayudarles haciendo algo que ellos no podrían hacer por sí mismos. La persona receptora de dicho favor no debe devolver ese favor a la anterior persona, debe hacer él mismo tres favores a otras personas siguiendo las mismas reglas, así, el número de beneficiados crece espectacularmente. Si se observa el grafo anterior se puede ver claramente que es la representación gráfica de dicha idea (que dicho sea de paso, me parece magnífica).

Después de ver la película, una de las inquietudes que me quedó fue saber, ¿cómo crece la cadena? Es decir, ¿a qué cantidad de personas afecta pasado un tiempo?

Aquí es donde el grafo nos va a ayudar. El nivel de un grafo es el número de lados que hay que recorrer hasta llegar al vértice origen (llamado raíz). Gráficamente:

La altura de un árbol es el nivel máximo que se alcance por alguna hoja (una hoja es un vértice hijo a partir del cual no sale ninguna flecha, en la representación de arriba, se trataría de todos los vértices de nivel 3).

Al tratarse de un árbol regular completo existe una formula para calcular el número de vértices del grafo (o si preferís, el número de personas afectadas por la Cadena de favores).

Donde m es el número de hijos que tiene cada padre (número de flechas que sale de cada vértice) y h es la altura el grafo. En el caso de la Cadena de favores:

Podemos observar que si sustituimos h=0, el resultado es 1. Es decir, el vértice raíz se encuentra incluido en la fórmula. En el caso de la Cadena de favores, si queremos retirar esta persona (ya que no recibe ningún favor de nadie) sencillamente deberemos restar 1 a la fórmula. Así:

No obstante, la exclusión o no de esta persona supongo que está sujeto a interpretaciones. Yo por lo pronto no lo excluiré.

Vamos, a hacer dos ejemplo, uno con nivel 3 (que es el grafo dibujado arriba) y otro con un nivel más alto para ver de que manera crece la cadena.

Con nivel 3:

Si alguien se quiere molestar en contar los puntos del grafo de arriba, podrá comprobar que efectivamente son 40.

Con nivel 16:

Efectivamente, el número de personas afectadas crece de manera espectacular. Sin duda sería una iniciativa muy bonita para llevar a cabo.

Me vuelvo a seguir estudiando.

7 comentarios:

Miguel dijo...

Cabrón, decías que no ibas a poner imágenes en tu blog y para una vez que pones tiene que ser un maldito grafo?! No podría haberte dado por poner paisajes, o fotos tuyas con cara triste, como en la mayoría de los blogs, copón.

Al respecto del artículo, sí, sería bonito, que te hagan favores suele estar muy bien, pero hacerlos da una pereza...

Un saludo!

Frozen dijo...

Lo cierto es que las limitaciones de blogger me obligan a usar imagenes para representar grafos y fórmulas. No obstante es perfectamente posible que algún día ponga alguna imagen de un paisaje o de lo que sea, pero será sólo en caso de que lo considere necesario o importante para el artículo.

Hala, mañana nos vemos.

Löla dijo...

Jajaja a mi el primer dibujote me recordaba a grupos de filiación de cognados (cada loco con su tema).
No hace mucho vi un reportaje sobre el banco del tiempo, la idea era parecida sólo que una persona prestaba servicios en algo que se la diese bien a otras personas y éstas se lo prestaban a él.
En fin, super interesante.
Yo sí que te hacía un favor .. QW

Casshern25 dijo...

más que espectacularmente que queda muy peliculero crece exponencialmente ... no estudies demasiado, es malo para la salud y te puedo garantizar que lo grafos tienen muchisimas aplicaciones.

Ines dijo...

La Lola va a saco paco xD

Y hombre claro, yo los grafos los uso a diario ufff si yo te contara, grafo por aqui grafo por allá...enfin....esq practicamente no se hablar de otra cosa xD

ale un besillo tai y no estudies pero aprueba

Frozen dijo...

jajajaja

que gracia me ha hecho lo de no estudies pero aprueba xD

lola QW QW

Aprendiz dijo...

Hombre, el número más que crecer de manera espectacular, crece de manera exponencial. De ahi, representa una semilogarítmica y tiene que salir una recta guapa guapa, jaja.