Grafos
Piste verte Le 3 novembre 2011Le 5 octobre 2020
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
[1] L. Euler, Solutio problematis ad geometriam situs pertinentis.
Commentarii academiae scientiarum imperialis Petropolitanae,
8 (1736), 128-140.
[2] G. Kirchhoff, Über die Auflösung der Gleichungen, auf welche man bei der Unter-suchung der linearen Verteilung galvanischer Ströme geführt wird. Ann. Phys. Chem., 72 (1847), 497-508.
[3] A. Cayley, On the mathematical theory of isomers. Philos. Mag., 67 (1874), 444-467.
[4] conocido 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.
[5] Se trata de un grafo completo donde toda pareja de vértices está unida por una arista.
[6] Vea también [http://mathworld.wolfram.com/RamseyNumber.html
[7] Planteada en la primera nota Comienzo de paseo de esta serie.
[8] Los 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.
[9] No 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
Laisser un commentaire
Actualités des maths
-
7 avril 2021Les maths dans la musique... la musique des maths (en ligne, 8/4)
-
16 mars 2021Des signaux partout – Des chauves-souris à Internet (en ligne, 25/3)
-
11 mars 2021Mathématiciens engagés : regards croisés (en ligne, 16/3)
-
10 mars 2021Astigmath, un quiz culturel pour tous et toutes (14/3)
-
8 mars 2021Cinquième édition du festival « Les maths dans tous leurs états »
-
23 février 2021Courbes et surfaces : le monde de Maryam Mirzakhani (Twitch, 1/3)
Commentaire sur l'article