El arte de contar

Le 13 octobre 2013  - Ecrit par  Juanjo Rué
Le 6 février 2019  - Traduit par  Jimena Royo-Letelier, Julio E. De Villegas
Article original : L’art de compter Voir les commentaires

Cet article a été écrit en partenariat avec L’Institut Henri Poincaré

El Instituto Henri Poincaré y Paisajes Matemáticos (Images des Mathématiques) han unido sus esfuerzos para supervisar la reedición de la colección El mundo es matemático, publicado por RBA en convenio con Le Monde. En 40 obras, esta colección de calidad, resultado de un proyecto colectivo de matemáticos españoles, aspira a presentar, a través de una gran variedad de puntos de vista, de múltiples facetas, las ciencias matemáticas, bajo un aspecto histórico, humano, social, técnico, cultural...

Revisado y mejorado al nivel de la forma, esta nueva edición fue completamente leída y corregida por el equipo de Images des Mathématiques ; prefacios y listas bibliográficas fueron agregadas. Le Monde consagra un suplemento especial para el lanzamiento de esta colección presentada por Cédric Villani, quien escribió el prefacio original.

Cada semana, con la salida de un nuevo número de la serie, un extracto seleccionado será presentado en Images des Mathématiques. Será acompañado por un resumen del libro y de una invitación a prolongar su lectura.

Extracto del capítulo 2. Grafos y mapas

En un grafo, un menor se construye como sigue : se dividen los vértices conectados en grupos y se considera las incidencias entre los diferentes grupos así compuestos (vea la figura siguiente). El menor se define como un grafo cuyos vértices son los grupos (las marcas grises donde se encuentran los vértices) y las aristas son las incidencias entre ellos. Aquí abajo, la construcción de un menor según la técnica descrita.

PNG - 45.6 ko
Un grafo y sus menores.

En el mundo de la teoría de grafos, existen algunos grafos particulares que tienen historia e incluso poseen un nombre especial debido a su importancia. Es lo que ocurre con el problema que tratamos. Dos grafos importantes son presentados en la siguiente ilustración : el grafo de cinco vértices y todas las aristas posibles (grafo denotado $K_5$ que se llama grafo completo con cinco vértices) y el grafo con seis vértices y nueve aristas ($K_{3,3}$ ). El lector puede tratar de dibujar esos grafos en el plano sin intersección y verá que es imposible. Del mismo modo, se puede tratar de demostrar que al borrar una de las aristas, ahora sí se podrá dibujarles sin intersección. De hecho, estos dos grafos son los más pequeños (en términos de número de vértices) que no son planos. En ese sentido, son los grafos no planos mínimos, ya que eliminar una de sus aristas les permite adquirir la propiedad de poder ser trazados sin intersección.

PNG - 26.8 ko
El grafo completo con 5 vértices K5 y el grafo bipartito K3,3.

Se puede demostrar por medio de un razonamiento elemental que estos dos grafos no son planos. Pero lo que es sorprendente, es que el recíproco es verdadero : si un grafo no posee ninguno de esos dos grafos como menor, entonces es plano. Este resultado, ahora clásico en el área, lo debemos al matemático polaco Kazimierz Kuratowski (Varsovia, 1896-1980), uno de los principales representantes de la escuela matemática polaca del siglo XX. Aquí está el enunciado del teorema de Kuratowski :

« Un grafo es plano si y solamente si no tiene $K_{3,3}$ o $K_5$ como menor. »

La siguiente observación se revela interesante : una condición topológica como el hecho de ser plano es intrínseca al grafo, no ligada a una representación cualquiera de este sobre una superficie. Conviene igualmente comentar que una condición también difícilmente realizable como la representación sin intersección de un grafo altamente complejo, se traduce en la única búsqueda de dos sub-estructuras claramente definidas en él. El teorema de Kuratowski es, de hecho, la parte visible del iceberg de una construcción matemática extremadamente compleja y rica, en el centro de la atención de una gran parte de la comunidad de especialistas de la combinatoria y el estudio de los algoritmos en lo que se llama la teoría de menores.

Se dice que la familia de los grafos planos es « cerrada bajo menores », lo que significa que todo menor de un grafo plano es igualmente plano. Esta propiedad deriva directamente de la definición de menor que enunciamos anteriormente. En este caso, el teorema de Kuratowski garantiza que los grafos de la familia en cuestión son únicamente caracterizados por los dos grafos que determinan el ser plano o no. Pero ¿es cierto que, de una manera general, toda familia de grafos cerrada bajo menores esté caracterizada por un conjunto finito de grafos prohibidos ? Esta pregunta, llamada conjetura de Wagner, es difícil, pero se puede responder de manera afirmativa : toda familia cerrada bajo menores está caracterizada por un conjunto finito de menores excluidos. Estas consideraciones han ocupado el frente de la escena de la teoría de grafos en la segunda mitad del siglo XX. En su gigantesca serie de más de veinte trabajos científicos (agrupados bajo el nombre de « Graph Minors » y consecutivamente enumerados por letras latinas) Neil Robertson y Paul Seymour plantean las bases estructurales de esta teoría matemática. Sus implicaciones son capitales en la teoría de grafos actual y, por eso, una gran parte de las investigaciones de la disciplina está hoy en día guiada por esta obra monumental. El teorema de Robertson-Seymour es el impresionante resultado del trabajo conjunto de los dos científicos.

Esta teoría tiene implicancias más profundas en el estudio estructural de los grafos ; en realidad, se trata de uno de los temas de investigación más desarrollados en el campo de la combinatoria y de la algorítmica de la teoría de grafos.

Una aplicación industrial

PNG - 117.2 ko

Saber si un grafo dado admite o no una representación plana es un problema capital en la industria. En electrónica, es indispensable saber fabricar un modelo eléctrico dado de la manera más simple posible. En efecto, mientras más complicaciones haya, los métodos de producción serán más caros. Por ejemplo, cuando se sabe qué modelo de circuito uno desea utilizar, hay que ser capaz de decir si ese modelo puede ser representado sobre un circuito impreso en el plano. Si no es posible representar el circuito sin intersección, el proceso industrial de fabricación costará más caro, en la medida en que las placas de silicio tendrán necesidad de más de una capa para cubrir las diferentes conexiones de cobre. Sabiendo que el proceso de producción de dichos circuitos consta de millones de unidades, el estudio de los grafos planos es un factor clave en una lógica de optimización de costos. Hay diferentes programas concebidos especialmente para determinar si un modelo eléctrico admite una representación plana y, llegado el caso, optimizar esta representación sobre un circuito impreso.

Para profundizar

He aquí algunos mensajes y artículos acerca del tema :

Post-scriptum :

El extracto propuesto fue escogido por el autor del prefacio del libro Patrick Popescu-Pampu. Él responderá los eventuales comentarios.

Partager cet article

Pour citer cet article :

Julio E. De Villegas, Jimena Royo-Letelier — «El arte de contar» — Images des Mathématiques, CNRS, 2019

Crédits image :

Image à la une - Marion Bucciarelli

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é ?

L'auteur

Juanjo Rué

Dossiers

Cet article fait partie du dossier «Le monde est mathématique» voir le dossier