Grafos

Piste verte Le 3 novembre 2011  - Ecrit par  Fernando Alcalde
Le 5 octobre 2020  - Traduit par  Jimena Royo-Letelier, Julio E. De Villegas
Article original : Graphes Voir les commentaires
Lire l'article en  

La teoría de grafos es un lindo ejemplo de teoría matemática unida a la realidad desde su origen.
El problema de los puentes de Königsberg
 [1] resuelto por Leonhard Euler en 1736, el estudio de las
redes eléctricas
 [2]
por Gustav Kirchhoff en 1847 o la enumeración de los isómeros de los hidrocarburos saturados acíclicos [3] por Arthur Cayley en 1874 ilustran bien esta idea. Pero yo voy a centrarme en otro asunto
 [4] : en todo grupo de seis personas, hay al menos tres de ellas que se conocen, o bien tres personas que no se conocen. Representemos cada una de esas personas por un punto, luego unamos dos puntos por un segmento rectilíneo de color rojo si todas las personas se conocen, o azul si no se conocen.

El asunto se transforma entonces en un teorema, llamado teorema de Ramsey, que se puede reformular de la siguiente manera : el grafo bicolor G así obtenido [5] contiene ya sea un triángulo rojo o sea un triángulo azul. Mejor aún : ya sea el sub-grafo rojo R de personas que se conocen, como el sub-grafo azul B de personas que no se conocen
(llamado el complementario de R), uno contiene un triángulo.

En realidad, Frank P. Ramsey demostró un teorema más general : para toda pareja de enteros positivos m y n, existe un número entero R(m,n), llamado número de Ramsey [6], tal que todo grafo completo bicolor G que tenga al menos ese número de vértices contiene un sub-grafo completo (o pandilla) con m vértices de un color o con n vértices del otro color. Tal como antes, el grafo rojo R debe entonces contener un sub-grafo completo con m vértices, o bien su complementario azul B contendrá un sub-grafo completo con n vértices.

La prueba de nuestro comentario es muy simple. Establezcamos un vértice cualquiera P. Está unido a los otros cinco vértices por aristas de color rojo o azul. Tendrá a lo menos tres aristas del mismo color, digamos rojo. Sus extremos A, B y C están también unidos por aristas de dos colores. Si una de esas tres aristas (digamos AB) es roja, tendremos por lo tanto un triángulo rojo PAB. Por el contrario, si ninguna es roja, tendremos un triángulo azul ABC.

Esta prueba se desmorona en cuanto se considera un grupo de cinco personas. En efecto, este es un grafo bicolor que no contiene ningún triángulo del mismo color :

Hemos verificado bien que R(3,3) = 6.

Pero volvamos a nuestra pregunta original [7] : ¿por qué el árbol de Kenyon es lindo ?

Uno podría pensar en las simetrías, pero no son muy numerosas : cuatro rotaciones, cuatros reflexiones y sus composiciones. Por lo tanto, cambiemos de idea y tratemos de construir un árbol de la siguiente manera. Partamos de un punto

luego fijemos uno de los cuatro puntos cardinales -Norte, Sur, Este y Oeste abreviados como N, S, E y O-, digamos O. Esta elección determina una arista (coloreada de rojo) que uno puede repetir en las otras tres direcciones N, E y S :

La elección de un segundo punto cardinal (digamos S) permite trazar un camino (formado por dos aristas coloreadas de rojo) y repetir la imagen en las otras direcciones :

Cada secuencia de puntos cardinales [8] determina un árbol punteado. Por ejemplo, el de la imagen, que empuja hacia el oeste, corresponde a la secuencia OSNE…

Esta es la construcción :

No es el árbol de Kenyon, ya que solo hay una manera de ir al infinito sin ir y volver, mientras que en el árbol de Kenyon hay cuatro maneras distintas. Además, es menos simétrico [9]. Sin embargo, es tan bonito como el árbol de Kenyon.

Parecidos a sí mismos alrededor de todo punto, esos dos árboles son indistinguibles a pequeña escala. Aventuremos una respuesta : es su naturaleza repetitiva las que los hace hermosos..

Notes

[3A. Cayley, On the mathematical theory of isomers. Philos. Mag., 67 (1874), 444-467.

[4conocido como « Party theorem » o « Theorem on friends and strangers » en la literatura anglosajona. Se encontrará una descripción un poco más precisa de esto en el sitio de Wikipedia.

[5Se trata de un grafo completo donde toda pareja de vértices está unida por una arista.

[6Vea también [http://mathworld.wolfram.com/RamseyNumber.html

[7Planteada en la primera nota Comienzo de paseo de esta serie.

[8Los matemáticos preferirán reemplazar E, N, O y S por 00, 10, 01 y 11 de manera de obtener una secuencia formada por 0 y 1.

[9No admite ninguna simetría como árbol punteado, sino una reflexión horizontal si uno olvida el origen.

Partager cet article

Pour citer cet article :

Julio E. De Villegas, Jimena Royo-Letelier — «Grafos» — Images des Mathématiques, CNRS, 2020

Crédits image :

Image à la une - Fernando Alcalde
img_6965 - Fernando Alcalde
img_6977 - Fernando Alcalde
img_6968 - Wikipedia
img_6969 - Álvaro Lozano Rojo
img_6973 - Álvaro Lozano Rojo
img_6975 - Álvaro Lozano Rojo
img_6976 - Álvaro Lozano Rojo

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?