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.