Grafos --y la modelación de relaciones

Versión para impresión

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. 

Lo que representa el grafo de un poliedro es la relación de adyacencia entre los vértices. Por esa razón no se le debería reprochar la ausencia de parecido con la representación usual del poliedro. Sin embargo, como un ejercicio de imaginación, el lector puede realizar el experimento imaginario de pensar los dos siguientes poliedros como si fuesen de hule y los pudiera deformar en la mente hasta lograr hacerlos planos --como en los grafos que los acompañan.
 
 
Como una aplicación elemental de los grafos, enseguida se presenta el
 

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).
 
Demostración
 
El problema se deja modelar mediante un grafo: Representemos con un punto (vértice o nodo) a cada una de las personas y unamos cada par de vértices con un segmento (arista o arco). Puesto que la relación de amistad puede o no existir entre cada par de amigos, tenemos que representar esa situación en el grafo. 
 
Pero esa relación de amistad o su ausencia es aleatoria en un grupo cualquiera de 6 personas. Así que la representación de este hecho no se puede realizar de una manera definida. 
 
La idea genial que se encontró para representarla es colorear a dos tintas las aristas de manera aleatoria: verde y rojo, por ejemplo. De esta manera, una coloración particular representa una reunión particular de 6 personas (en cuanto a su amistad o la ausencia de ella).
 
 
Ahora sí se puede razonar el problema y lograr una demostración. La demostración es como sigue (la de la derecha es el razonamiento con el grafo):
 
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.

Y la demostración está completa. (Porque el argumento es simétrico si iniciáramos con PA,PB,PC rojas --el lector se puede convencer fácilmente de ello cambiando el código de colores.)
 

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.)

Epílogo

 
Este teorema (de amigos y desconocidos) es uno de los teoremas cuyo atractivo radica en que, con mínima teoría, se demuestra un resultado sorprendente. Piense el lector en el teorema que dice: los puntos medios de un cuadrilátero forman un paralelogramo (conocido como teorema de Varignon).
 
Los saluda
jmd