En este post la noción matemática de grafo es presentada a través de la metáfora de los poliedros y la relación de adyacencia entre sus vértices. Y ello para darle la vuelta a las definiciones formales, y ahorrarnos al menos cuatro definiciones: vértice, arista, la relación de adyacencia entre vértices, y la de incidencia entre vértices y aristas.
(Estos cuatro conceptos mantienen en el grafo su significado que tienen en el poliedro. Se aprovecha así que éste le es familiar a cualquier adolescente que haya pasado por una educación media de cierta calidad --y él mismo no haya burlado al sistema aprovechando su "manga ancha" y/o aplicando los 1001 trucos que existen para pasar de un grado a otro sin estudiar.)
Se presenta también --como un ejemplo de aplicación de los grafos-- el problema clásico de los amigos y desconocidos (el otro friendship theorem), se modela con un grafo y se resuelve con un razonamiento elemental y casi ateórico. Nota: Se usa el término grafo como traducción del término inglés graph, como una forma de evitar evocar el significado de gráfica de una función.
Poliedros de hule: la metáfora original
Un grafo es un objeto matemático usado para representar relaciones entre objetos. Por ejemplo la relación de amistad entre personas. La terminología inicial (vértices, aristas, incidencia, adyacencia) está inspirada, o tiene como telón de fondo, la metáfora de los poliedros: un tetraedro tiene 4 vértices y cuatro aristas, y en cada vértice inciden 3 aristas; también se dice que dos vértices son adyacentes o vecinos si están unidos por una arista.
La representación de un poliedro mediante un grafo tiene varias ventajas, pero es necesario hacer la "traducción": el grafo se dibuja sobre un plano, mientras que la representación usual de un poliedro, aunque también se realiza sobre el plano, trata de imitar la forma en que uno lo percibe en tres dimensiones.
Teorema de amigos y desconocidos (el otro teorema de la amistad)
En un grupo de 6 personas siempre existen 3 que son amigos entre sí o bien desconocidos entre sí (mutuamente conocidos o mutuamente desconocidos).
| Razonamiento con lenguaje natural | Razonamiento con grafos |
|---|---|
| Elijamos una de las personas en el grupo, llamémosla P. | Elijamos uno de los vértices del grafo, llamémoslo P. |
| Respecto a las otras 5 personas, P puede conocerlas o no conocerlas. | Las 5 aristas incidentes con P están bicoloreadas; unas son verdes y las otras rojas. |
| Por el principio de las pichoneras, P conoce a 3 de ellas o bien desconoce a 3 de ellas | Por el principio de las pichoneras, hay tres aristas incidentes con P que son del mismo color. |
| Si P conoce a tres de ellas , entonces llamémoslas A,B,C. | Si tres de las aristas incidentes con P son verdes, entonces llamémos A,B,C a los extremos de tales aristas. Es decir, PA, PB y PC son verdes. |
| Si las 3 personas A,B,C son desconocidos entre si , ya terminamos. | Si las 3 aristas del triángulo ABC son rojos, ya terminamos. |
| De otra manera, dos de ellos son amigos, digamos la A y la B . | De otra manera, una de ellas es verde, digamos la arista AB es verde. |
| Se concluye que P, A y B son amigos entre sí. | Se concluye que las aristas del triángulo PAB son verdes. |
Comentarios
- Notemos primero que, para una reunión particular de 6 personas, el grafo asociado debe tener dos tipos de aristas. Y la forma más fácil de distinguirlas es coloreándolas a dos tintas.
- Después habría que decir que ya con el grafo coloreado (a pesar de que solamente se sabe que es bicolor y no se sabe de qué color es cada arista) la mente ya tiene un objeto concreto sobre el cual razonar (así sea imaginario, pues el grafo es fácil de imaginar --es un hexágono con todas sus diagonales).
- La demostración es fácil de seguir (aunque, históricamente, no haya sido fácil de inventar). Y quizá no sea fácil para el novicio mantener en suspenso el color de cada arista. De hecho, parece ser que la capacidad de mantener el suspenso es una habilidad aprendida y debe ser adquirida de manera consciente y en la práctica --es decir, no es una habilidad espontánea o natural.
- La demostración escasamente requiere de algún resultado matemático (el principio de las pichoneras puede evitarse: "son 5 de dos colores, 3 tienen que ser del mismo color, chécalo"). Sin embargo, mantener la atención y dividir en casos no son tampoco habilidades naturales. (Lo normal es más bien la atención dispersa y la división en casos es parte del método analítico de razonamiento.)